C++ Program To Perform Binary Search Tree Operations (Insertion,Deletion and Searching ) Using Recursion
-------------------------------------------------------------------------------
>>> Click Here To Download <<<
-------------------------------------------------------------------------------
#include<iostream.h>
#include<conio.h>
#include<process.h>
struct node
{
node *left;
node *right;
int data;
};
class BST
{
public:
node *root;
BST()
{
root=NULL;
}
void display1()
{
display(root);
}
void display(node *rt)
{
if(rt!=NULL)
{
display(rt->left);
cout<<rt->data<<" ";
display(rt->right);
}
}
int isempty()
{
if(root==NULL)
return 1;
return 0;
}
void insert(int d)
{
node *t=new node;
node *par;
t->data=d;
t->left=t->right=par=NULL;
if(isempty())
root=t;
else
{
node *cur;
cur=root;
while(cur!=NULL)
{
par=cur;
if(t->data>cur->data)
cur=cur->right;
else
cur=cur->left;
}
if(t->data<=par->data)
par->left=t;
else
par->right=t;
}
}
void remove(int d)
{
int found=0;
if(isempty())
{
cout<<"The Tree is empty";
return;
}
node *cur;
node *par;
cur=root;
while(cur!=NULL)
{
if(cur->data==d)
{
found=1;
cout<<"Element is found";
break;
}
else
{
par=cur;
if(d>cur->data)
{
cur=cur->right;
}
else
{
cur=cur->left;
}
}
}
if(!found)
{
cout<<"Not found";
return;
}
if((cur->left==NULL)&&(cur->right==NULL))
{
if(par->left==cur)
par->left=NULL;
else
par->right=NULL;
delete cur;
return;
}
if(((cur->left==NULL)&&(cur->right!=NULL))||((cur->left!=NULL)&&(cur->right==NULL)))
{
if((cur->left==NULL)&&(cur->right!=NULL))
{
if(par->left==cur)
{
par->left=cur->right;
delete cur;
}
else
{
par->right=cur->right;
delete cur;
}
}
else
{
if(par->left==cur)
{
par->left=cur->left;
delete cur;
}
else
{
par->right=cur->left;
delete cur;
}
}
return;
}
if((cur->left!=NULL)&&(cur->right!=NULL))
{
node *chkr;
chkr=cur->right;
if((chkr->left==NULL)&&(chkr->right==NULL))
{
cur=chkr;
delete chkr;
cur->right=NULL;
}
else
{
if((cur->right)->left!=NULL)
{
node *lcur,*lcurp;
lcurp=cur->right;
lcur=(cur->right)->left;
while(lcur->left!=NULL)
{
lcurp=lcur;
lcur=lcur->left;
}
cur->data=lcur->data;
delete lcur;
lcurp->left=NULL;
}
else
{
node *temp;
temp=cur->right;
cur->data=temp->data;
cur->right=temp->right;
delete temp;
}
}
}
return;
}
};
void main()
{
int item,ch;
clrscr();
BST ob;
do
{
cout<<"\n1.insert\n2.delete\n3.display\n4.exit\n";
cout<<"Enter the option:";
cin>>ch;
switch(ch)
{
case 1:cout<<"Enter element to be inserted:";
cin>>item;
ob.insert(item);
break;
case 2:cout<<"Enter element to be deleted:";
cin>>item;
ob.remove(item);
break;
case 3:cout<<"Elements in the BST are:\n";
ob.display1();
break;
case 4:exit(0);
}
}while(ch<=4);
getch();
}
0 comments:
Post a Comment