bstreee.cpp

binary search tree is umplemented using data structures in C++

#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
struct tree
{
	int data;
	struct tree *left,*right;
}*root=NULL;
void menu(void)
{
	cout<<"\n*****************Options are*******************\n\n";
	cout<<"\n1. To insert";
	cout<<"\n2. To search";
	cout<<"\n3. To delete";
	cout<<"\n4. To display";
	cout<<"\n5. To exit";
}
void menudisp(void)
{
	cout<<"\n*************Display Options**************\n\n";
	cout<<"\n1. To display in Pre-order";
	cout<<"\n2. To display in In-order";
	cout<<"\n3. To display in Post-order";
	cout<<"\n4. To exit";
}
void menusearch(void)
{
	cout<<"\n**************Search Options**************\n\n";
	cout<<"\n1. To search Specific value";
	cout<<"\n2. To search Maximum value";
	cout<<"\n3. To search Minimum value";
	cout<<"\n4. To exit";
}

void insert(struct tree **root,struct tree *current)
{
	if(*root==NULL)
	{
		*root=current;
	}
	else if((*root)->data==current->data)
	{
		cout<<"\nData already exit, You can't enter this data";
		getch();
	}
	else if(current->data>(*root)->data)
	{
		insert(&((*root)->right),current);
	}
	else
	{
		insert(&((*root)->left),current);
	}
}
void search_max(struct tree *root)
{
	struct tree *p;
	if(root==NULL)
	{
		cout<<"\nThere is no data in the tree";
	}
	else if(root->data!=NULL&&root->left==NULL&&root->right==NULL)
	{
		cout<<"\nThe tree contains only: "<<root->data;
	}
	else if(root->data!=NULL&&root->left!=NULL&&root->right==NULL)
	{
		cout<<"\nMaximun Data is: "<<root->data;
	}
	else
	{
		p=root;
		while(p->right!=NULL)
		{
			p=p->right;
		}
		cout<<"\nMaximum Data is: "<<p->data;
	}

}
void search_min(struct tree *root)
{
	struct tree *p;
	if(root==NULL)
	{
		cout<<"\nThere is no data in the tree";
	}
	else if(root->data!=NULL&&root->left==NULL&&root->right==NULL)
	{
		cout<<"\nThe tree contains only: "<<root->data;
	}
	else if(root->data!=NULL&&root->left==NULL&&root->right!=NULL)
	{
		cout<<"\nMinimum data is: "<<root->data;
	}
	else
	{
		p=root;
		while(p->left!=NULL)
		{
			p=p->left;
		}
		cout<<"\nMinimum data is: "<<p->data;
	}
}
void search(struct tree *root,int key)
{
	if(root==NULL)
	{
		cout<<"\nThe tree consists of no data!";
	}
	else if(root->data==key)
	{
		cout<<"\nData found!";
	}
	else if(root->data<key)
	{
		search(root->right,key);
	}
	else
	{
		search(root->left,key);
	}
}
void delete1(struct tree *ns,struct tree *ns1)
{
	if(ns==root&&root->left==NULL&&root->right==NULL)
	{       root=NULL;
		delete(ns);
	}
	else if(ns!=root&&ns->left==NULL&&ns->right==NULL)
	{
		if(ns1->left==ns)
		{
			ns1->left=NULL;
			delete(ns);
		}
		else if(ns1->right==ns)
		{
			ns1->right=NULL;
			delete(ns);
		}
	}
}
void delete2(struct tree *ns,struct tree *ns1)
{
	if(ns==root&&ns->left==NULL&&ns->right!=NULL)
	{
		root=root->right;
		ns->right=NULL;
		delete(ns);
	}
	else if(ns==root&&ns->right==NULL&&ns->left!=NULL)
	{
		root=root->left;
		ns->left=NULL;
		delete(ns);
	}
	else if(ns!=root&&ns->left==NULL&&ns->right!=NULL)
	{
		if(ns1->left==ns)
		{
			ns1->left=ns->right;
			delete(ns);
		}
		else if(ns1->right==ns)
		{
			ns1->right=ns->right;
			delete(ns);
		}
	}
	else if(ns!=root&&ns->left!=NULL&&ns->right==NULL)
	{
		if(ns1->left==ns)
		{
			ns1->left=ns->left;
			delete(ns);
		}
		else if(ns1->right==ns)
		{
			ns1->right=ns->left;
			delete(ns);
		}
	}
}
void deletefun(struct tree *root,int key)
{
	struct tree *s,*s1,*s2;
	s=root;
	while(s->data!=key&&s!=NULL)
	{
		if(s->data<key)
		{
			s=s->right;
			if(s->data!=root->data||s->data!=root->right->data)
			{
				s1=s->right;
			}
		}
		else if(s->data>key)
		{
			s=s->left;
				if(s->data!=root->data||s->data!=root->left->data)
			{
				s1=s->left;
			}
		}
		if(s->data==root->left->data||s->data==root->right->data)
		{
			s1=root;
		}
	}
      /*	if(s->data>root->data)
	{
		s1=root;
		while(s1->right->data<s->data)
		{
			s1=s1->right;
		}
		if(s1->right!=s)
		{
			s1=s1->right;
			while(s1->left!=s)
			{
				s1=s1->left;
			}
		}
	}
	else if(s->data<root->data)
	{
		s1=root;
		while(s1->left->data>s->data)
		{
			s1=s1->left;
		}
		if(s1->left!=s)
		{
			s1=s1->left;
			while(s1->right!=s&&s1->left!=s)
			{
				s1=s1->right;
			}
		}
	}*/
	if(s==NULL)
	{
		cout<<"\nData not found to delete";
		getch();
	}
	else if(s->left==NULL&&s->right==NULL)
	{
		delete1(s,s1);
	}
	else if(s->left!=NULL&&s->right==NULL)
	{
		delete2(s,s1);
	}
	else if(s->left==NULL&&s->right!=NULL)
	{
		delete2(s,s1);
	}
	else if(s->data!=NULL&&s->left!=NULL&&s->right!=NULL)
	{
		s1=s->right;
		if(s1->left!=NULL)
		{
			while(s1->left!=NULL)
			{
				s1=s1->left;
			}
			s2=s->right;
			while(s2->left!=s1)
			{
				s2=s2->left;
			}
			if(s1->right==NULL)
			{
				s->data=s1->data;
				//s2->left=NULL;
				delete1(s1,s2);
			}
			else if(s1->right!=NULL)
			{
				s->data=s1->data;
				delete2(s1,s2);
			}

		}
		else if(s1->left==NULL)
		{
			if(s1->right==NULL)
			{
				s->data=s1->data;
				if(s2->left==s1)
				{
					s2->left=NULL;
				}
				delete1(s1,s);
			}
			else if(s1->right!=NULL)
			{
				s->data=s1->data;
				delete2(s1,s);
			}
		}
	}
}
void display_pre(struct tree *root)
{
	if(root!=NULL)
	{
		cout<<root->data<<" ";
		display_pre(root->left);
		display_pre(root->right);
	}
}
void display_In(struct tree *root)
{
	if(root!=NULL)
	{
		display_In(root->left);
		cout<<root->data<<" ";
		display_In(root->right);
	}
}
void display_post(struct tree *root)
{
	if(root!=NULL)
	{
		display_post(root->left);
		display_post(root->right);
		cout<<root->data<<" ";
	}
}
void operation(void)
{
	struct tree *curr;
	int choice=0,key1,opt=0;
	while(choice!=5)
	{
		clrscr();
		menu();
		cout<<"\nEnter your choice: ";
		cin>>choice;
		switch(choice)
		{
			case 1:
			{
				curr=new tree;
				curr->left=NULL;
				curr->right=NULL;
				cout<<"\nEnter data: ";
				cin>>curr->data;
				insert((&root),curr);
				break;
			}
			case 2:
			{
				clrscr();
				menusearch();
				cout<<"\nEnter your choice: ";
				cin>>opt;
				switch(opt)
				{
					case 1:
					{
						clrscr();
						cout<<"\nEnter value you want to search: ";
						cin>>key1;
						search(root,key1);
						cout<<"\nPress any key to main menu!";
						getch();
						break;
					}
					case 2:
					{
						clrscr();
						search_max(root);
						cout<<"\nPress any key to go back to main menu";
						getch();
						break;
					}
					case 3:
					{
						clrscr();
						search_min(root);
						cout<<"\nPress any key to go back to main menu";
						getch();
						break;
					}
					case 4:
					{
						exit(1);
						break;
					}
					default:
					{
						cout<<"\nYou have entered wrong option!\n";
						cout<<"\nTry Again!";
					}
				}
				break;
			}
			case 3:
			{
				cout<<"\nEnter value you want to delete: ";
				cin>>key1;
				deletefun(root,key1);
				break;
			}
			case 4:
			{
				clrscr();
				menudisp();
				cout<<"\nEnter your option: ";
				cin>>opt;
				switch(opt)
				{
					case 1:
					{
						clrscr();
						display_pre(root);
						cout<<"\nPress any key to go to disp menu!";
						getch();
						break;
					}
					case 2:
					{
						clrscr();
						display_In(root);
						cout<<"\nPress any key to go to disp menu!";
						getch();
						break;
					}
					case 3:
					{
						clrscr();
						display_post(root);
						cout<<"\nPress any key to go to disp menu";
						getch();
						break;
					}
					case 4:
					{
						exit(1);
						break;
					}
					default:
					{
						cout<<"\nYou have entered wrong option!\n";
						cout<<"\nTry again!";
					}

				}
				break;
			}
			case 5:
			{
				exit(1);
				break;
			}
			default:
			{
				cout<<"\nYou have entered wrong option!";
			}
		}
	}
}
void main(void)
{
	root=NULL;
	clrscr();
	operation();
	getch();
}