Urgent Help in Binary Search Trees..

Question

Mehwish Shaikh 0 Light Poster

16 Years Ago

Hello and hii fellows....
I want your help right now in making a BST in which we can perform treeSearch....treeMINIMUM....treeMAXIMUM....treeINSERT....treeSUCCESSOR....treePREDECESSOR....treeDELETE....alongwith INORDER....POSTORDER....PREORDER traversal methods....
I have made a program consistiting of all methods excluding treeDELETE....
I'm ordered to make a tree-class....and a structure for node of a tree....
but im confused how to use those methods in MAIN() function after making Objects of Class-tree....Im a very primary-level programmer....so i don't use different functions for printing or whatever....i hope you'll get it from my code..
Code is:

#include <iostream.h>
#include <conio.h>
#define NULL 0

struct node
{
	node* parent;
	node* left;
	node* right;
	int key;
};

class BST
{
	private:

		node* root;
		node array[10];

	public:
		
		BST(int data)	//Constructor
		{
			COUT<<"\n Enter element to insert in the tree: \n";
			cin>>data;
			InsertTree(root,data);
			cout<<endl;
		}

		void INSERTTree(node* i,int k); //Functions declarations
		void PreOT(node* i);
		void IOT(node* i);
		void POT(node* i);
                                int SEARCHtree(node* i, int k);
		int MINtree(node * i);
		int MAXtree(node * i);
                                void DELETETree(node* i,int k);
		int treeSuccessor(node * i);
		int treePredecessor(node * i);
}; //end class

void BST::INSERTTree(node* i, int k)
{
	if(i->key==NULL)
	{
		i->key = k;
		i->left = NULL:
		i->right = NULL;
	}
	
	else if(k < i->key)	//If element is smaller than node
	{
		INSERTTree(i->left, k);
	}

	else if(k >= i->key)
	{
		INSERTTree(i->right, k);
	}

}	

void BST::PreOT(node* i)            
{
		if(i != NULL)
		{
			cout<<(i->key)<< endl;
			PreOT(i->left);
			PreOT(i->right);
		}
}


void BST::IOT(node* i)
{
		if(i != NULL)
		{

			IOT(i->left);
			cout<< (i->key)<< endl;
			IOT(i->right);
		}
}

void BST::POT(node * i)
{
		if(i != NULL)
		{
			POT(i->left);
			POT(i->right);
			cout<<(i->key)<< endl;
		}
}


int BST::SEARCHtree(node* i, int k)
{
	if(i==NULL)
	{
		return 0;
	}
		
	else if(k == i->key)
	{
		return(i->key);
	}
	
	else if(k < i->key)
	{
		return TreeSearch(i->left, k);
	}
	
	else(k >= i->key)
	{
		return TreeSearch(i->right, k);
	}
}


int BST::MINtree(node * i)
{
	while(i->left != NULL)
	{
		i=i->left;
	}
	return (i->key);
}

int BST::MAXtree(node * i)
{
	while(i->right !=NULL)
	{	
		i=i->right;
	}
	return (i->key);
}	

int BST::treeSuccessor(node * i)
{
	if(i->right != NULL)
	{
		return TreeMin(i->right);
	}
	node * y= i->parent;
	while(y != NULL <> i= y->right);
	{
		i=y;
		y=y->parent;
	}
	return (y->key);
}

int BST::treePredecessor(node * i)
{
	if(i->left != NULL)
	{
		return TreeMax(i->left);
	}

	node * y= i->parent;
	while(y != NULL <> i= y->left);
	{
		i=y;
		y=y->parent;
	}
	return (y->key);
}


int main()
{
	clrscr();
                BST t1;
                t1.POT(node* i)  //don't know how to call methods..
                getch();
	return 0;
}

I think i've made mistakes in functions too..I want to alsohave COUT for printing in INSERTTree method......i don't know what to do....i have just done..whatever my mind thought....
Seeking for your urgent help....but i hope you'll make alterations in this same above code..otherwise i might not be able to get the code
Thanks in advance....!!

