Binary Tree insert Func

This is a discussion on Binary Tree insert Func within the C Programming forums, part of the General Programming Boards category; I am having trouble writing an insert function for a binary tree. Here is the structure that I have to ...

  1. #1
    Registered User
    Join Date
    Mar 2014
    Posts
    12

    Binary Tree insert Func



    I am having trouble writing an insert function for a binary tree.

    Here is the structure that I have to use.

    I have the print function done, the insert function is the one I am having trouble with, thanks a lot.


    Code:
    typedef struct bt_{ 
    int value; 
    struct bt_ *right; 
    struct bt_ *left; 
    }BST; 
    
    
    
    
    
    BST* insert(BST* root, int value); 
    /*This function will insert a new node with a value of value in BST. Remember, in this program a binary tree is defined either being null or it is a node whose left subtree is filled with nodes whose values are less than its own, and a right subtree whose right subtree is filled with nodes whose values are greater than or equal to its own. Although not required, it is recommended that you try and implement this function recursively. */ 
    
    
    void printTree(BST* root) 
    { 
    displayBST(root, 0); 
    } 
    
    void displayBST(BST* root, int depth) 
    { 
    if (root == NULL) 
    { 
    padding(' ', depth); 
    printf("-\n"); 
    return; 
    } 
    
    displayBST(root->left, depth+4); 
    padding(' ', depth); 
    printf("%d\n", root->value); 
    displayBST(root->right, depth+4); 
    } 
    
    void padding(char toPrint, int numTimes) 
    { 
    int i; 
    for (i = 0; i < numTimes; i++) 
    printf("%c", toPrint); 
    }

    Thanks for your help!



  2. #2
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,498
    So, you know how to apply recursion to an in-order traversal to print the tree, by treating the left and right sub-trees as effectively just a smaller binary tree. Can you apply that concept to inserting a node/value? If the node is smaller than the root of this subtree, what might you do? What if it's bigger? What if it's equal? What if root is null?

    I'm having a hard time figuring out how to give help without just giving away the answer. See if you can at least post some attempt in pseudo code or actual code with your attempt, and we can guide you from there.

  3. #3
    Registered User
    Join Date
    Mar 2014
    Posts
    12
    Quote Originally Posted by anduril462 View Post
    So, you know how to apply recursion to an in-order traversal to print the tree, by treating the left and right sub-trees as effectively just a smaller binary tree. Can you apply that concept to inserting a node/value? If the node is smaller than the root of this subtree, what might you do? What if it's bigger? What if it's equal? What if root is null?

    I'm having a hard time figuring out how to give help without just giving away the answer. See if you can at least post some attempt in pseudo code or actual code with your attempt, and we can guide you from there.

    Here is my attempt:
    Code:
    BST * insert( BST * root, int value ) { 
        if ( root != 0 ) { 
            if ( value < root->value ) 
                root->left= insert( root->left, value ); 
            else if ( value > root->value ) 
                root->right= insert( root->right, value ); 
            return root; 
        } 
        BST *n= (BST *) malloc( sizeof( BST ) ); 
        n->value= value; 
        n->left= n->right= 0; 
        return n; 
    } 
    

  4. #4
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,498
    That looks about right. Test it. If it gives you trouble, post back here with the input you used that failed and a description of the problem.

  5. #5
    Registered User
    Join Date
    Mar 2014
    Posts
    12
    Quote Originally Posted by anduril462 View Post
    That looks about right. Test it. If it gives you trouble, post back here with the input you used that failed and a description of the problem.

    Here are the errors

    prel.c: In function ‘displayBST’:
    prel.c:53: warning: passing argument 1 of ‘padding’ makes integer from pointer without a cast
    prel.c:13: note: expected ‘char’ but argument is of type ‘char *’
    prel.c:58: warning: passing argument 1 of ‘padding’ makes integer from pointer without a cast
    prel.c:13: note: expected ‘char’ but argument is of type ‘char *’


    Here is my code:

    Code:
    #include <stdio.h>
    #include<stdlib.h>
    
    
    typedef struct bt_{
            int value;
            struct bt_ *right;
            struct bt_ *left;
    }BST;
    
    
    BST* insert(BST* root, int value);
    void printTree(BST* root);
    void displayBST(BST* root, int depth);
    void padding(char toPrint, int numTimes);
    
    
    int main(){
    
    
            int value;
            BST *new_BST;
    
    
            while(value != -1){
                    printf("\nEnter a number to put into the tree");
                    scanf("%d", &value);
    
    
                    new_BST = insert(new_BST, value);
            }
    
    
            printTree(new_BST);
    }
    
    
    BST* insert(BST* root, int value){
            if(root != 0){
                    if(value < root->value)
                            root->left = insert(root->left, value);
                    else if( value > root->value)
                            root->right = insert(root->right, value);
                    return root;
            }
            BST *n = (BST*) malloc(sizeof(BST));
            n->value = value;
            n->left = n->right = 0;
            return n;
    }
    
    
    void printTree(BST* root)
    {
            displayBST(root,0);
    
    void displayBST(BST* root, int depth){
    
    
            if(root==NULL)
            {
                    padding("''", depth);
                    printf("-\n");
                    return;
            }
            displayBST(root->left,depth+4);
            padding("'' ", depth);
            printf("%d\n", root->value);
            displayBST(root->right, depth+4);
            }
    void padding(char toPrint, int numTimes)
    {
            int i;
            for(i=0; i < numTimes; i++)
                    printf("%c", toPrint);
    }



    thanks

  6. #6
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,498
    What you used to have that worked
    Code:
    padding(' ', depth);
    What you now have, that doesn't work
    Code:
    padding("'' ", depth);

  7. #7
    Registered User
    Join Date
    Mar 2014
    Posts
    12
    Quote Originally Posted by anduril462 View Post
    What you used to have that worked
    Code:
    padding(' ', depth);
    What you now have, that doesn't work
    Code:
    padding("'' ", depth);

    okay thanks it works now. How would I go about searching the list? and maybe deleting a number in the list? Thanks a lot lol.

  8. #8
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,498
    Well, searching is easy, because of the structure and organization of the binary tree.

    As for deleting, well, there's a nice Wikipedia article that talks about binary trees and the various operations on them. I would hate to rob you of the wonderful learning experience by just telling you how to do it .

  9. #9
    Registered User
    Join Date
    Mar 2014
    Posts
    12
    Quote Originally Posted by anduril462 View Post
    Well, searching is easy, because of the structure and organization of the binary tree.

    As for deleting, well, there's a nice Wikipedia article that talks about binary trees and the various operations on them. I would hate to rob you of the wonderful learning experience by just telling you how to do it .

    I know, but it would be sweet if you could help me out just this once, if not its cool thanks for everything

  10. #10
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,498
    Quote Originally Posted by nslice22 View Post
    I know, but it would be sweet if you could help me out just this once, if not its cool thanks for everything
    Giving you the solution would be the exact opposite of sweet, and it would do the exact opposite of helping you out.

    1. It would violate the forum's homework policy. I know you know that, since you agreed to having read the forum rules and to abiding by them, as a requirement to signing up for your account.
    2. It would violate my personal ethics.
    3. It would encourage you to try this tactic again, either with me or somebody else, since it worked once.
    4. It would encourage you to try this tactic again, because you never learned the fundamentals, so you can't do the advanced work yourself, even if you wanted to.
    5. Helping you cheat your way to a degree you don't deserve means you might get a job you don't deserve and aren't qualified for. I don't want to do anything to increase the number of incompetent people that work in the programming industry. One way or another, it will make my life more difficult, whether I rely on them as employees, they make a product I use, etc.
    6. The mere fact that you asked does not reflect well on your character.

    Yep, I'm a giant a-hole when it comes to academic honesty and ethics. Other than that, I'm a pretty nice guy. If you make a real attempt and post back with real questions, you'll get real help instead of snark.

    Seriously though, the search is super easy. Think about how you find a node. Draw a tree on paper and do the lookup by hand. The delete is trickier but still isn't that hard, once you take a little time to study it. Again, draw a few examples out on paper and work through them by hand. I told you in your Linked List thread to work out a solution by hand -- that goes for all your programming problems. I can not stress this enough: if you can't solve the problem yourself, you can't program a computer to solve it.

  11. #11
    Registered User
    Join Date
    Mar 2014
    Posts
    12
    Quote Originally Posted by anduril462 View Post
    Giving you the solution would be the exact opposite of sweet, and it would do the exact opposite of helping you out.

    1. It would violate the forum's homework policy. I know you know that, since you agreed to having read the forum rules and to abiding by them, as a requirement to signing up for your account.
    2. It would violate my personal ethics.
    3. It would encourage you to try this tactic again, either with me or somebody else, since it worked once.
    4. It would encourage you to try this tactic again, because you never learned the fundamentals, so you can't do the advanced work yourself, even if you wanted to.
    5. Helping you cheat your way to a degree you don't deserve means you might get a job you don't deserve and aren't qualified for. I don't want to do anything to increase the number of incompetent people that work in the programming industry. One way or another, it will make my life more difficult, whether I rely on them as employees, they make a product I use, etc.
    6. The mere fact that you asked does not reflect well on your character.

    Yep, I'm a giant a-hole when it comes to academic honesty and ethics. Other than that, I'm a pretty nice guy. If you make a real attempt and post back with real questions, you'll get real help instead of snark.

    Seriously though, the search is super easy. Think about how you find a node. Draw a tree on paper and do the lookup by hand. The delete is trickier but still isn't that hard, once you take a little time to study it. Again, draw a few examples out on paper and work through them by hand. I told you in your Linked List thread to work out a solution by hand -- that goes for all your programming problems. I can not stress this enough: if you can't solve the problem yourself, you can't program a computer to solve it.
    Thanks a lot

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Search Tree Insert
    By bleuz in forum C++ Programming
    Replies: 5
    Last Post: 04-30-2010, 09:53 AM
  2. Help with insert/delete binary search tree
    By Nazgulled in forum C Programming
    Replies: 39
    Last Post: 03-25-2009, 04:24 PM
  3. insert into binary tree question..
    By transgalactic2 in forum C Programming
    Replies: 32
    Last Post: 11-18-2008, 02:21 PM
  4. Insert elements in binary tree
    By lastrial in forum C Programming
    Replies: 3
    Last Post: 05-23-2007, 10:22 AM
  5. Binary Tree Insert & Find
    By Micko in forum C++ Programming
    Replies: 4
    Last Post: 04-11-2004, 01:18 PM

Tags for this Thread


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