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,059
    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
    21,727
    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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    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