Tree structure with problem in insertion function

I tried to implement a binary tree. My problem is that appear an error at the insertion function.

The insertion function which i used:

void insert_tree(TREE *tree,int x)
{
     NODE *p=(NODE *)malloc(sizeof(NODE));
     
     if(tree->root==NULL)
          {
          p=tree->root;
          p->data=x;
          p->left=NULL;
          p->right=NULL;
          }
     else
         {
          if((x < p->data)&&(p->left==NULL));
              {
                p->left=insert_node_tree(p->left,x);
              }  
          else
              {
                  // root->right=insert_node_tree(root->right,x);
              }      
    (tree->size)++;  
}

Open in new window


error appear at line
p->left=insert_node_tree(p->left,x);

Open in new window




What is going wrong ?
Tom3333Asked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Julian HansenCommented:
if((x < p->data)&&(p->left==NULL));
              {
                p->left=insert_node_tree(p->left,x);
              }  

Look at the above code - you are checking if p->left is NULL and if it is you are passing it to insert_node_tree
So tree is coming in with a NULL pointer.

Then here you have

     if(tree->root==NULL)
          {
          p=tree->root;
          p->data=x;
          p->left=NULL;
          p->right=NULL;
          }

What if tree is null

Should be
     if(treet==NULL)
          {
/*          p=tree->root; REMOVE THIS */
          p->data=x;
          p->left=NULL;
          p->right=NULL;
          tree = p; // ADD THIS
          }
0
sarabandeCommented:
if((x < p->data)&&(p->left==NULL));

Open in new window


the if statement ends with a semicolon ;

because of that the next block was entered without any condition.

Sara
0
Tom3333Author Commented:
sarabande you are right i remove the semicolon but the problem is stil exist.

julianH i tried your suggestion but without success.

when i tried the code
void insert_node_tree(TREE *tree,int x)
{
      NODE *p=(NODE *)malloc(sizeof(NODE));
       if(tree==NULL)
          {
         // p=tree->root; REMOVE THIS 
          p->data=x;
          p->left=NULL;
          p->right=NULL;
          tree = p; // ADD THIS
             }
}

Open in new window


a problem appear at the line :
tree = p; // ADD THIS

Open in new window

with the message :
cannot convert `NODE*' to `TREE*' in assignment



My starting code (before i receive any suggestions  is) :
#include<stdio.h>
#include<stdlib.h>

typedef struct tnode
                {
                int data; 
                struct tnode *left;
                struct tnode *right;       
                }NODE;
typedef struct
        {
        NODE * root;
        int size;
        }TREE;

void initialization_tree(TREE *tree)
        {
        NODE *root=NULL;
        tree->size=0;
        }
void insert_node_tree(TREE *tree,int x)
{
     NODE *p=(NODE *)malloc(sizeof(NODE));
     
     if(tree->root==NULL)
          {
          p=tree->root;
          p->data=x;
          p->left=NULL;
          p->right=NULL;
          }
     else
         {
          if((x < p->data)&&(p->left==NULL))
              {
                p->left=insert_node_tree
                (p->left,x);
              }  
          else
              {
                  // root->right=insert_node_tree(root->right,x);
              }      
    (tree->size)++;  
}
}

int main()
{
    TREE tree;
    initialization_tree(&tree);
    insert_node_tree(&tree,12);
return 0;    
}

Open in new window

0
Amazon Web Services

Are you thinking about creating an Amazon Web Services account for your business? Not sure where to start? In this course you’ll get an overview of the history of AWS and take a tour of their user interface.

Julian HansenCommented:
Then you need to do this
tree->root = p; // ADD THIS
0
Tom3333Author Commented:
this is working :
tree->root = p; // ADD THIS

For the case in  which, we need to add a node at the left the following is not working, how to fix it ?

 else
          {
             if ((x < p->data)&&(p->left==NULL))
             {
             p->left=insert_node_tree(p->left,x);
             }

Open in new window


Error appear at the line :
 p->left=insert_node_tree(p->left,x);

Open in new window


with the message :
cannot convert `tnode*' to `TREE*' for argument `1' to `void insert_node_tree(TREE*, int)'
0
Tom3333Author Commented:
any suggestions what is going wrong ?
0
sarabandeCommented:
you try to pass a NODE* where a TREE* is required.

note, a NODE has pointers to left and right child NODE and a member for the data. a TREE has a pointer to root NODE and a size member (what helps to fast give back the number of tree nodes).

both structures have a valid meaning and though the TREE structure in C could be replaced by NODE with little disadvantages, you better support both the TREE and the NODE.

however, that requires to insert functions:

int tree_insert(TREE * tree, int data);

NODE * treenode_insert(NODE *, int data);

in the first function tree_insert you create a new root node if the TREE is empty assign the data and return tree->size = 1. if not empty you call the second function after you determined whether the left or the right child NODE needs to be passed.

Sara
0
sarabandeCommented:
should be "two" insert functions.

Sara
0
Julian HansenCommented:
You only need one function

there should be only one tree structure per  tree you are managing.

Your tree should be created outside of the insert and the

tree->root should be passed to the insert function i.e

insert_node_tree(tree->root,12);

Open in new window


And change your insert to

void insert_node_tree(NODE *tree,int x)
{

Open in new window

0
sarabandeCommented:
there should be only one tree structure per  tree you are managing.
tree->root should be passed to the insert function i.e
insert_node_tree(tree->root,12);
void insert_node_tree(NODE *tree,int x)
julianH, you don't seem to see that your recommendations and the code you supply are in contradiction. 'root' is not a member of NODE but of TREE. so, your advice will not help but confuse.

Tom, it is a good idea to have a TREE structure additional to a NODE, even if each NODE would be the root of a new subtree. but such subtrees are more important for internal purposes in tree management rather than for a practical use in your program when using the tree as container.

Sara
0
Julian HansenCommented:
that your recommendations and the code you supply are in contradiction.
No they are not.

Root is a member of Tree - that is why you pass that to the insert function

The only confusion (And this is a carry over from the original code) is the naming of the variable.

void insert_node(NODE * tree, int x)

This can be changed to

void insert_node(NODE * subtree, int x)

So you create a tree

TREE * tree;

Now we initialise the tree

initialization_tree(&tree)

Now we want to insert something so we pass the root (NODE) of the tree struct to the insert

insert_node_tree(tree->root,12);

In the insert_node - we receive a node (which was called tree - due to legacy and the fact that to change the name of the param would mean modifying the rest of insert).

There is much wrong with this code - the idea is to help the author find the problems himself - having said that - here is a corrected insert function

void insert_node_tree(NODE *subtree,int x)
{
     NODE *p=(NODE *)malloc(sizeof(NODE));
     
     if(subtree==NULL) {
          p->data=x;
          p->left=NULL;
          p->right=NULL;
          subtree = p;
     }
     else {
          if(x < p->data)  {
                insert_node_tree(p->left,x);
          }  
          else {
                 insert_node_tree(p->right,x);
          }      
         (subtree->size)++;
     }
}

Open in new window

0
sarabandeCommented:
julianH, the confusing thing is that you speak of using only one structure but have samples that were using two structures TREE and NODE. also it is confusing that you still were naming a node with "subtree" though it is better than naming it tree. even if C isn't an object-oriented programming language, it is good practice to not naming variables or arguments wrongly. in your code the NODE* argument can be NULL, it can be a "leaf" node, where both the left and right members are NULL, it can be a degenerated tree node where only one of left and right is not NULL and it can be a root node of a subtree. only for the last case it would make sense to name the argument 'subtree'.

the next problem is that you were posting full code without knowing whether it is homework or not.

the last issue is that your code is not correct. when subtree is NULL you assign new p to it. but subtree is a local copy of the variable passed from caller. it is only valid in the insert function. so the calling function would not get the p returned. in C you would need to make the argument a pointer to NODE* to handle it the way you posted. but it would be much easier to handle the case in the insert function and avoid passing a NULL node to the function.

here we have advantages if using two insert functions:

void insert_to_tree(TREE * tree, int data)
{
     if (tree == NULL)
         ...  // don't accept a NULL tree

     if (tree->root == NULL)
     {
          // create a new root NODE and assign data member
          ...
     }
     else 
     {
             insert_to _node(tree->root, data);
             ...

void insert_to_node(NODE * node, int data)
{
      if (node == NULL) 
      {
            // may not happen: error
            ...
      }
      if (data < node->data)
      {
          if (node->left == NULL)
          {
                // create a new left node and assign data
                ...
          }
          // recursive call passing a valid node 
          insert_to_node(node->left, data);
      }
      else 
      {
          // handling for right sub node accordingly
          ...

Open in new window


the above code may have some redundancies (which could be reduced in a further step) but handles all cases and is less error-prone.

Sara
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
mlmccCommented:
I've requested that this question be closed as follows:

Accepted answer: 25 points for sarabande's comment #a39514429
Assisted answer: 25 points for julianH's comment #a39514306

for the following reason:

This question has been classified as abandoned and is closed as part of the Cleanup Program. See the recommendation for more details.
0
sarabandeCommented:
julianH's comment #a39514306 should not be an assisted solution as the code posted in the comment contains wrong code (as explained in the following comment). you may use #a39508205 of julianH instead which rightly pointed to one of multiple errors in the author's code.

Sara
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
C

From novice to tech pro — start learning today.