Binary Search tree (BST) operations

/*Binary Search tree with insertion, deletion.....processes
compiler- Turbo c++     author- Mangilal Sharma
--------------------------------------------------------*/
# include <iostream.h>
# include <stdlib.h>
# include <conio.h>

struct bs_node
{
 int element;
 bs_node *left;
 bs_node *right;
 int height;
};

typedef struct bs_node *bs_nodeptr;

class bst
{
 public:
  bst();
      void insert(int,bs_nodeptr &);
      void del(int,bs_nodeptr &);
       int deletemin(bs_nodeptr &);
      void find(int,bs_nodeptr &);
bs_nodeptr findmin(bs_nodeptr);
bs_nodeptr findmax(bs_nodeptr);
      void copy(bs_nodeptr &,bs_nodeptr &);
      void makeempty(bs_nodeptr &);
bs_nodeptr bs_nodecopy(bs_nodeptr &);
      void preorder(bs_nodeptr);
      void inorder(bs_nodeptr);
      void postorder(bs_nodeptr);
       int bsheight(bs_nodeptr);
bs_nodeptr srl(bs_nodeptr &);
bs_nodeptr drl(bs_nodeptr &);
bs_nodeptr srr(bs_nodeptr &);
bs_nodeptr drr(bs_nodeptr &);
       int nobs_nodes(bs_nodeptr);
       int maxx(int value1,int value2)
       {
return ((value1 > value2) ? value1 : value2);
       }
};

void bst::insert(int x,bs_nodeptr &p)
{
 if (p == NULL)
 {
  p = new bs_node;
  p->element = x;
  p->left=NULL;
  p->right = NULL;
  p->height=0;
  if (p==NULL)
  cout<<"Out of Space";
 }
 else
 {
  if (x<p->element)
  {
   insert(x,p->left);
   if ((bsheight(p->left) - bsheight(p->right))==2)
   {
    if (x < p->left->element)
    p=srl(p);
    else
    p = drl(p);
   }
  }
  else if (x>p->element)
  {
   insert(x,p->right);
   if ((bsheight(p->right) - bsheight(p->left))==2)
   {
    if (x > p->right->element)
    p=srr(p);
    else
    p = drr(p);
   }
  }
  else
  cout<<"Element Exists";
 }
 int m,n,d;
 m=bsheight(p->left);
 n=bsheight(p->right);
 d=maxx(m,n);
 p->height = d + 1;
}

bs_nodeptr bst::findmin(bs_nodeptr p)
{
 if (p==NULL)
 {
  cout<<"Empty Tree";
  return p;
 }
 else
 {
  while(p->left !=NULL)
  p=p->left;
  return p;
 }
}

bs_nodeptr bst::findmax(bs_nodeptr p)
{
 if (p==NULL)
 {
  cout<<"Empty Tree";
  return p;
 }
 else
 {
  while(p->right !=NULL)
  p=p->right;
  return p;
 }
}

void bst::find(int x,bs_nodeptr &p)
{
 if (p==NULL)
 cout<<"Element not found";
 else
 if (x < p->element)
 find(x,p->left);
 else
 if (x>p->element)
 find(x,p->right);
 else
 cout<<"Element found !";
}

void bst::copy(bs_nodeptr &p,bs_nodeptr &p1)
{
 makeempty(p1);
 p1 = bs_nodecopy(p);
}

void bst::makeempty(bs_nodeptr &p)
{
 bs_nodeptr d;
 if (p != NULL)
 {
  makeempty(p->left);
  makeempty(p->right);
  d=p;
  free(d);
  p=NULL;
 }
}

bs_nodeptr bst::bs_nodecopy(bs_nodeptr &p)
{
 bs_nodeptr temp;
 if (p==NULL) return p;
 else
 {
  temp = new bs_node;
  temp->element = p->element;
  temp->left = bs_nodecopy(p->left);
  temp->right = bs_nodecopy(p->right);
  return temp;
 }
}

void bst::del(int x,bs_nodeptr &p)
{
 bs_nodeptr d;
 if (p==NULL)
 cout<<"Element not found";
 else if ( x < p->element)
 del(x,p->left);
 else if (x > p->element)
 del(x,p->right);
 else if ((p->left == NULL) && (p->right == NULL))
 {
  d=p;
  free(d);
  p=NULL;
  cout<<" Element deleted !";
 }
 else if (p->left == NULL)
 {
  d=p;
  free(d);
  p=p->right;
  cout<<" Element deleted !";
 }
 else if (p->right == NULL)
 {
  d=p;
  p=p->left;
  free(d);
  cout<<" Element deleted !";
 }
 else
 p->element = deletemin(p->right);
}