c++

4 Contributors
16 Replies
326 Views
2 Days Discussion Span
Latest Post 16 Years Ago Latest Post by Nick Evan

Nick Evan 4,005 Industrious Poster

16 Years Ago

Please Be Hurry....
I'm looking forward for your kind help....

It may be urgent to you, but it isn't to us :)

but im confused how to use those methods in MAIN() function after making Objects of Class-tree.

You've forgotten to create a node that you send to the functions, so without looking through all of your code, I'd say your main should look something like this:

node n;
    BST t1;
    t1.POT(&n);

I want to alsohave COUT

It's cout (not in caps). C++ is case-sensitive....

You should know stuff like this if you're able to write a binary searchtree yourself.
The fact that you use clrscr(), getch and COUT, makes me suspect that you stole the code from somewhere....

Nick Evan 4,005 Industrious Poster

16 Years Ago

bt i want you to have a look on my program bcz its giving me so many errors..

You should learn to ask your questions in English, not leet. The shift-key is on your keyboard for a purpose...

I just write COUT for emphasizing purpose..

No it's also wrong in your code:

COUT<<"\n Enter element to insert in the tree: \n";

So did you change the things I mentioned? If yes: Post your new code here.

[edit]
Oh and clrscr() and getch() are outdated and non-standard. So my modern compiler will give an error if I would compile your code. So that's why it's bad to use them.

Are you using the Turbo compiler? If yes: upgrade to a compiler that isn't 15 years old, like the free VS2008

mitrmkar 1,056 Posting Virtuoso

16 Years Ago

its giving me so many errors....

Well, first of all, be consistent with the names of the member functions, for example

int BST::SEARCHtree(node* i, int k)
{
	if(i==NULL)
	{
		return 0;
	}
		
	else if(k == i->key)
	{
		return(i->key);
	}
	
	else if(k < i->key)
	{
		return TreeSearch(i->left, k);
	}
	
	else(k >= i->key)
	{
		return TreeSearch(i->right, k);
	}
}

Nick Evan 4,005 Industrious Poster

16 Years Ago

First of all: What mitrmkar said should solve a lot of your errors.

But more important:
you didn't write this code yourself, you probably found it somewhere on the net. If you want to understand how binarytrees work, click here and follow the tutorial.

Reply to this topic

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.

Mehwish Shaikh 0 Light Poster · Answer 1 · 2008-09-03T16:00:35+00:00

Please Be Hurry....
I'm looking forward for your kind help....

Mehwish Shaikh 0 Light Poster · Answer 2 · 2008-09-03T19:45:19+00:00

yeah definitely it isn't urgent to you....but the thing is that if you wan help me..then i'd need help in time na....

I just write COUT for emphasizing purpose..otherwise its a very bsic thing that c++ is case-sensitive....and whats wrong with using clrscr() and getch()....
bcz if i don't use both these terms in my programs..screen does'nt get freezed nor does it clean itself....is there nything bad while using them..??

Mehwish Shaikh 0 Light Poster · Answer 3 · 2008-09-03T19:47:13+00:00

well you told me the way to use it in main()....bt i want you to have a look on my program bcz its giving me so many errors....i'll be really thankful to you ifyou just copy paste it in your C++ and tell me how to solve those....
thanks for your time..

Mehwish Shaikh 0 Light Poster · Answer 4 · 2008-09-03T20:09:36+00:00

Well then this COUT in code is also just because of shift key present on my keyboard.

#include <iostream.h>
#include <conio.h>
#define NULL 0

struct node
{
	node* parent;
	node* left;
	node* right;
	int key;
};

class BST
{
	private:

		node* root;
		node array[10];

	public:
                          BST()   //Constructor
	         {
		int data;
		root==NULL;
	                cout<<"\n Enter element to insert in the tree: \n";
	               cin>>data;
	INSERTTree(root,data);
	cout<<endl;
}//constructor ends
void INSERTTree(node* i,int k); //Functions declarations
		void PreOT(node* i);
		void IOT(node* i);
		void POT(node* i);
                                int SEARCHtree(node* i, int k);
		int MINtree(node * i);
		int MAXtree(node * i);
                                void DELETETree(node* i,int k);
		int treeSuccessor(node * i);
		int treePredecessor(node * i);
}; //end class

