Inserting Nodes at Binary Trees

This is a discussion on Inserting Nodes at Binary Trees within the C++ Programming forums, part of the General Programming Boards category; Ok i'll try to be brief. As part of one of my essays i thought of creating source code for ...

  1. #1
    Registered User
    Join Date
    Dec 2007
    Posts
    1

    Inserting Nodes at Binary Trees

    Ok i'll try to be brief. As part of one of my essays i thought of creating source code for implementation of a binary tree and its basic functions.

    My code is both from books,lecture notes and googling but for some reason on the printing of the nodes using inOrder traversal only 2 or 3 nodes are being printed.

    I will put my code here although i am sure that only few might actually comprehend what it is about because this subject needs good knowledge of all the tricks about inserting/deleting nodes from theory of Binary Trees.


    Exercise: Create code for a binary tree.The program reads the size of the tree N and then inserts N nodes with values between 1 and 30.000 into the tree.
    You cant enter a node if it is not already on the tree,so you must search if it exists before entering it.

    Finally ,after having inserted all N nodes print them using InOrder traversal.


    Tips: My code works for the first 2 nodes...but doesnt print anything else.And i will bust my head open if i wont figure out why.

    I appreciate any help guys , this is a tough question and this is my first time on this forum.
    (seems very warm so far btw)








    Code:
    #include <iostream>
    #include <cstdlib>
    #include <ctime>
    
    using namespace std;
    
    //the struct which represents the node
    struct tnode {
           struct tnode *left, *right;
           int key;
    };
    
    
    void InOrder( tnode *x )
    {
           if (x == 0) return;
           InOrder(x->left);
           cout << x->key << " ";
           InOrder(x->right);
    }
    
    
    int main ()
    {
           srand((long)2004126);
           tnode *root = 0;
           int size, key2;
           int flag;
    
           cout << "\nPlease enter the size of the tree.  N: ";
           cin >> size;
    
           for (int i = 0; i < size; i++) {
                   key2 = 1 + rand() &#37; 30000;  //creating random node key between 1-30.000
                   tnode *p = root;
                   tnode *q = 0 ;
                   flag = 0;
    
              //searching existing tree for node with that value
    
                   while((p != 0)&&(flag==0)) {
                           q = p;
                           if (p->key == key2) {
                                   flag = 1; //node with that key already exists -cant enter
                           } else if (p->key < key2) {
                                   p = p->left; //case 1: key smaller than root
                           } else {
                                   p = p->right; //case 2: key bigger than root
                           }
                   }
                  
    
                     //creating new node with key2 as content
                   if (flag == 0) { //flag is 0 when that value didnt already exist on the tree
                           tnode *z = new tnode;
                           z->key = key2;
                           z->left = 0;
                           z->right = 0;    //creation of nw node that will take key2 as its value
                                  //and will have 2 NULL kids (left and right)
    
                           if (q == 0) {
                                   root = z;
                           //case of empty tree
                           //case handling about where the new node will be put
                           } else if (key2 > q->key) {
                                   q->right = z;
                           } else {
                                   q->left = z;
                           }
                   }
           }
    
           //cout << "\nroot is : "<< root->key;          //not needed ,just for checking 
                                                                              //the value of root
           InOrder(root);
           cout << endl;
           cin >> size;
           return 0;
    }

  2. #2
    Registered User
    Join Date
    Mar 2005
    Location
    Mountaintop, Pa
    Posts
    1,058
    Code:
    #include <iostream>
    #include <cstdlib>
    #include <ctime>
    
    using namespace std;
    
    //the struct which represents the node
    struct tnode {
        struct tnode *left, *right;
        int key;
    };
    
    tnode *insertleft(tnode *tree,int ele)
    {
        if(tree==NULL)
        {
            tree=new tnode;
            tree->left=tree->right=NULL;
            tree->key=ele;
        }
        else
            tree->left=insertleft(tree->left,ele);
        return(tree);
    }
    
    tnode *insertright(tnode *tree,int ele)
    {
        if(tree==NULL)
        {
            tree=new tnode;
            tree->left=tree->right=NULL;
            tree->key=ele;
        }
        else
            tree->right=insertright(tree->right,ele);
        return(tree);
    }
    
    void InOrder( tnode *x )
    {
        if (x == 0) return;
        InOrder(x->left);
        cout << x->key << " ";
        InOrder(x->right);
    }
    
    int main (void )
    {
        srand((long)2004126);
        tnode *root = 0;
        int size, key2;
        int flag;
    
        cout << "\nPlease enter the size of the tree.  N: ";
        cin >> size;
    
        for (int i = 0; i < size; i++) {
            key2 = 1 + rand() % 30000;  //creating random node key between 1-30.000
            tnode *p = root;
            tnode *q = 0;
            flag = 0;
    
            //searching existing tree for node with that value
            while((p != 0)&&(flag==0)) {
                q = p;
                if (p->key == key2) {
                    flag = 1; //node with that key already exists -cant enter
                } 
                else if (p->key < key2) {
                    p = p->left; //case 1: key smaller than root
                } 
                else {
                    p = p->right; //case 2: key bigger than root
                }
            }
    
            //creating new node with key2 as content
            if (flag == 0) 
            { //flag is 0 when that value didnt already exist on the tree
                if (q == 0) {
                    root =new tnode;
                    root->left=root->right=NULL;
                    root->key=key2;
                    //case of empty tree
                    //case handling about where the new node will be put
                } 
                else if (key2 > q->key) {
                    root = insertright(root,key2);
                } 
                else {
                    root = insertleft(root,key2);
                }
            }
        }
        //cout << "\nroot is : "<< root->key;          //not needed ,just for checking 
        //the value of root
        InOrder(root);
        cout << endl;
        cin >> size;
        return 0;
    }

  3. #3
    Chinese pâté foxman's Avatar
    Join Date
    Jul 2007
    Location
    Canada
    Posts
    404
    First of all, here you are in the C section, not the C++ one (next time, think about it ). But since your code is mostly C with the bad things who comes with C++ (like being able to declare variable anywhere), well, here's why your program wasn't working.

    It's because of a rather small error. Don't have nothing to do with how you were adding a new node. The error is:

    Code:
    while((p != 0)&&(flag==0)) {
                q = p;
                if (p->key == key2) {
                    flag = 1; //node with that key already exists -cant enter
                } 
                else if (p->key < key2) {
                    p = p->left; //case 1: key smaller than root
                } 
                else {
                    p = p->right; //case 2: key bigger than root
                }
            }
    where it should be

    Code:
    while((p != 0)&&(flag==0)) {
                q = p;
                if (p->key == key2) {
                        flag = 1; //node with that key already exists -cant enter
                } else if (key2 < p->key) {
                        p = p->left; //case 1: key smaller than root
                } else {
                        p = p->right; //case 2: key bigger than root
                }
        }
    Everything else looks fine.

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    23,639
    First of all, here you are in the C section, not the C++ one (next time, think about it ).
    Good point. I have moved this thread to the C++ Programming board.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary tree not inserting nodes correctly
    By jk1998 in forum C++ Programming
    Replies: 7
    Last Post: 09-22-2007, 12:37 PM
  2. A Binary Search Tree of... Binary Search Trees...
    By SlyMaelstrom in forum C++ Programming
    Replies: 5
    Last Post: 12-10-2005, 01:12 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. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 08:40 PM
  5. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM

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