insert into binary tree question..

This is a discussion on insert into binary tree question.. within the C Programming forums, part of the General Programming Boards category; i wrote a function called insert i want to build a binary tree like this Code: 2 / \ 1 ...

  1. #1
    Banned
    Join Date
    Oct 2008
    Posts
    1,535

    insert into binary tree question..

    i wrote a function called insert i want to build a binary tree like this

    Code:
        2
       / \
      1   10
         /
        5
    for that i wrote a function as i read in the tutorials
    i cant see where is my mistake in that function
    Code:
    #include <stdio.h>
    
    typedef struct node{
      struct  node *left;
       struct node *right;
        int data;
    
    }node;
    node  insert (node *root,int data);
    
    int main(){
    
    node * root;
    root=insert(root,2);
    root=insert(root,1);
    root=insert(root,10);
    root=insert(root,5);
        return 0;
    }
    
    node  * insert (node *root,int data){
     if (!root){
         root=malloc(node);
         root->data=data;
         return root;
     }//end if
    
     else{
         if (data=<root->data){ //start if check
             return insert(root->left,data);
         }//end if check
         else {
             return insert(root->left,data);
         }
    
     }//end else
    }//end insert

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    You may want to set root to NULL when you declare the variable.

    Also, as you insert, you may want to set the left/right pointers to NULL.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #3
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    1. Code:
      node * root  = NULL;
    2. Code:
      data=<root->data
      doesn't mean anything. Presumably you don't want the equal sign.
    3. You need to make sure that in your left/right cases that you set the link -- you don't want to return the inserted thing, you want to set root->left to the value of the inserted thing. Then after that you need to return root.

  4. #4
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    regarding the second one:
    Code:
    data=<root->data
    the data on the left side is a parameter in the input of the insert function.
    the data on the right side is the data inside the node.
    so its comparing the data in the root with the data parameter and inserts it to the left
    if its smaller or equals
    and to the right if the data parameter is bigger then the data in the root

    so in the end i add the line
    return root;

    is that ok?
    Code:
    #include <stdio.h>
    
    typedef struct node{
      struct  node *left;
       struct node *right;
        int data;
    
    }node;
    node  insert (node *root,int data);
    
    int main(){
    
    node * root=NULL;
    root=insert(root,2);
    root=insert(root,1);
    root=insert(root,10);
    root=insert(root,5);
        return 0;
    }
    
    node  * insert (node *root,int data){
     if (!root){
         root=malloc(node);
         root->data=data;
         return root;
     }//end if
    
     else{
         if (data=<root->data){ //start if check
             return insert(root->left,data);
         }//end if check
         else {
             return insert(root->left,data);
         }
    
     }//end else
    
    return root;  //always return the root of the tree
    }//end insert
    Last edited by transgalactic2; 11-17-2008 at 01:48 PM.

  5. #5
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,705
    >> root=malloc(node);

    That doesn't even compile. Pay attention to your compiler errors.
    Code:
    #include <cmath>
    #include <complex>
    bool flip(bool value)
    {
           return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) * std::complex<float>(std::atan(1.0)*(1 << (value + 2)))
        ).real() < 0;
    }

  6. #6
    Guest Sebastiani's Avatar
    Join Date
    Aug 2001
    Location
    Waterloo, Texas
    Posts
    5,705
    >> so its comparing the data in the root with the data parameter

    Reread tabstops post. It's *NOT* valid C.

    >> is that ok?

    If you're not even going to listen to the advise posted, then why bother?
    Code:
    #include <cmath>
    #include <complex>
    bool flip(bool value)
    {
           return std::pow
        (
            std::complex<float>(std::exp(1.0)), 
            std::complex<float>(0, 1) * std::complex<float>(std::atan(1.0)*(1 << (value + 2)))
        ).real() < 0;
    }

  7. #7
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by transgalactic2 View Post
    regarding the second one:
    Code:
    data=<root->data
    the data on the left side is a parameter in the input of the insert function.
    the data on the right side is the data inside the node.
    so its comparing the data in the root with the data parameter and inserts it to the left
    if its smaller or equals
    and to the right if the data parameter is bigger then the data in the root
    If you think =< means anything in C, there's nothing I can do for you. Look up your comparison operators again.
    Quote Originally Posted by transgalactic2 View Post
    so in the end i add the line
    return root;

    is that ok?
    If you had fixed the other stuff, yes. Since you didn't, not quite.
    Quote Originally Posted by transgalactic2 View Post
    Code:
    #include <stdio.h>
    
    typedef struct node{
      struct  node *left;
       struct node *right;
        int data;
    
    }node;
    node  insert (node *root,int data);
    
    int main(){
    
    node * root=NULL;
    root=insert(root,2);
    root=insert(root,1);
    root=insert(root,10);
    root=insert(root,5);
        return 0;
    }
    
    node  * insert (node *root,int data){
     if (!root){
         root=malloc(node); 
         root->data=data;
         return root;
     }//end if  /*Other people have told you how to fix this. */
    
     else{
         if (data=<root->data){ //start if check
             return insert(root->left,data); /*You cannot RETURN here; you must set the link here*/
         }//end if check
         else {
             return insert(root->left,data);  /* ditto */
         }
    
     }//end else
    
    return root;  //always return the root of the tree
    }//end insert

  8. #8
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    why this line is not correct?
    i assign space into the empty node.

    Code:
    root=malloc(node);

  9. #9
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    malloc does not take a type -- it takes a number of bytes. You must not give it a type; you must give it a number of bytes.

    If nothing else, do a board search on malloc and look at the 17304 (approximately) examples of it being correctly used.

  10. #10
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    ahhh like this

    Code:
    root=malloc(sizeof(node));

  11. #11
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    regarding this error:

    Code:
    return insert(root->left,data); /*You cannot RETURN here; you must set the link here*/
    i send the data to the left side of the tree
    we need to return a linked node
    and thats what the function does in the end
    where am i mistaken?
    Code:
    #include <stdio.h>
    
    typedef struct node{
      struct  node *left;
       struct node *right;
        int data;
    
    }node;
    node  insert (node *root,int data);
    
    int main(){
    
    node * root=NULL;
    root=insert(root,2);
    root=insert(root,1);
    root=insert(root,10);
    root=insert(root,5);
        return 0;
    }
    
    node  * insert (node root,int data){
     if (!root){
         root=malloc(sizeof(node));
         root->data=data;
         
     }//end if
    
     else{
         if (data<=root->data){ //start if check
             return insert(root->left,data);
         }//end if check
         else {
             return insert(root->right,data);
         }
    
     }//end else
    return *root;
    }//end insert
    Last edited by transgalactic2; 11-17-2008 at 02:17 PM.

  12. #12
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    i did the linking you said
    i think you meant that

    it still doesnt work

    Code:
    #include <stdio.h>
    
    typedef struct node{
      struct  node *left;
       struct node *right;
        int data;
    
    }node;
    node  insert (node *root,int data);
    
    int main(){
    
    node * root=NULL;
    root=insert(root,2);
    root=insert(root,1);
    root=insert(root,10);
    root=insert(root,5);
        return 0;
    }
    
    node  * insert (node root,int data){
     if (!root){
         root=malloc(sizeof(node));
         root->data=data;
    
     }//end if
    
     else{
         if (data<=root->data){ //start if check
             return root->left=insert(root->left,data);
         }//end if check
         else {
             return root->right=insert(root->right,data);
         }
    
     }//end else
          return *root;
    }//end insert
    Last edited by transgalactic2; 11-17-2008 at 02:23 PM.

  13. #13
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    You absolutely can't return *root at the end of the code.

    I'm sure you should return the root node at all times when you return from the function.

    You still need to set the new node's left/right pointers to NULL when you add a node, and when you have added the node, the left or right node of the node where you added the new node needs to be modified.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  14. #14
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,799
    #1. Mismatch in return type of function and first function argument in declaration/definition:
    Code:
    node  insert (node *root,int data);
    
    node  * insert (node root,int data){
       ...
    }
    That a typo?

    #2. Already mentioned by matsp, but you need to set the left/right pointers to NULL after you malloc the memory:
    Code:
     if (!root){
        root=malloc(sizeof(node));
        root->data=data;
        root->left = NULL;
        root->right = NULL;
     }
    #3. Setting of the current root's left/right pointers to the returned value of the recursive calls.
    Code:
    else{
         if (data <= root->data){
             root->left = insert(root->left,data);
         }
         else {
             root->right = insert(root->right,data);
         }
    
     }
    #4. Bad return type (don't need that *).
    Code:
    return *root;
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  15. #15
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Why do you insist on using the word return there? You do not want to return (you're going to return root -- not *root! -- later), so don't return.

Page 1 of 3 123 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. arrays vs lists? And containers in general!
    By clegs in forum C++ Programming
    Replies: 22
    Last Post: 12-03-2007, 01:02 PM
  2. Binary Tree
    By Ideswa in forum C Programming
    Replies: 12
    Last Post: 10-25-2007, 12:24 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. binary search tree help
    By noob2c in forum C++ Programming
    Replies: 6
    Last Post: 11-09-2003, 01:51 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21