void BST::INSERTTree(node* root, node* node)
{
node* y=NULL;
node* x =root;
while(x!=NULL)
{	do y=x
		if(node->key < x->key)
			x= x->left;
		else x = x->right;
}
node->parent = y;
if(y = NULL)
	root = node;
else if(node-> key < y->key)
                y->left = node;
else   
                 y->right=node;
} 
void BST::PreOT(node* i)            
{
		if(i != NULL)
		{
			cout<<(i->key)<< endl;
			PreOT(i->left);
			PreOT(i->right);
		}
}


void BST::IOT(node* i)
{
		if(i != NULL)
		{

			IOT(i->left);
			cout<< (i->key)<< endl;
			IOT(i->right);
		}
}

void BST::POT(node * i)
{
		if(i != NULL)
		{
			POT(i->left);
			POT(i->right);
			cout<<(i->key)<< endl;
		}
}

int BST::SEARCHtree(node* i, int k)
{
	if(i==NULL)
	{
		return 0;
	}
		
	else if(k == i->key)
	{
		return(i->key);
	}
	
	else if(k < i->key)
	{
		return TreeSearch(i->left, k);
	}
	
	else(k >= i->key)
	{
		return TreeSearch(i->right, k);
	}
}

int BST::MINtree(node * i)
{
	while(i->left != NULL)
	{
		i=i->left;
	}
	return (i->key);
}

int BST::MAXtree(node * i)
{
	while(i->right !=NULL)
	{	
		i=i->right;
	}
	return (i->key);
}	

int BST::treeSuccessor(node * i)
{
	if(i->right != NULL)
	{
		return TreeMin(i->right);
	}
	node * y= i->parent;
	while(y != NULL <> i= y->right);
	{
		i=y;
		y=y->parent;
	}
	return (y->key);
}

int BST::treePredecessor(node * i)
{
	if(i->left != NULL)
	{
		return TreeMax(i->left);
	}

	node * y= i->parent;
	while(y != NULL <> i= y->left);
	{
		i=y;
		y=y->parent;
	}
	return (y->key);
}

int main()
{
clrscr();
node n;
BSt t1;
t1.POT(&n);
t1.PreOT(&n);
t1.IOT(&n);
t1.SEARCHtree(&n, 10);
t1.SEARCHtree(&n, 25);
t1.treeSuccessor(&n);
t1.treePredecessor(&n);
getch();
return 0;
}

Mehwish Shaikh 0 Light Poster · Answer 5 · 2008-09-03T20:11:40+00:00

Yes, You're right.
Actually I have changed the code so many times, that now im just messing it out more..
Thanks for telling mitrmkar..

Mehwish Shaikh 0 Light Poster · Answer 6 · 2008-09-03T20:13:57+00:00

Niek_ Should I do
node n;
OR
node* n;
Secondly I've changed INSERTTree code..Have a look on it..but i also want to print the current values of tree.

Mehwish Shaikh 0 Light Poster · Answer 7 · 2008-09-03T20:16:32+00:00

Can I write the code like this in main() for printing the data..

cout<<t1.SEARCHtree(&n, 25)<<endl;
cout<<endl<<t1.treeSuccessor(&n);
cout<<endl<<t1.treePredecessor(&n);

Mehwish Shaikh 0 Light Poster · Answer 8 · 2008-09-04T15:56:31+00:00

Thanks alot niek_e....
That one really helped me alot....
but im still confused about something, s i don't know some basic points of C++..
Like whether to use ; after an if statement or not..and the stuff like this..:
I have made this program..which is error-free..

#include <iostream.h>
#include <conio.h>
#define NULL 0

struct node
{
	node* parent;
	node* left;
	node* right;
	int key;
};

class BST
{
	private:

	node* root;
	node array[3];

