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)

#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() % 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;
}

Try this..! Your code had one logical error. Can you tell me what was that ? :)

#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() % 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;
}

Problem solved.

Line 46 is > not <

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.