CODEWITHSUNDEEP
cbinary-tree
devin
devin

Reputation: 6527

Binary Trees in C

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.

Upvotes: 1

Views: 1457

Answers (9)

Grekoz
Grekoz

Reputation: 81

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

}

Upvotes: 2

Ralph M. Rickenbach
Ralph M. Rickenbach

Reputation: 13163

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

Upvotes: 0

Dortz
Dortz

Reputation: 177

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.

Upvotes: 0

sbooth
sbooth

Reputation: 16976

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

Upvotes: 0

sykloid
sykloid

Reputation: 101206

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;

Upvotes: 2

Rob Lachlan
Rob Lachlan

Reputation: 14459

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.

Upvotes: 0

Jeff
Jeff

Reputation: 2009

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

Upvotes: 1

Joe
Joe

Reputation: 2976

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.

Upvotes: 2

arul
arul

Reputation: 14084

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

Upvotes: 0

Related Questions