	public:

		BST()
		{
			root = &array[0];

			array[0].parent = NULL;
			array[0].left = &array[1];
			array[0].right = &array[2];
			array[0].key = 56;

			array[1].parent = &array[0];
			array[1].left = NULL;
			array[1].right =NULL;
			array[1].key = 50;

			array[2].parent = &array[0];
			array[2].left = NULL;
			array[2].right = NULL;
			array[2].key = 58;

			cout<< "Preorder Traverse:\n";
			PreOT(root);
			cout<< endl;
			cout<< "Inorder Traversing:  ";
			cout<<endl;
			IOT(root);
			cout<< endl;
			cout<< "\nPostorder Traverse:\n";
			POT(root);
			cout<< endl;
			cout<<"Minimum iteratively" <<endl;
			itreeMIN(root);
			cout<<endl;
			cout<<"\nMaximum iteratively" <<endl;
			itreeMAX(root);
			cout<<endl;
			cout<<"\nMinimum recursively" <<endl;
			rtreeMIN(root);
			cout<<endl;
			cout<<"\nMaximum recursively" <<endl;
			rtreeMAX(root);
			cout<<endl;
			cout<<"\nPredecessor is: "<<endl;
			treePREDECESSOR(root);
			cout<<endl;
			cout<<"\nSuccessor is: "<<endl;
			treeSUCCESSOR(root);
			cout<<endl;
			cout<<"\nSearching tree recursively: "<<endl;
			rTreeSearch(root, 40);
			cout<<endl;
			cout<<"\nSearching tree iteratively: "<<endl;
			iTreeSearch(root,50) ;
			cout<<endl;
		}
		void PreOT(node* i);
		void IOT(node* i);
		void POT(node* i);
		void itreeMIN(node* i);
		void rtreeMIN(node * i);
		void itreeMAX(node* i);
                                void rTreeSearch(node* i, int k);
		void iTreeSearch(node* i, int k);

		void rtreeMAX(node * i);
		void treeSUCCESSOR(node * i);
		void treePREDECESSOR(node * i);
		

};	

void BST::PreOT(node* i)
{
		if(i != NULL)
		{
			cout<<(i->key)<< "  ";
			POT(i->left);
			POT(i->right);
		}
}
void BST::IOT(node* i)
{
		if(i != NULL)
		{

			IOT(i->left);
			cout<<(i->key)<< " ";
			IOT(i->right);
		}
}

void BST::POT(node * i)
{
		if(i != NULL)
		{
			POT(i->left);
			POT(i->right);
			cout<<(i->key)<< "  ";
		}
}


void BST::itreeMIN(node * i)
{
	while(i->left != NULL)
		 i = i->left;
	cout<<endl<<(i->key)<<endl;
}
void BST::rtreeMIN(node * i)
{
	if(i->left != NULL)
		rtreeMIN(i->left);
	cout<<(i->key)<<endl;
}


void BST::itreeMAX(node * i)
{
	while(i->right != NULL)
		i = i->right;
	cout<<endl<<(i->key)<<endl;
}
void BST::rtreeMAX(node * i)
{
	if(i->right != NULL)
	{
		rtreeMAX(i->right);
	}
	cout<<(i->key)<<endl ;
}


void BST::treeSUCCESSOR(node * i)
{
	if(i->right != NULL)
		itreeMIN(i->right);
	node* y = i->parent;
	while(y != NULL && i == y->right)
	{
		i = y;
		y = y->parent;
	}
//cout<<(i->key)<<" is root."<<endl;   //OR return y;
}


void BST::treePREDECESSOR(node * i)
{
	if(i->left != NULL)
	{
		itreeMAX(i->left);
	}

	node * y= i->parent;
	while(y != NULL && i== y->left)
	{
		i=y;
		y = y->parent;
	}
cout<<endl<<(i->key)<<" is root."<<endl;
}




