Friday, August 31, 2012

C Program for Deleting node from Binary Search Tree

#include<iostream.h>
#include<alloc.h>
#include<conio.h>
struct tree
{
  int item;
  struct tree *left,*right;
}*h;
void join(tree *p,tree *q)
{
  if(p==NULL)
  {h=q;return;}
  if(p->item<q->item)
  {
    if(p->right!=NULL)
    join(p->right,q);
    else
    p->right=q;
  }
  else
  {
    if(p->left!=NULL)
    join(p->left,q);
    else
    p->left=q;
  }
}
void BST()
{
  tree *q;
  cout<<"Enter Value";
  q=(tree*)malloc(sizeof(tree));
  cin>>q->item;
  q->right=NULL;
  q->left=NULL;
  join(h,q);
  cout<<"Continue y/n";
  if(getche()=='y')
  BST();
  else
  return;
}
void print_inorder(struct tree *p)
{

     if(p==NULL)return;
     print_inorder(p->left);
     cout<<endl<<p->item;
     print_inorder(p->right);
}
void del(tree *q,int num)
{
  tree *parent=NULL;
  while(q!=NULL)
  {
    if(q->item==num)
    break;
    else if(q->item>num)
    {parent=q;q=q->left;}
    else
    {parent=q;q=q->right;}
  }
  cout<<"Parent"<<parent->item;

  if(q->left==NULL&&q->right==NULL)
  {
   if(parent->item<num)parent->right=NULL;
   else parent->left=NULL;
   free(q);
  }
  else if(q->left!=NULL&&q->right==NULL)
  {
   if(parent->item<num)parent->right=q->left;
   else parent->left=q->left;
   free(q);
  }
  else if(q->left==NULL&&q->right!=NULL)
  {
   if(parent->item<num)parent->right=q->right;
   else parent->left=q->right;
   free(q);
  }
  else
  {
    tree *temp=NULL,*inorder_successor=NULL;
    temp=q;
    inorder_successor=q->right;
    while(inorder_successor->left!=NULL)
    {
     temp=inorder_successor;
     inorder_successor=inorder_successor->left;
    }
    if(inorder_successor->right!=NULL)
    temp->left=inorder_successor->right;
    else if(q!=temp)
    temp->left=NULL;
    else
    temp->right=NULL;

    inorder_successor->left=q->left;
    inorder_successor->right=q->right;

    if(parent->item<inorder_successor->item)parent->right=inorder_successor;
    else parent->left=inorder_successor;
  }
}
void main()
{
 clrscr();
 h=NULL;
 cout<<"\nEnter Values to Build a B.S.T\n";
 BST();
 cout<<"\nInorder Traversal of B.S.T";
 print_inorder(h);
 cout<<"Enter";
 int x;
 cin>>x;
 del(h,x);
 print_inorder(h);
 getch();
}

No comments:

Post a Comment