Binary Search Tree Program in C++

#include <iostream.h>
#include <process.h>

class tnode
{
public:
 int data;
 tnode *lchild;
 tnode *rchild;
 tnode(int n,tnode *l=0,tnode *r=0)
 {  
  data=n;
  lchild=l;
  rchild=r;
 }
};

class Queue
{
private:
    int front,rear,size;
 tnode **a;
public:
 Queue(int size=0)
 {
  front=rear=-1;
  if (size!=0)
   a=new tnode*[size];
  else
   a=0;
  this->size=size;
 }
 void enqueue(tnode* el);
 tnode* dequeue();
 bool isempty() const;
};

void Queue::enqueue(tnode* el)
{
 if(isempty())
 {
       front=rear=0;
    a[front]=el;
 }
 else
 {
  rear=(rear+1)%size;
  a[rear]=el;
 }
}
tnode* Queue::dequeue()
{
 tnode* i;
 if (front==-1)
  cout<<"Empty list. Deletion not possible";
 else if (front==rear)
 {
  i=a[front];
     front=rear=-1;
 }
 else
 {  
  i=a[front];
  front=(front+1)%size;
 }
    return i;
}

bool Queue::isempty() const
{
 return(front==-1);
}

class BST
{
private:
 tnode *root;
 void preorder(tnode *);
 void postorder(tnode *);
 void inorder(tnode *);
public:
 BST()
 {
  root=0;
 }

 void insert(int x);
 void insert(tnode* &p,int x);
 void delete_by_copying(int x);
 void delete_by_merging(int x);
 tnode* search(int x);
 tnode* search(tnode * p,int x);
 void preorder();
 void postorder();
 void inorder();
 void level_by_level_traversal();
 int count_leafnode();
 int count_leafnode(tnode *t);
 int count_nonleaf();
 int count_nonleaf(tnode *t);
 int height();
 int height(tnode *t);
 tnode* mirror();
 tnode* mirror(tnode *p);
};

// Inserting an element
void BST::insert(int x)
{
 treenode*t=new treenode(x);
 if(root==NULL)
 {
  root=t;
  return;
 }
 treenode*p,*fp;
 p=root;
 fp=0;
 while(p!=0)
 {
  fp=p;
  if(x==p->data)
   throw"DUPLICATE VALUE";
  else if(x<p->data)
   p=p->lchild;
  else
   p=p->rchild;
 }
 if(x<fp->data)
  fp->lchild=t;
 else
  fp->rchild=t;
}

// Deletion By Copying
void BST::delete_by_copying(int x)
{
 if (root==0)
  throw "Empty tree";
 tnode *p=root;
 tnode *fp=0;
 while(p!=0 && p->data!=x)
 {
  fp=p;
  if (x<p->data)
   p=p->lchild;
  else
   p=p->rchild;
 }
    if (p==0)
  throw "Element not present ";
 bool lchild;
 if (fp!=0)
   lchild=(x<fp->data)?true:false;
 // if deleted node is a leaf
 if ((p->lchild==0) && (p->rchild)==0)
 {
  if (fp==0)
  {
   root=0;return;
  }
  if (lchild)
   fp->lchild=0;
     else
     fp->rchild=0;
 }
 // if deleted node has lchild only
 else if (p->rchild==0)
 {  
  if (fp==0)
  {
   root=p->lchild;
   return;
  }
  if (lchild)
   fp->lchild=p->lchild;
     else
     fp->rchild=p->lchild;
 }
 // if deleted node has rchild only
 else if (p->lchild==0)
 {  
  if (fp==0)
  {
   root=p->rchild;
   return;
  }
  if (lchild)
   fp->lchild=p->rchild;
     else
      fp->rchild=p->rchild;
 }
 // if both the children exists
 else
 { tnode *q=p->rchild;
   tnode *fq=p;
   while (q->lchild!=0)
   {
    fq=q;
    q=q->lchild;
   }
      p->data=q->data;
      if (q->data<fq->data)
    fq->lchild=q->rchild;
   else
    fq->rchild =q->rchild;
   delete q;
 }
}