void BST::iTreeSearch(node* i, int k)
{
	cout<<"Searching for: "<<k<<endl;
	while(i != NULL && k != i->key)
	{
		if(k < i->key)
			i = i->left;
		else if(k > i->key)
			i = i->right;
		else
			cout<<"Key NOT found: "<<endl;
	}
cout<<"Key Found is: "<<(i->key)<<endl;
}

void BST::rTreeSearch(node* i, int k)
{
	cout<<"Searching for key: "<<k<<endl;
	if(i== NULL || i->key == k)
			cout<<"Key found is: "<<(i->key)<<endl;
	else if(k < i->key)
			rTreeSearch(i->left, k);
	else if(k > i->key)
		rTreeSearch(i->right, k);
	else  if(k != i->key)
	     cout<<"NOT FOUND..!!"<<endl;
}




int main()
{
	clrscr();
	BST b1;
	node* node1= new node;
	
getch();
	return 0;
}

But the proble now is that i want to add insert() instead of using array in constructor..Secondly i want to access the functions in main()..I did like you told me before about passing node in the function argument..but its giving errors..
In the treesearch function the last else statement, which should work when the key isn't found in the tree, is also not working..and garbage data is shown instead of it..

Plese don't think that im copying from somewhere..i have really put my efforts in making this program..
I hope you'll try to solve my problems..

Mehwish Shaikh 0 Light Poster · Answer 9 · 2008-09-04T16:02:32+00:00

Thanks alot niek_e....
That one really helped me alot....
but im still confused about something, s i don't know some basic points of C++..
Like whether to use ; after an if statement or not..and the stuff like this..:
I have made this program..which is error-free..

#include <iostream.h>
#include <conio.h>
#define NULL 0

struct node
{
	node* parent;
	node* left;
	node* right;
	int key;
};

class BST
{
	private:

		node* root;
		node array[3];

	public:

		BST()
		{
			root = &array[0];

			array[0].parent = NULL;
			array[0].left = &array[1];
			array[0].right = &array[2];
			array[0].key = 66;

			array[1].parent = &array[0];
			array[1].left = NULL;
			array[1].right =NULL;
			array[1].key = 50;

			array[2].parent = &array[0];
			array[2].left = NULL;
			array[2].right = NULL;
			array[2].key = 23;

			cout<< "Preorder Traverse:\n";
			PreOT(root);
			cout<< endl;
			cout<< "Inorder Traversing:  ";
			cout<<endl;
			IOT(root);
			cout<< endl;
			cout<< "\nPostorder Traverse:\n";
			POT(root);
			cout<< endl;
			cout<<"Minimum iteratively" <<endl;
			itreeMIN(root);
			cout<<endl;
			cout<<"\nMaximum iteratively" <<endl;
			itreeMAX(root);
			cout<<endl;
			cout<<"\nMinimum recursively" <<endl;
			rtreeMIN(root);
			cout<<endl;
			cout<<"\nMaximum recursively" <<endl;
			rtreeMAX(root);
			cout<<endl;
			cout<<"\nPredecessor is: "<<endl;
			treePREDECESSOR(root);
			cout<<endl;
			cout<<"\nSuccessor is: "<<endl;
			treeSUCCESSOR(root);
			cout<<endl;
			cout<<"\nSearching tree recursively: "<<endl;
			rTreeSearch(root, 10);
			cout<<endl;
			cout<<"\nSearching tree iteratively: "<<endl;
			iTreeSearch(root,50) ;
			cout<<endl;
		}
		void PreOT(node* i);
		void IOT(node* i);
		void POT(node* i);
		void itreeMIN(node* i);
		void rtreeMIN(node * i);
		void itreeMAX(node* i);
		void rtreeMAX(node * i);
		void treeSUCCESSOR(node * i);
		void treePREDECESSOR(node * i);
		void rTreeSearch(node* i, int k);
		void iTreeSearch(node* i, int k);


};	

void BST::PreOT(node* i)
{
		if(i != NULL)
		{
			cout<<(i->key)<< "  ";
			POT(i->left);
			POT(i->right);
		}
}
void BST::IOT(node* i)
{
		if(i != NULL)
		{

			IOT(i->left);
			cout<<(i->key)<< " ";
			IOT(i->right);
		}
}

