Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > A Binary Tree in C

Reply
Thread Tools

A Binary Tree in C

 
 
arnuld
Guest
Posts: n/a
 
      08-04-2009
A Binary Search Tree implemented in C. Any advice on how to complete the
one remained function ?


/* A Binary tree learned from "The Practice of Programming", section
2.8 . Its a little bit different though. It also includes the
* count of each element added into the tree. Currentlly it supports 3
functions: adding an element, printing and free()ing the whole
* tree. Only one fucntion, the deletion of a single element, have
remained.
*
*
* VERSION 0.0
*
*/


#include <stdio.h>
#include <stdlib.h>
#include <string.h>

enum { SIZE_NAME = 30 };


/* One disadvantage of using char [] as a struct memeber is the size of
name is limited. but if we use char* there will be no limit
on the size then. */
struct namev
{
char name[SIZE_NAME];
int cnt;
struct namev* left;
struct namev* right;
};


struct namev* tree_add_name(struct namev*, char* );
void tree_free(struct namev* );
void tree_print(struct namev* );
struct namev* tree_delete_name(struct namev*, char*);



int main(void)
{
struct namev* root = NULL;

root = tree_add_name(root, "comp.lang.c");
root = tree_add_name(root, "comp.lang.c++");
root = tree_add_name(root, "comp.lang.lisp");
root = tree_add_name(root, "comp.unix.programmer");
root = tree_add_name(root, "comp.unix.programmer");
root = tree_add_name(root, "comp.lang.c");
root = tree_add_name(root, "comp.lang.");


tree_print(root);

return 0;
}


struct namev* tree_add_name(struct namev* r, char* name)
{
int cmp;

if(NULL == name)
{
fprintf(stderr, "FILE: %s, LINE: %d : No name provided\n",
__FILE__, __LINE__);
return r;
}


if(NULL == r) /* We got a new element */
{
r = malloc(1 * sizeof *r);
if(NULL == r)
{
fprintf(stderr,"FILE: %s, LINE: %d : malloc() failed\n",
__FILE__, __LINE__);
return NULL;
}
strcpy(r->name, name);
r->cnt = 1;
r->left = r->right = NULL;
}
else if(0 == (cmp = strcmp(name, r->name)))
{
r->cnt++;
}
else if(cmp < 0)
{
r->left = tree_add_name(r->left, name);
}
else
{
r->right = tree_add_name(r->right, name);
}

return r;
}



void tree_free(struct namev* r)
{
if(r)
{
tree_free(r->left);
tree_free(r->right);
tree_free(r);

r = NULL;
}
}


void tree_print(struct namev* r)
{
if(r)
{
tree_print(r->left);
printf("name = %s, count = %d\n", r->name, r->cnt);
/* how can I keep those printed elements properly aligned ? */
tree_print(r->right);
}
}



struct namev* tree_delete_name(struct namev* e, char* c)
{
int cmp;

if(NULL == e || NULL == c)
{
fprintf(stderr, "FILE: %s, LINE: %d: NUL arguments\n", __FILE__,
__LINE__);
return e;
}
else if(0 == (cmp = strcmp(c, e->name)))
{
/* How can keep the pointers/left-right intact after free()ing
this ?
or I am just dealing with a theoretical problem. Practically, we
never remove a single element from a tree ?? */
}
else if(cmp < 0)
{
tree_delete_name(e->left, c);
}
else
{
tree_delete_name(e->right, c);
}

return e;
}


=================== OUTPUT ==========================
[arnuld@dune programs]$ gcc -ansi -pedantic -Wall -Wextra binary-tree.c
[arnuld@dune programs]$ ./a.out
name = comp.lang., count = 1
name = comp.lang.c, count = 2
name = comp.lang.c++, count = 1
name = comp.lang.lisp, count = 1
name = comp.unix.programmer, count = 2
[arnuld@dune programs]$










--
www.lispmachine.wordpress.com
my email is @ the above blog.

 
Reply With Quote
 
 
 
 
Ben Bacarisse
Guest
Posts: n/a
 
      08-04-2009
