Saturday 5 April 2014

C++ Program To Perform Binary Search Tree Operations (Insertion,Deletion and Searching ) Using Recursion


C++ Program To Perform Binary Search Tree Operations (Insertion,Deletion and Searching ) Using Recursion


-------------------------------------------------------------------------------
-------------------------------------------------------------------------------



#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