Binary Trees in C

Question

I'm trying to insert nodes into a tree in order. My function works fine... when there's only three nodes.

I have this code:

typedef struct _Tnode Tnode;
struct _Tnode {
    char* data;
    Tnode* left;
    Tnode* right;
};

Along with this:

Tnode* add_tnode(Tnode* current_node, char* value) {
Tnode* ret_value; 

if(current_node == NULL) {
 current_node = (Tnode*) malloc(sizeof(Tnode));

 if(current_node != NULL) {
   (current_node)->data = value;
   (current_node)->left = NULL;
   (current_node)->right = NULL;
   ret_value = current_node; }
 else 
  printf("no memory"); 
}
else {
 if(strcmp(current_node->data,value)) { //left for less than 

  ret_value = add_tnode((current_node->left), value);
  current_node -> left = (Tnode*) malloc(sizeof(Tnode));
  (current_node -> left) -> data = value;
 }

 else if(strcmp(current_node->data,value) > 0) {

  ret_value = add_tnode((current_node -> right), value);
  current_node -> right = (Tnode*) malloc(sizeof(Tnode));
  (current_node -> right) -> data = value;
 }

 else {
  printf("duplicate\n");
  ret_value = current_node;
 }
}

return ret_value;

}

I know what's wrong here, I just don't know how to fix it. This just overwrites the two nodes attached to the root node. i.e.

         |root_node|
        /           \
|node_2|             |node_3|

I can't add a node four. It just overwrites node 2 or 3 depending on the input. After debugging and a little research, I'm not quite sure where to go from here...

If anyone can help, I'd really appreciate it.

Answer 1

I guess that you'll need to add a pointer to the parent node to the _Tnode struct.

Answer 2

This would appear to just be a school project.

Where to begin.

1) You are clobbering left/right all the way down the tree. I'm not sure why you would expect them to be preserved since: a) You always write to these nodes. b) The only time you return an existing node is on a strcmp match.

2) You really need to check strcmp < 0 on your first compare.

3) For a non-balanced tree, there's no reason to use recursion - you can just use a loop until you get to a leaf and then hook the leaf. If you really want recursion...

4) Recursive... Return NULL in all cases except when you create a node (ie: the first part where you have current == NULL).

5) In the left/right, store the return value in a temp local Node*. Only if the return value is not NULL should you assign left/right.

Even this doesn't feel right to me, but if I started from scratch it just wouldn't look like this at all. :) We won't even get into the memory leaks/crashes you probably will end up with by just pushing 'char *' values around all willy nilly.

Answer 3

for starters - the first strcmp

if(strcmp(current_node->data,value))

is probably not right - this is true for both less than and greater than, and then the second if does not make sense

Answer 4

The problem is that after making your recursive function call to add_tnode, on the left branch, say, you are obliterating that same branch with your malloc. The malloc should only happen when you have recursed down to the point where you will be adding the node, not when you are making a recursive call.

Essentially, in a particular function call, you should either make a recursive call OR malloc a new node, not both.

This also produces a memory leak, probably.

Answer 5

You should leave the mallocing only to the case where the insertion reaches a leaf node (ie NULL). In the other cases, all you should do is to traverse to the next level depending on your comparison. In your case, you're traversing to the next level, and then killing it with a new malloc. Because of this you're never getting past the first level.

eg.

if (current_node == NULL) // Do initialization stuff and return current_node

if (strcmp(current_node->data, value) < 0) {
    current_node->left = add_tnode((current_node->left), value);
} else if (strcmp(current_node->data, value) > 0) {
    current_node->right = add_tnode((current_node->right), value);
}

return current_node;

Answer 6

Once you found out, that current_node->data is not null and compared it with value, you first have to check whether the corresponding pointer current_node->left (or ->right) is already in use (!= NULL).

If it is null, you proceed as you do. That is the case that works fine now.

If not, you have to retest the whole thing against the correspondig node, calling your function again on the cooresponding node. Here some pseudo code:

Wrap the code with:

void Add_node(Tnode* current_node) {
...
else {
        if(strcmp(current_node->data,value) < 0) {  //left for less than 
           if(current_node->left != NULL) {
                Add_node(current_node->left);
           } else {
                ret_value = add_tnode((current_node->left), value);
                current_node -> left = (Tnode*) malloc(sizeof(Tnode));
                (current_node -> left) -> data = value;
        } else if(strcmp(current_node->data,value) > 0) {
                Add_node(current_node->right);
           } else {
           ...
}

This is called recoursion (a function callin itself) and walk through the tree. To read some node, you have to do a recursive function again. Be carefull that they terminate (here at some point the left or right pointer will be null, thus terminating the recursive calling).

Answer 7

If you aren't implementing this for your own edification, I would just use libavl

Answer 8

You don't need to know the parent of the node. just the value at the current node.

Pseudocode:

add_treenode(root, value)

{

 //check if we are at a leaf  
 if root == null
     allocate space for new node.
     set children to null
     save root->value = value
     return root // if you need to return something, return the node you inserted.
 //if not, this node has a value
 if root->value < value  //use strcmp since value is a string
       add_tnode(root->left, value)
 else
       add_tnode(root->right, value)
 return NULL

}

This is as clean as it gets when it comes to inserting a new tree node. pass the root and the value of the node you want to insert, and it does the rest.

Answer 9

struct _Tnode {
        char* data;
        struct _Tnode * left, * right;
    };
    typedef struct _Tnode Tnode;

void addNode(Tnode ** tree, Tnode * node){

    if(!(*tree)){
        *tree = node;
        return;
    }

    if(node->data < (*tree)->val){
       insert(&(*tree)->left, node);
    }else if(node->data>(*tree)->data){
       insert(&(*tree)->right, node);
    }

}