// Deletion by Merging
void BST::delete_by_merging(int x)
{
 if (root==0)
  throw "Empty tree";
 tnode *p=root;
 tnode *fp=0;
 while(p!=0 && p->data!=x)
 {
  fp=p;
  if (x<p->data)
   p=p->lchild;
  else
   p=p->rchild;
 }
    if (p==0)
  throw "Element not present ";
 bool lchild;
 if (fp!=0)
   lchild=(x<fp->data)?true:false;
 // if deleted node is a leaf
 if ((p->lchild==0) && (p->rchild)==0)
 {
  if (fp==0)
  {
   root=0;return;
  }
  if (lchild)
   fp->lchild=0;
     else
      fp->rchild=0;
 }
 // if deleted node has lchild only
 else if (p->rchild==0)
 {  
  if (fp==0)
  {
   root=p->lchild;
   return;
  }
  if (lchild)
   fp->lchild=p->lchild;
     else
      fp->rchild=p->lchild;
 }
 // if deleted node has rchild only
 else if (p->lchild==0)
 {
  if (fp==0)
  {
   root=p->rchild;
   return;
  }
  if (lchild)
   fp->lchild=p->rchild;
     else
      fp->rchild=p->rchild;
 }
 // if both the children exists
 else
 {
   tnode *q=p->lchild;
   tnode *rc=p->rchild;
   while (q->rchild!=0)
   {
    q=q->rchild;
   }
   q->rchild=rc;
      if (fp==0)
    root=p->lchild;
   else
   {  
    if (p->data<fp->data)
     fp->lchild=p->lchild;
    else
     fp->rchild=p->lchild;
   }
   delete p;
 }
 }

//Searching an element
tnode* BST::search(int x)
{
          if (root==0)
     return(0);
          if (root->data==x)
     return (root);
          if (x<root->data)
     return(search(root->lchild,x));
          else
     return(search(root->rchild,x));
}

tnode* BST::search(tnode * p,int x)
{
          if (p==0)
     return(0);
          if (p->data==x)
     return (p);
          if (x<p->data)
     return(search(p->lchild,x));
          else
     return(search(p->rchild,x));
}

// Inorder Traversal
void BST::inorder()
{
 if (root==0)
  return;
 inorder(root->lchild);
 cout<<root->data<<"  ";
 inorder(root->rchild);
}

void BST::inorder(tnode* r)
{
 if (r==0)
  return;
 inorder(r->lchild);
 cout<<r->data<<"  ";
 inorder(r->rchild);
}

// Preorder Traversal
void BST::preorder()
{
 if (root==0)
  return;
 cout<<root->data<<"  ";
 preorder(root->lchild);
 preorder(root->rchild);
}

void BST::preorder(tnode* r)
{
 if (r==0)
  return;
 cout<<r->data<<"  ";
 preorder(r->lchild);
 preorder(r->rchild);
}

//Postorder Traversal
void BST::postorder()
{
 if (root==0)
  return;
 postorder(root->lchild);
 postorder(root->rchild); 
 cout<<root->data<<"  ";
}

void BST::postorder(tnode* r)
{
 if (r==0)
  return;
 postorder(r->lchild);
 postorder(r->rchild);
 cout<<r->data<<"  ";
}

// Level by Level Traversal
void BST::level_by_level_traversal()
{
 if(root==0)
 {
  cout<<"Empty tree";
  return;
 }
 cout<<"\nLevel by level traversal is ";
 Queue q(10);
 q.enqueue(root);
 while(!q.isempty())
 {
  tnode *p=q.dequeue();
  cout<<p->data<<" ";
  if(p->lchild!=0)
   q.enqueue(p->lchild);
  if(p->rchild!=0)
   q.enqueue(p->rchild);
 }
}

//Count leaf nodes
int BST::count_leafnode()
{
 if(root==0)
  return 0;
 else if(root->lchild==0&&root->rchild==0)
  return 1;
 else
  return(count_leafnode(root->lchild)+count_leafnode(root->rchild));
}

int BST::count_leafnode(tnode *t)
{
 if(t==0)
  return 0;
 else if(t->lchild==0&&t->rchild==0)
  return 1;
 else
  return(count_leafnode(t->lchild)+count_leafnode(t->rchild));
}

//Count non leaf nodes
int BST::count_nonleaf()
{
 if(root==0)
  return 0;
 else if(root->lchild==0&&root->rchild==0)
  return 0;
 else
  return(1+count_nonleaf(root->lchild)+count_nonleaf(root->rchild));
}  

