A Binary Tree in C

A

arnuld

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]$
 
B

Ben Bacarisse

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

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;
};

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>
 
N

Nick Keighley

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
 
B

Bill Cunningham

Ben Bacarisse said:
arnuld said:
A Binary Search Tree implemented in C. Any advice on how to complete the
one remained function ?

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
 
B

Bill Cunningham

arnuld said:
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
 
B

Ben Bacarisse

Bill Cunningham said:
Ben Bacarisse said:
arnuld said:
A Binary Search Tree implemented in C. Any advice on how to complete the
one remained function ?

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.
 
A

arnuld

..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 ?
 
B

Ben Bacarisse

arnuld said:
..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.
 
A

arnuld

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.
 
A

arnuld

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

We are even then :)


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.

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 ?
 
B

Ben Bacarisse

arnuld said:
That does not work, I already tried.

You are on your own then unless you explain "does not work" or you
specify "properly aligned"!
But that way, memory will still be there being used by the elements.

How bad a problem is that? It may be a show-stopper or it may be
quite unimportant.
I will take this one then.

Which one? The leaf only option may use more memory than leaving
nodes with a count of zero.
So I can conclude when you want to remove lots
of elements then Binary Search Tree is not the choice to make ?

No. The benefit does decrease as the proportion of deletes vs.
look-ups increases -- but that is not the same as a bad choice.
 
G

Guest