arnuld <(E-Mail Removed)> writes:

> A Binary Search Tree implemented in C. Any advice on how to complete the
> one remained function ?


<snip>
> enum { SIZE_NAME = 30 };
>
>
> /* One disadvantage of using char [] as a struct memeber is the size of
> name is limited. but if we use char* there will be no limit
> on the size then. */


Yes, I'm not a fan of fixed-size arrays for string, but they are
simple.

> struct namev
> {
> char name[SIZE_NAME];
> int cnt;
> struct namev* left;
> struct namev* right;
> };


<snip>
> void tree_print(struct namev* r)
> {
> if(r)
> {
> tree_print(r->left);
> printf("name = %s, count = %d\n", r->name, r->cnt);
> /* how can I keep those printed elements properly aligned ? */


You can't -- not without finding the longest string first and using
that as a field width. try %20s or %-20s for the moment and see if
that is what you want.

> tree_print(r->right);
> }
> }
>
>
>
> struct namev* tree_delete_name(struct namev* e, char* c)
> {
> int cmp;
>
> if(NULL == e || NULL == c)
> {
> fprintf(stderr, "FILE: %s, LINE: %d: NUL arguments\n", __FILE__,
> __LINE__);
> return e;
> }
> else if(0 == (cmp = strcmp(c, e->name)))
> {
> /* How can keep the pointers/left-right intact after free()ing
> this ?
> or I am just dealing with a theoretical problem. Practically, we
> never remove a single element from a tree ?? */


If e->left and e->right are both NULL you can delete and return NULL.
if only one of them is non-null you can return that pointer but what
do you do if both are non-null? One strategy (that you can use in the
other cases as well, BTW) is to set e->cnt to zero. Provided that
your print and any future "find" function ignore strings with zero
count, it will all work.

The usual alternatives are to write a balanced tree, or to store
strings only in leaf nodes.

> }
> else if(cmp < 0)
> {
> tree_delete_name(e->left, c);


You have to write:

e->left = tree_delete_name(e->left, c);

or the tree is not modified.

> }
> else
> {
> tree_delete_name(e->right, c);


and again here.

> }
>
> return e;
> }


<snip>
--
Ben.
 
Reply With Quote
 
 
 
 
Nick Keighley
Guest
Posts: n/a
 
      08-04-2009
On 4 Aug, 12:25, arnuld <(E-Mail Removed)> wrote:

> void tree_free(struct namev* r)
> {
> * if(r)
> * * {
> * * * tree_free(r->left);
> * * * tree_free(r->right);
> * * * tree_free(r);
>
> * * * r = NULL;
> * * }
>
> }


this looks odd. Suppose you have a tree with only a single node in it.

&r = 7777;
r->left = 0;
r->right = 0;

now call tree_free(&r) a trace looks like this

tree_free (777)
tree_free (0)
tree_free (0)
tree_free (777) oops!

I think you should have freed a node rather than a tree
 
Reply With Quote
 
Bill Cunningham
Guest
Posts: n/a
 
      08-04-2009

"Ben Bacarisse" <(E-Mail Removed)> wrote in message
news:0.f11bf2999539fa89b8b6.20090804133058BST.87fx (E-Mail Removed)...
> arnuld <(E-Mail Removed)> writes:
>
>> A Binary Search Tree implemented in C. Any advice on how to complete the
>> one remained function ?

>
> <snip>
>> enum { SIZE_NAME = 30 };
>>
>>
>> /* One disadvantage of using char [] as a struct memeber is the size of
>> name is limited. but if we use char* there will be no limit
>> on the size then. */

>
> Yes, I'm not a fan of fixed-size arrays for string, but they are
> simple.
>
>> struct namev
>> {
>> char name[SIZE_NAME];
>> int cnt;
>> struct namev* left;
>> struct namev* right;
>> };


For what it's worth. I would've used
char name[CHAR_MAX];