int bst::deletemin(bs_nodeptr &p)
{
 int c;
 cout<<"inside deltemin";
 if (p->left == NULL)
 {
  c=p->element;
  p=p->right;
  return c;
 }
 else
 {
  c=deletemin(p->left);
  return c;
 }
}

void bst::preorder(bs_nodeptr p)
{
 if (p!=NULL)
 {
  cout<<p->element<<"-->";
  preorder(p->left);
  preorder(p->right);
 }
}

void bst::inorder(bs_nodeptr p)
{
 if (p!=NULL)
 {
  inorder(p->left);
  cout<<p->element<<"-->";
  inorder(p->right);
 }
}

void bst::postorder(bs_nodeptr p)
{
 if (p!=NULL)
 {
  postorder(p->left);
  postorder(p->right);
  cout<<p->element<<"-->";
 }
}

int bst::bsheight(bs_nodeptr p)
{
 int t;
 if (p == NULL) return -1;
 else
 {
  t = p->height;
  return t;
 }
}

bs_nodeptr bst:: srl(bs_nodeptr &p1)
{
 bs_nodeptr p2;
 p2 = p1->left;
 p1->left = p2->right;
 p2->right = p1;
 p1->height = maxx(bsheight(p1->left),bsheight(p1->right)) + 1;
 p2->height = maxx(bsheight(p2->left),p1->height) + 1;
 return p2;
}

bs_nodeptr bst:: srr(bs_nodeptr &p1)
{
 bs_nodeptr p2;
 p2 = p1->right;
 p1->right = p2->left;
 p2->left = p1;
 p1->height = maxx(bsheight(p1->left),bsheight(p1->right)) + 1;
 p2->height = maxx(p1->height,bsheight(p2->right)) + 1;
 return p2;
}

bs_nodeptr bst:: drl(bs_nodeptr &p1)
{
 p1->left=srr(p1->left);
 return srl(p1);
}

bs_nodeptr bst::drr(bs_nodeptr &p1)
{
 p1->right = srl(p1->right);
 return srr(p1);
}

int bst::nobs_nodes(bs_nodeptr p)
{
 int count=0;
 if (p!=NULL)
 {
  nobs_nodes(p->left);
  nobs_nodes(p->right);
  count++;
 }
 return count;
}

bst::bst()
{
 clrscr();
 bs_nodeptr root,root1,minn,maxx;
 int a,choice,findele,delele,leftele,rightele,flag;
 root =NULL;
 root1=NULL;
 while(1)
 {
  cout<<"\n\tOperations on Binary Search tree..\n";
  cout<<"\t\t1.  Insertion\n";
  cout<<"\t\t2.  FindMin\n";
  cout<<"\t\t3.  FindMax\n";
  cout<<"\t\t4.  Find\n";
  cout<<"\t\t5.  Copy\n";
  cout<<"\t\t6.  Delete\n";
  cout<<"\t\t7.  Preorder\n";
  cout<<"\t\t8.  Inorder\n";
  cout<<"\t\t9.  Postorder\n";
  cout<<"\t\t10. Height\n";
  cout<<"\t\t11. To main page\n";
  cout<<"\t\t12. Exit\n";
  cout<<"\n\t\t      Enter Your Choice= ";
  cin>>choice;
  switch(choice)
  {
   case 1:
 cout<<"Enter new bs_nodes value:";
 cin>>a;
 insert(a,root);
 break;
   case 2:
 if (root !=NULL)
 {
  minn=findmin(root);
  cout<<"Min element : "<<minn->element;
 }
 break;
   case 3:
 if (root !=NULL)
 {
  maxx=findmax(root);
  cout<<"Max element : "<<maxx->element;
 }
 break;
   case 4:
 cout<<"Enter Search bs_node :";
 cin>>findele;
 if (root != NULL)
 find(findele,root);
 break;
   case 5:
 copy(root,root1);
 inorder(root1);
 break;
   case 6:
 cout<<"Enter bs_node that u want to delete:";
 cin>>delele;
 del(delele,root);
 inorder(root);
 break;
   case 7:
 cout<<" Preorder travers... :";
 preorder(root);
 break;
   case 8:
 cout<<" Inorder travers.... :";
 inorder(root);
 break;
   case 9:
 cout<<" Postorder travers... :";
 postorder(root);
 break;
   case 10:
 cout<<" Height and Depth is ";
 cout<<bsheight(root);
 cout<<"\nNo. of bs_nodes is "<<nobs_nodes(root);
 break;
   case 11:
  return;
   case 12:
  exit(1);
   default:
  cout<<"\n\t\tWrong Choice, Enter Again\n";
  }
 }
}
/*=========================14Nov.,2010=============================*/