Thread: 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;
}

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;
}

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.