Bill


 
Reply With Quote
 
Bill Cunningham
Guest
Posts: n/a
 
      08-04-2009

"arnuld" <(E-Mail Removed)> wrote in message
news(E-Mail Removed)...
>A Binary Search Tree implemented in C. Any advice on how to complete the
> one remained function ?
>
>
> /* A Binary tree learned from "The Practice of Programming", section
> 2.8 . Its a little bit different though. It also includes the
> * count of each element added into the tree. Currentlly it supports 3
> functions: adding an element, printing and free()ing the whole
> * tree. Only one fucntion, the deletion of a single element, have
> remained.
> *
> *
> * VERSION 0.0
> *
> */
>
>
> #include <stdio.h>
> #include <stdlib.h>
> #include <string.h>
>
> enum { SIZE_NAME = 30 };
>
>
> /* One disadvantage of using char [] as a struct memeber is the size of
> name is limited. but if we use char* there will be no limit
> on the size then. */
> struct namev
> {
> char name[SIZE_NAME];
> int cnt;
> struct namev* left;
> struct namev* right;
> };
>
>
> struct namev* tree_add_name(struct namev*, char* );
> void tree_free(struct namev* );
> void tree_print(struct namev* );
> struct namev* tree_delete_name(struct namev*, char*);
>
>

Thanks Arnuld. Something here just clicked. I've been struugling with
this algorithm for awhile. What you have written above is simple.

Bill


 
Reply With Quote
 
Ben Bacarisse
Guest
Posts: n/a
 
      08-04-2009
"Bill Cunningham" <(E-Mail Removed)> writes:

> "Ben Bacarisse" <(E-Mail Removed)> wrote in message
> news:0.f11bf2999539fa89b8b6.20090804133058BST.87fx (E-Mail Removed)...
>> arnuld <(E-Mail Removed)> writes:
>>
>>> A Binary Search Tree implemented in C. Any advice on how to complete the
>>> one remained function ?

>>
>> <snip>
>>> enum { SIZE_NAME = 30 };
>>>
>>>
>>> /* One disadvantage of using char [] as a struct memeber is the size of
>>> name is limited. but if we use char* there will be no limit
>>> on the size then. */

>>
>> Yes, I'm not a fan of fixed-size arrays for string, but they are
>> simple.
>>
>>> struct namev
>>> {
>>> char name[SIZE_NAME];
>>> int cnt;
>>> struct namev* left;
>>> struct namev* right;
>>> };

>
> For what it's worth. I would've used
> char name[CHAR_MAX];


That would be very odd. CHAR_MAX is defined to be the largest value
that plain char can hold. It bears no relationship to the length of
name that one might want to store in this tree.

--
Ben.
 
Reply With Quote
 
arnuld
Guest
Posts: n/a
 
      08-05-2009
> On Tue, 04 Aug 2009 11:25:45 +0000, arnuld wrote:

> ..SNIP...


> struct namev
> {
> char name[SIZE_NAME];
> int cnt;
> struct namev* left;
> struct namev* right;
> };
>



Can't we do something like we do with a Queue in C:


struct my_struct
{
int num;
struct my_struct* next;
};

struct my_list
{
struct my_struct* head;
struct my_struct* tail;
};



See the original struct is something but we implemented Queue in a new
struct using 2 pointers to the original struct. Can we do something like
that with Binary Tree ?




--
www.lispmachine.wordpress.com
my email is @ the above blog.

 
Reply With Quote
 
Ben Bacarisse
Guest
Posts: n/a
 
      08-05-2009
arnuld <(E-Mail Removed)> writes:

>> On Tue, 04 Aug 2009 11:25:45 +0000, arnuld wrote:

>
>> ..SNIP...

>
>> struct namev
>> {
>> char name[SIZE_NAME];
>> int cnt;
>> struct namev* left;
>> struct namev* right;
>> };
>>