| /* 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;
| };

This isn't a binary tree issue, but a data structure issue.
What I do for any kind of struct with ONE variable part is
put the variable part last, define it as having 1 member,
but actually allocate the node as large as needed. I do this
for binary trees and for linked lists. The complication is
when you want the key and value to both be variable. But
even this can be done in a single piece of data.
 
K

Keith Thompson

| /* 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;
| };

This isn't a binary tree issue, but a data structure issue.
What I do for any kind of struct with ONE variable part is
put the variable part last, define it as having 1 member,
but actually allocate the node as large as needed. I do this
for binary trees and for linked lists. The complication is
when you want the key and value to both be variable. But
even this can be done in a single piece of data.

This is the infamous "struct hack"; see question 2.6 of the
comp.lang.c FAQ, <http://www.c-faq.com/>.
 
A

arnuld

You are on your own then unless you explain "does not work" or you
specify "properly aligned"!

I will leave this feature as its not technical point but printing that
pleases to eyes.

How bad a problem is that? It may be a show-stopper or it may be quite
unimportant.


I think it a very serious problem. When an element is not in use then we
need to free the memory hold by it otherwise it could lead to Segfault or
malloc() failed when system will have no memory to allocate.


Which one? The leaf only option may use more memory than leaving nodes
with a count of zero.

I will write a balanced tree then. if a data-structure does not allow me
to free the memory, its of no use.

No. The benefit does decrease as the proportion of deletes vs. look-ups
increases -- but that is not the same as a bad choice.


If a program can't free the memory, how good is that. The it will be like
writing one more Windows.
 
B

Ben Bacarisse

arnuld said:
I think it a very serious problem. When an element is not in use then we
need to free the memory hold by it otherwise it could lead to Segfault or
malloc() failed when system will have no memory to allocate.

Only you know, of course, but what you give here is a very general
argument. Note that what I suggested does not mean that the space
can't every be reclaimed. When the tree is no longer needed you can
delete it and as you delete more and more nodes, more of the nodes
will have null left and right pointers and you can always clean up the
tree -- either looking for nodes that have only zero-count children or
simply deleting an re-building it.

I felt it worth suggesting because allocating fixed-length strings in
the nodes is also wasteful of space so I did not think you were being
careful with memory use.

I will write a balanced tree then. if a data-structure does not allow me
to free the memory, its of no use.

All the above is beside the point now because a balanced tree is
absolutely the right way to do it.

<snip>
 
G

Guest

| I think it a very serious problem. When an element is not in use then we
| need to free the memory hold by it otherwise it could lead to Segfault or
| malloc() failed when system will have no memory to allocate.

I have written programs where I needed the binary tree(s) right up to the
end of the program. I could have then gone through the tree and freed
each node. But I didn't. I let VM destruction take care of it. That is
not an option when the VM is not being destroyed or it's not a VM case
(such as a kernel or driver). I regularly skip free() calls in my CGI
code, for example, because the VM lifetime is so short.


| I will write a balanced tree then. if a data-structure does not allow me
| to free the memory, its of no use.

In my AVL code, I did write an avl_empty() function. It deletes all the
nodes in a tree without the extra work that would be needed (such as the
pointless rebalancing) by calling avl_delete() in a loop. It calls a
provided callback function passing it the pointer to the node. I pass it
the function pointer for free() in most cases.

I see no reason free() cannot be used when deleting a node, or all nodes
all at once.
 
A

arnuld

Only you know, of course, but what you give here is a very general
argument. Note that what I suggested does not mean that the space can't
every be reclaimed. When the tree is no longer needed you can delete it
and as you delete more and more nodes, more of the nodes will have null
left and right pointers and you can always clean up the tree -- either
looking for nodes that have only zero-count children or simply deleting
an re-building it.


I don't follow you here. Lets leave the zero-count feature and talk about
deleting (which of course means free()ing) the tree elements. You say,
you did not suggest that memory hold by the elements can not be
reclaimed. Fine, that is what I want, to get back the memory but then u
suggest, in the last line, to simple deleting and building the whole tree
which of course seems like a wastage of resources to me when the input is
much larger.



I felt it worth suggesting because allocating fixed-length strings in
the nodes is also wasteful of space so I did not think you were being
careful with memory use.

You have 2 choices here, either allocate the local array or use pointer
and then malloc() the memory. I did not want to use malloc(), I avoid
malloc() *all* the time *while* I can.
All the above is beside the point now because a balanced tree is
absolutely the right way to do it.

Okay, Balanced Tree is the next Data Structure I will implement in C. I
have fever, there is some sort of flu that is happened to spread
Hyderabad (this is where I work). I have 5 days of medication, after that
I will work on Balanced Tree.
 
B

Ben Bacarisse

arnuld said:
I don't follow you here. Lets leave the zero-count feature and talk about
deleting (which of course means free()ing) the tree elements. You say,
you did not suggest that memory hold by the elements can not be
reclaimed. Fine, that is what I want, to get back the memory but then u
suggest, in the last line, to simple deleting and building the whole tree
which of course seems like a wastage of resources to me when the input is
much larger.

And it may not be worth it. I was just offering alternatives. You
seemed to be making a general claim that not deleting every node as
early as possible is useless, but that is not true. It is not space
optimal but there may be programs in which it is the right balance
between programming complexity and performance.
You have 2 choices here, either allocate the local array or use pointer
and then malloc() the memory. I did not want to use malloc(), I avoid
malloc() *all* the time *while* I can.

(Aside: local is not the best word. You mean in the same struct.
Local should probably be kept to refer to named objects with automatic
storage class.)

Allocating the string in the same struct as the pointers does not mean
that they have to be of fixed size. C99 has formalised "the struct
hack" that was common in C90 for dealing with this.

Secondly, you can reduce the number of malloc calls in other ways: you
could allocate large string buffers and use them to store your
strings, allocating again when they run out, or you could allocate
arrays of node structures and hand these out as you need them. In the
bad old days these were very useful techniques, but it their relative
benefit has decreased as malloc (and OS memory allocation) have got
better. I am not suggesting your do either, but I do want to explain
why, to me, your program does not look as if you want to avoid malloc
wherever possible.
Okay, Balanced Tree is the next Data Structure I will implement in C. I
have fever, there is some sort of flu that is happened to spread
Hyderabad (this is where I work). I have 5 days of medication, after that
I will work on Balanced Tree.

Sorry to hear that. I with you a speedy recovery.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top