void BST::POT(node * i)
{
		if(i != NULL)
		{
			POT(i->left);
			POT(i->right);
			cout<<(i->key)<< "  ";
		}
}


void BST::itreeMIN(node * i)
{
	while(i->left != NULL)
		 i = i->left;
	cout<<endl<<(i->key)<<endl;
}
void BST::rtreeMIN(node * i)
{
	if(i->left != NULL)
		rtreeMIN(i->left);
	cout<<(i->key)<<endl;
}


void BST::itreeMAX(node * i)
{
	while(i->right != NULL)
		i = i->right;
	cout<<endl<<(i->key)<<endl;
}
void BST::rtreeMAX(node * i)
{
	if(i->right != NULL)
	{
		rtreeMAX(i->right);
	}
	cout<<(i->key)<<endl ;
}


void BST::treeSUCCESSOR(node * i)
{
	if(i->right != NULL)
		itreeMIN(i->right);
	node* y = i->parent;
	while(y != NULL && i == y->right)
	{
		i = y;
		y = y->parent;
	}
//cout<<(i->key)<<" is root."<<endl;   //OR return y;
}


void BST::treePREDECESSOR(node * i)
{
	if(i->left != NULL)
	{
		itreeMAX(i->left);
	}

	node * y= i->parent;
	while(y != NULL && i== y->left)
	{
		i=y;
		y = y->parent;
	}
cout<<endl<<(i->key)<<" is root."<<endl;
}




void BST::iTreeSearch(node* i, int k)
{
	cout<<"Searching for: "<<k<<endl;
	while(i != NULL && k != i->key)
	{
		if(k < i->key)
			i = i->left;
		else if(k > i->key)
			i = i->right;
		else
			cout<<"Key NOT found: "<<endl;
	}
cout<<"Key Found is: "<<(i->key)<<endl;
}

void BST::rTreeSearch(node* i, int k)
{
	cout<<"Searching for key: "<<k<<endl;
	if(i== NULL || i->key == k)
			cout<<"Key found is: "<<(i->key)<<endl;
	else if(k < i->key)
			rTreeSearch(i->left, k);
	else if(k > i->key)
		rTreeSearch(i->right, k);
	else  if(k != i->key)
	     cout<<"NOT FOUND..!!"<<endl;
}




int main()
{
	clrscr();
	BST b1;
	node* node1= new node;
	
getch();
	return 0;
}

But the proble now is that i want to add insert() instead of using array in constructor..Secondly i want to access the functions in main()..I did like you told me before about passing node in the function argument..but its giving errors..
In the treesearch function the last else statement, which should work when the key isn't found in the tree, is also not working..and garbage data is shown instead of it..

Plese don't think that im copying from somewhere..i have really put my efforts in making this program..
I hope you'll try to solve my problems..

Nick Evan 4,005 Industrious Poster Team Colleague Featured Poster · Answer 10 · 2008-09-04T16:12:17+00:00

But the proble now is that i want to add insert() instead of using array in constructor..

Inserting is quite simple. "Insertion into a tree is a variation of an unsuccessful search". In other words: You just search the tree for a number. If it doesn't exist in the tree, you will automatically be at the leaf where the data should be added. So make a new node and insert it at that leaf.

Plese don't think that im copying from somewhere..i have really put my efforts in making this program..

To be honest: I still suspect that you copied the code from somewhere. If you don't understand how a semicolon works, pointers and trees should be way out of your league. But that's just my opinion.

The link I gave you has a lot of useful information on binary trees, it's worth the read.

dmanw100 36 Posting Whiz in Training · Answer 11 · 2008-09-05T19:24:37+00:00

cls is Windows-specific so it won't work on all platforms

Nick Evan 4,005 Industrious Poster Team Colleague Featured Poster · Answer 12 · 2008-09-05T20:01:00+00:00

cls is Windows-specific so it won't work on all platforms

Although this is true, was does this have to do with anything in this thread?