>
> Can't we do something like we do with a Queue in C:
>
> struct my_struct
> {
> int num;
> struct my_struct* next;
> };
>
> struct my_list
> {
> struct my_struct* head;
> struct my_struct* tail;
> };


The first name is not very helpful. The two structures define,
respectively, a node in a list and the list itself. I'd call the
first my_node (if i had to use a "my_" prefix).

> See the original struct is something but we implemented Queue in a new
> struct using 2 pointers to the original struct. Can we do something like
> that with Binary Tree ?


Yes, but it helps less because the whole tree is one pointer, rather
than two. You end up with:

struct my_tree {
struct my_tree_node *root;
};

Of course, if there is any reason to hold extra information then it
starts to look more useful. However, because a tree is recursive, you
will often find that any extra information you need (like, say, the
depth) will be needed at every node, so it never belongs to the root
alone.

--
Ben.
 
Reply With Quote
 
arnuld
Guest
Posts: n/a
 
      08-06-2009
> On Aug 4, 6:30*pm, Nick Keighley <(E-Mail Removed)> wrote:
>> On 4 Aug, 12:25, arnuld <(E-Mail Removed)> wrote:
> > void tree_free(struct namev* r)
> > {
> > * if(r)
> > * * {
> > * * * tree_free(r->left);
> > * * * tree_free(r->right);
> > * * * tree_free(r);

>
> > * * * r = NULL;
> > * * }

>
> > }



> this looks odd. Suppose you have a tree with only a single node in it.
>
> * *&r = 7777;
> * * r->left = 0;
> * * r->right = 0;
>
> now call tree_free(&r) a trace looks like this
>
> * *tree_free (777)
> * * * *tree_free (0)
> * * * *tree_free (0)
> * * * *tree_free (777) * oops!
>
> *I think you should have freed a node rather than a tree


I am sure I did not get you.
 
Reply With Quote
 
arnuld
Guest
Posts: n/a
 
      08-06-2009
> On Tue, 04 Aug 2009 13:30:58 +0100, Ben Bacarisse wrote:
>> arnuld wrote:


> Yes, I'm not a fan of fixed-size arrays for string, but they are simple.


We are even then



>> void tree_print(struct namev* r)
>> {
>> if(r)
>> {
>> tree_print(r->left);
>> printf("name = %s, count = %d\n", r->name, r->cnt); /* how can
>> I keep those printed elements properly aligned ? */


> You can't -- not without finding the longest string first and using that
> as a field width. try %20s or %-20s for the moment and see if that is
> what you want.


That does not work, I already tried.


>> /* How can keep the pointers/left-right intact after free()ing this ?
>> or I am just dealing with a theoretical problem. Practically, we
>> never remove a single element from a tree ?? */


> If e->left and e->right are both NULL you can delete and return NULL. if
> only one of them is non-null you can return that pointer but what do you
> do if both are non-null? One strategy (that you can use in the other
> cases as well, BTW) is to set e->cnt to zero. Provided that your print
> and any future "find" function ignore strings with zero count, it will
> all work.


But that way, memory will still be there being used by the elements.


> The usual alternatives are to write a balanced tree, or to store strings
> only in leaf nodes.


I will take this one then. So I can conclude when you want to remove lots
of elements then Binary Search Tree is not the choice to make ?



--
www.lispmachine.wordpress.com
my email is @ the above blog.

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Binary tree search vs Binary search Bogdan C Programming 22 10-21-2010 09:46 PM
Hi, I want to implement a General Tree Data structure (Not Binary Tree ) which have more than 2 sub nodes? sharan C Programming 2 10-31-2007 02:58 AM
Hi, I want to implement a General Tree Data structure (Not Binary Tree ) which have more than 2 sub nodes? sharan C Programming 1 10-30-2007 11:01 PM
Hi, I want to implement a General Tree Data structure (Not Binary Tree ) which have more than 2 sub nodes? sharan C Programming 4 10-30-2007 08:21 PM
B tree, B+ tree and B* tree Stub C Programming 3 11-12-2003 01:51 PM



Advertisments