int BST::count_nonleaf(tnode *t)
{
 if(t==0)
  return 0;
 else if(t->lchild==0&&t->rchild==0)
  return 0;
 else
  return(1+count_nonleaf(t->lchild)+count_nonleaf(t->rchild));
}

//Calculate height of tree
int BST::height()
{
 if (root==0)
  return 0;
 else if (root->lchild==0 && root->rchild==0)
  return 1;
 else
 {
   int hl=height(root->lchild);
   int hr=height(root->rchild);
   int max=hl>hr?hl:hr;
   return(max+1);
 }
}

int BST::height(tnode *t)
{
 if(t==0)
  return 0;
 else if(t->lchild==0&&t->rchild==0)
  return 1;
 else
 {
  int x=height(t->lchild);
  int y=height(t->rchild);
  if(x>y)
   return(1+x);
  else
   return (1+y);
 }
}

//Mirror image of tree
tnode* BST::mirror()
{
 if(root == NULL)
  return root ;
 else
 {
  mirror(root->lchild);
  mirror(root->rchild);
  tnode *temp;
  temp=root->lchild;
  root->lchild=root->rchild;
  root->rchild=temp;
 }
 return root;
}
tnode* BST::mirror(tnode *p)
{
 if(p == NULL)
  return p ;
 else
 {
  mirror(p->lchild);
  mirror(p->rchild);
  tnode *temp;
  temp=p->lchild;
  p->lchild=p->rchild;
  p->rchild=temp;
 }
 return p;
}

void main()
{
 BST b;
 int i,n;
 tnode *p;
 int ch;
 do
 {
  cout<<"\n\nMAIN MENU";
  cout<<"\n1.)Insertion ";
  cout<<"\n2.)Deletion by copying ";
  cout<<"\n3.)Deletion by merging";
  cout<<"\n4.)Search a no in BST ";
  cout<<"\n5.)In-Order Traversal ";
  cout<<"\n6.)Pre-Order Traversal ";
  cout<<"\n7.)Post-Order Traversal ";
  cout<<"\n8.)Level-by-level Traversal ";
  cout<<"\n9.)Count no of non leaf nodes ";
  cout<<"\n10.)Count no of leaf nodes ";
  cout<<"\n11.)Height of tree ";
  cout<<"\n12.)Mirror image ";
  cout<<"\n13.)Exit ";
  cout<<"\n\n\t\t\t Enter your choice: ";
  cin>>ch;
  switch(ch)
  {
   case 1 : cout<<"\n Enter the node to be inserted : ";
     cin>>n;
     b.insert(n);
     cout<<"\n The tree in inorder traversal is: ";
     b.inorder();
     break;
   case 2 : cout<<"\n Enter the node to be deleted : ";
     cin>>n;
     b.delete_by_copying(n);
     cout<<"\n The tree in inorder traversal is: ";
     b.inorder();
     break;
                        case 3 : cout<<"\n Enter the node to be deleted : ";
     cin>>n;
     b.delete_by_merging(n);
     cout<<"\n The tree in inorder traversal is: ";
     b.inorder();
     break;
   case 4 : cout<<"\n Enter the node to be searched: ";
            cin>>n;
     p=b.search(n);
     if(p!=0)
       cout<<"\n Node "<<p<<" found";
     else
       cout<<"\n Node not present";
     break;
   case 5 : cout<<"\n Inorder traversal is: ";
            b.inorder();
     break;
   case 6 : cout<<"\n Preorder traversal is: ";
            b.preorder();
     break;
   case 7 : cout<<"\n Postorder traversal is: ";
            b.postorder();
     break;
   case 8 : b.level_by_level_traversal();
     break;
          case 9 : n=b.count_nonleaf();
     cout<<"No. of non leaf nodes= "<<n;
            break;
          case 10: n=b.count_leafnode();
     cout<<"No. of leaf nodes= "<<n;
            break;
   case 11: n=b.height();
     cout<<"Height of tree= "<<n;
     break;
   case 12: p=b.mirror();
     cout<<"\n The tree in inorder traversal is: ";
     b.inorder();
     break;
   default: exit(0);
  }
 }while(ch!=13);
}