BINARY SEARCH TREE
EX.NO :
DATE :
AIM
To implement binary search tree and its operation in C++ language
ALGORITHM
Step 1: Start
Step 2: Read the option value
Step 3: If option=1 then read x
And check if root is NULL then assign root as t
Step 4: Else store current data as x and print it
If (curr->data=x) then assign left child to curr and check if (curr==NULL)
Prev->lchild=t
Step 5: Else prev=curr, curr=curr->rchild then check if (curr==NULL) then Pre->rchild=t
Step 6: Print the value of x
Step 7: Enter the no. of deleted x. check p is not NULL and then assign lchild as p.
Step 8: If p is NULL then print x
Check p as root then assign c as root. Then delete the node p.
Step 9: Stop
PROGRAM
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
class btnode
{
public:
int val;
btnode *left,*right;
friend class bstree;
}*root,*t;
class bstree
{
public:
void insert(int x,btnode * & t);
btnode * find(const int,btnode * & t);
btnode * findmin(btnode * & t);
btnode * findmax(btnode * & t);
void remove(int,btnode * & t);
void makeempty(btnode * & t);
int display(btnode * & t);
};
void bstree::insert(int x, btnode * & t)
{
if(t==NULL)
{
t=new btnode;
t->left=NULL;
t->right=NULL;
t->val=x;
}
else if(x<t->val)
insert(x,t->left);
else if(t->val<x)
insert(x,t->right);
}
btnode * bstree::find(const int x,btnode * & t)
{
if(t==NULL)
return (NULL);
else if(x<t->val)
return find(x,t->left);
else if(t->val<x)
return find(x,t->right);
else
return t;
}
btnode * bstree::findmin(btnode * & t)
{
if(t==NULL)
return NULL;
if(t->left==NULL)
return t;
return findmin(t->left);
}
btnode * bstree::findmax(btnode * & t)
{
if(t!=NULL)
while(t->right!=NULL)
t=t->right;
return t;
}
void bstree::remove(int x,btnode * & t)
{
if(t==NULL)
{
cout<"The element not found in tree";
return;
}
if(x<t->val)
remove(x,t->left);
else if(t->val<x)
remove(x,t->right);
else if(t->left!=NULL&t->right!=NULL)
{
t->val=findmin(t->right)->val;
remove(t->val,t->right);
}
else
{
btnode *oldnode=t;
t=(t->left!=NULL)?t->left:t->right;
delete oldnode;
cout<"the element is deleted";
}
}
void bstree::makeempty(btnode * & t)
{
if(t!=NULL)
{
makeempty(t->left);
makeempty(t->right);
delete t;
}
t=NULL;
}
int bstree::display(btnode * & t)
{
if(t==NULL)
return 0;
display(t->left);
cout<t->val<"\t";
display(t->right);
return 1;
}
void main()
{
bstree bb;
int ele,ch=0,node,search;
clrscr();
cout<"Implementation of binary search tree";
root=NULL;
do
{
cout<"MENU:\t1.Insert\t2.Delete\t3.Display\t4.Find\t5.findmin\t6.findmax\t7.Clear\t8.Exit\n";
cout<"Enter the choice";
cin>ch;
switch(ch)
{
case 1:
cout<"Enter the no. of nodes for btree";
int no;
cin>no;
for(int i=0;i<no;i++)
{
cout<"Enter the"<i+1<"value:";
cin>ele;
bb.insert(ele,root);
}
break;
case 2:
cout<"Enter the node to be deleted";
cin>node;
bb.remove(node,root);
break;
case 3:
cout<"The nodes in the tree are:\n";
bb.display(root);
//if(bb.display(root)==0)
//cout<"The tree is empty";
break;
case 4:
cout<"Enter the element to be searched";
cin>search;
t=bb.find(search,root);
if(t->val==search)
cout<"the element is found";
else
cout<"The element is not found";
break;
case 5:
t=bb.findmin(root);
cout<"the minimum node in the tree is:"<t->val;
break;
case 6:
t=bb.findmax(root);
cout<"The maximum node in the tree is:"<t->val;
break;
case 7:
bb.makeempty(root);
cout<"The tree is now empty";
break;
case 8:
exit(0);
}
}while(ch<=9);
}
OUTPUT
Implementation of binary search tree
MENU: 1.Insert 2.Delete
3.Display 4.Find 5.findmin 6.findmax 7.Clear 8.Exit
Enter the choice 1
Enter the no. of nodes for btree 3
Enter the 1 value: 5
Enter the 2 value: 65
Enter the 3 value: 7
MENU: 1.Insert 2.Delete 3.Display 4.Find 5.findmin
6.findmax 7.Clear 8.Exit
Enter the choice 2
Enter the node to be deleted 65
the element is deleted
MENU: 1.Insert 2.Delete 3.Display
4.Find 5.findmin 6.findmax 7.Clear 8.Exit
Enter the choice 3
The nodes in the tree are:
5 7
MENU: 1.Insert 2.Delete 3.Display 4.Find
5.findmin 6.findmax 7.Clear 8.Exit
Enter the choice 4
Enter the element to be searched 7
the element is found
MENU: 1.Insert 2.Delete 3.Display
4.Find 5.findmin 6.findmax 7.Clear 8.Exit
Enter the choice 5
the minimum node in the tree is: 5
MENU: 1.Insert 2.Delete 3.Display 4.Find 5.findmin 6.findmax 7.Clear 8.Exit
Enter the choice 6
The maximum node in the tree is: 7
MENU: 1.Insert 2.Delete 3.Display 4.Find 5.findmin 6.findmax 7.Clear 8.Exit
Enter the choice 7
The tree is now empty
MENU: 1.Insert 2.Delete 3.Display
4.Find 5.findmin 6.findmax 7.Clear 8.Exit
Enter the choice 8
RESULT
Hence the program is executed and the output is obtained successfully.