PROGRAM TO IMPLEMENT EXPRESSION TREE AND PRINTING IN INORDER TRAVERSAL

PROGRAM TO IMPLEMENT EXPRESSION TREE AND PRINTING IN INORDER

Please not that here operator will be at roots and operands will be at leaves.It is useful for evaluating expressions.The following code implements expression tree.

/******************************************************

Program for creating an expression tree and printing it using an inorder traversal

*******************************************************/

#include <iostream.h>

#include <conio.h>

#include <ctype.h>

#define size 20

typedef struct node

{

char data;

struct node *left;

struct node *right;

}btree;

class EXP_TREE

{

private:

/*stack stores the operand nodes of the tree*/

btree  *stack[size];

int  top;

public:

btree *root;

EXP_TREE();

void create(char exp[]);

void push(btree *);

void display(btree *root);

btree* pop();

};

EXP_TREE::EXP_TREE()

{

 root=NULL;

 top=-1;//initializing stack

}

void EXP_TREE::create(char exp[])

{

 int pos;

 char ch;

 pos = 0;

 ch = exp[pos];

 while ( ch !='\0')

 {

/* Create a new node */

  root = new btree;

  root -> left = root -> right = NULL ;

  root -> data = ch;

  if (isalpha( ch) ) /* is it a operand */

push ( root); /* push operand */

  else if ( ch=='+' ||ch=='-'||ch=='*'||ch=='/')

  {

   /* it is operator, so pop two nodes from stack

 set first node as right child and

 set second as left child and push the

operator node on to the stack

   */

root->right = pop();

root->left = pop();

push(root);

  }

  else

cout<<"Invalid character in expression\n";

  pos ++;

   ch = exp[pos]; /* Read next character */

 }

 root= pop();

}

void EXP_TREE::push(btree *Node)

{

if ( top+1 >= size )

cout<<"Error: Stack is Full\n";

top++;

stack[top] = Node;

}

btree* EXP_TREE::pop()

{

btree *Node;

if ( top == -1 )

 cout<<"Error: Stack is Empty\n";

Node = stack[top];

top--;

return(Node);

}

void EXP_TREE::display(btree *root)

{

btree *temp;

temp = root;

if (temp != NULL )

{

 display(temp->left);

 cout<<" "<<temp->data;

 display(temp->right);

}

}

void main()

{

 char  exp[80]; /* exp stores postfix expression */

 EXP_TREE obj;

 clrscr();

 cout<<"Enter the postfix expression\n";

 cin>>exp;

 obj.create(exp);

 cout<<"\n The Tree is created...\n";

 cout<<"\n The inorder traversal of it is \n ";

 obj.display(obj.root);

 getch();

}

If you have any query,please notify me so that i can help you.Good day.

CODE FOR THREADED BINARY TREE

THREADED BINARY TREE IMPLEMENTATION (C++ CODE)

Last Updated On: 12th Dec 2015

Introduction

If we consider the case of Binary Tree creation, for the leaf nodes there is no sub tree further. So we are just setting the left and right fields of leaf nodes to NULL. Since NULL value is put in the left and right field of the node, it is just a wastage of the memory. So to avoid null values in the node we just set the threads which are actually the links to the predecessor and successor nodes.

There are three types of threading possible:

• Inorder Threading
• Preorder Threading
• Postorder Threading 

In this tutorial we will be looking at Inorder Threading Technique which is the most famous one. The typical C structure of the node of Threaded Binary Tree would like :

typedef struct bst
  {
   int data;
   int lth,rth;
   struct bst *left,*right;
  }

And The typical threaded binary tree looks like this:

Now let's see the code for threaded binary tree in action:

# include <iostream.h>
# include <conio.h>
 typedef struct bst
  {
   int data;
   int lth,rth;
   struct bst *left,*right;
  }node;
class thread
{
  private:

  node *dummy;
  node *New,*root,*temp,*parent;
 public:
 thread();
 void create(); //All The implementation Details are hidden!
 void display();
 void find();
 void delet();
};
/*
--------------------------------------------------------------------------
constructor 
--------------------------------------------------------------------------
*/
thread::thread()
{
 root=NULL;
}
/*
--------------------------------------------------------------------------
create function
--------------------------------------------------------------------------
*/
void thread::create()
{
  void insert(node *,node *);
  New=new node;
  New->left=NULL;
  New->right=NULL;
  New->lth=0;
  New->rth=0;
  cout<<"\n Enter The Element ";
  cin>>New->data;
  if(root==NULL)
  {                                      // Tree is not Created
   root=New;
   dummy=new node;
   dummy->data=-999;
   dummy->left=root;
   root->left=dummy;
   root->right=dummy;
  }
  else
  insert(root,New);
}

/*
--------------------------------------------------------------------------
display function
--------------------------------------------------------------------------
*/
void thread::display()
{
  void inorder(node *,node *dummy);
  if(root==NULL)
            cout<<"Tree Is Not Created";
  else
            {
               cout<<"\n The Tree is : ";
               inorder(root,dummy);
            }
}
/*
--------------------------------------------------------------------------
find function which calls the routine for searching an elemnt
--------------------------------------------------------------------------
*/
void thread::find()
{
  node *search(node *,node *,int,node **);
  int key;
  cout<<"\n Enter The Element Which You Want To Search";
  cin>>key;
  temp=search(root,dummy,key,&parent);
  if(temp==NULL)
   cout<<"\nElement is Not Present";
  else
   cout<<" It's Parent Node is "<<parent->data;
}
/*
--------------------------------------------------------------------------
delet function which calls the routine for deletion of an element
--------------------------------------------------------------------------
*/
void thread::delet()
{
  void del(node *,node *,int);
  int key;
  cout<<"\n Enter The Element U wish to Delete";
  cin>>key;
  del(root,dummy,key);
}
/*
--------------------------------------------------------------------------
function is for creating a binary search tree
--------------------------------------------------------------------------
*/
void insert(node *root,node *New)
{
  if(New->data<root->data)
   {
             if(root->lth==0)
              {
                        New->left=root->left;
                        New->right=root;
                        root->left=New;
                        root->lth=1;
             }
             else
                        insert(root->left,New);
  }
  if(New->data>root->data)
  {
            if(root->rth==0)
            {
                        New->right=root->right;
                        New->left=root;
                        root->rth=1;
                        root->right=New;
            }
            else
             insert(root->right,New);
  }
}
/*
--------------------------------------------------------------------------
search function
--------------------------------------------------------------------------
*/
node *search(node *root,node *dummy,int key,node **parent)
{
  node *temp;
  int flag=0;
  temp=root;
  while((temp!=dummy))
  {
   if(temp->data==key)
   {
            cout<<"\n The "<<temp->data<<" Element is Present";
            flag=1;
            return temp;
  }
   *parent=temp;
   if(temp->data>key)
            temp=temp->left;
   else
            temp=temp->right;
  }
return NULL;
}

/*
--------------------------------------------------------------------------
function is for deleting a node from binary search tree
There exists three possible cases for deletion of a node
--------------------------------------------------------------------------
*/

void del(node *root,node *dummy,int key)
{
  node *temp,*parent,*temp_succ;
  node *search(node *,node *,int,node **);
  int flag=0;
  temp=search(root,dummy,key,&parent);
  if(root==temp)
  {
   cout<<"\n Its Root Node Which Can Not Be Deleted!!";
   return;
  }
  //deleting a node with two children
  if(temp->lth==1&&temp->rth==1)
  {
   parent=temp;
   temp_succ=temp->right;//Finding Inorder successor
   while(temp_succ->lth==1)
   {
            flag=1;
            parent=temp_succ;
            temp_succ=temp_succ->left;
   }
   if(flag==0)
   {
            temp->data=temp_succ->data;
            parent->right=temp_succ->right;
            parent->rth=0;
  }
  else//inorder successor is on left subbranch.
                        // and it has to be traversed
  {
            temp->data=temp_succ->data;
            parent->rth=0;
            parent->lth=0;
            parent->left=temp_succ->left;
   }
   cout<<" Now Deleted it!";
   return;
  }
 //deleting a node having only one child
  //The node to be deleted has left child
  if(temp->lth==1 &&temp->rth==0)
  {
   if(parent->left==temp)
   {
            (temp->left)->right=parent;
             parent->left=temp->left;
   }
   else
   {
            (temp->left)->right=temp->right;
            parent->right=temp->left;
   }
   temp=NULL;
   delete temp;
   cout<<" Now Deleted it!";
   return;
  }

  //The node to be deleted has right child
  if(temp->lth==0 &&temp->rth!=0)
  {
   if(parent->left==temp)
   {
            parent->left=temp->right;
            (temp->right)->left=temp->left;
            (temp->right)->right=parent;
   }
   else
   {
            parent->right=temp->right;
            (temp->right)->left=parent;

   }
   temp=NULL;
   delete temp;
   cout<<" Now Deleted it!";
   return;
  }
  //deleting a node which is having no child
  if(temp->lth==0 &&temp->rth==0)
  {
            if(parent->left==temp)
            {
              parent->left=temp->left;
              parent->lth=0;
            }
            else
             {
               parent->right=temp->right;
               parent->rth=0;
             }
   cout<<" Now Deleted it!";
   return;
  }
}
/*
--------------------------------------------------------------------------
inorder function
--------------------------------------------------------------------------
*/
void inorder(node *temp,node *dummy)
{
   while(temp!=dummy)
   {
            while(temp->lth==1)
             temp=temp->left;
   cout<<"  "<<temp->data;
   while(temp->rth==0)
   {
   temp=temp->right;
            if(temp==dummy)
             return;
            cout<<"  "<<temp->data;
   }
   temp=temp->right;
  }
 }
/*
--------------------------------------------------------------------------
main function
--------------------------------------------------------------------------
*/
void main()
{
   int choice;
   char ans='N';
   thread th;
   clrscr();
   do
   {

            cout<<"\n\t Program For Threaded Binary Tree";
            cout<<"\n1.Create \n2.Display \n3.Search \n4.Delete";
            cin>>choice;
            switch(choice)
            {
              case 1:do
                                    {
                                      th.create();
                                       cout<<"\n Do u Want To enter More  Elements?(y/n)";
                                       ans=getch();
                                    }while(ans=='y');
                                    break;
             case 2:th.display();
                                    break;
             case 3:th.find();
                                    break;
             case 4:th.delet();
                           break;
            }
   cout<<"\n\nWant To See Main Menu?(y/n)";
   ans=getche();
   }while(ans=='y');
}

BTREE IMPLEMENTATION

BTREE IMPLEMENTATION (C++ CODE):

#include<iostream.h>
#include<conio.h>
#define max 5

class node;
struct pair
 {
  node *next;
  int key;
 };

class node
{
 public:
 int noofkeys;
 pair data[max];
 node *father;
 node *first;
 node();
 int leafnode();
 void insertinanode(pair x);
 pair splitanode(pair x);
 node *nextindex(int x);
 void display();
};

void node::display()
{
 cout<<"(";
 for(int i=0;i<noofkeys;i++)
 cout<<data[i].key<<" ";
 cout<<")";
}

node *node::nextindex(int x)
{
 if(x<data[0].key)
 return(first);
 for(int i=0;i<noofkeys;i++)
 if(x<=data[i].key)
 return data[i-1].next;
 return data[i-1].next;
}

int node::leafnode()
{
 if(data[0].next==NULL)
 return 1;
 return 0;
}

void node::insertinanode(pair x)
{
 for(int i=noofkeys-1;i>=0&&data[i].key>x.key;i--)
 data[i+1]=data[i];
 data[i+1]=x;
 noofkeys++;
}

pair node::splitanode(pair x)
{
 node *t;
 pair mypair;
 int i,j,centre;
 centre=(noofkeys-1)/2;
 t=new node;
 if(x.key>data[centre].key)
 {
  for(i=centre+1,j=0;i<=noofkeys;i++,j++)
  t->data[j]=data[i];
  t->noofkeys=noofkeys-centre-1;
  noofkeys=noofkeys-t->noofkeys;
  t->insertinanode(x);
  t->first=t->data[0].next;
  t->father=father;
  mypair.key=t->data[0].key;
  mypair.next=t;
  for(i=1;i<t->noofkeys;i++)
  t->data[i-1]=t->data[i];
  t->noofkeys--;
 }
 else
 {
  for(i=centre,j=0;i<noofkeys;i++,j++)
  t->data[j]=data[i];
  t->noofkeys=noofkeys-centre;
  noofkeys=noofkeys-t->noofkeys;
  insertinanode(x);
  t->father=father;
  mypair.key=t->data[0].key;
  mypair.next=t;
  for(i=1;i<t->noofkeys;i++)
  t->data[i-1]=t->data[i];
  t->noofkeys--;
 }
 return(mypair);
}

node::node()
{
 for(int i=0;i<=max;i++)
 data[i].next=NULL;
 noofkeys=0;
 father=NULL;
 first=NULL;
}

class q
{
 node *data[60];
 int r,f;
 public:
 q()
 {
  r=f=0;
 }
 int empty()
 {
  if(r==f)
  return 1;
  else
  return 0;
 }
 node *deque()
 {
  return data[f++];
 }
 void enque(node *x)
 {
  data[r++]=x;
 }
 void makeempty()
 {
  r=f=0;
 }
};

class btree
{
 int mkeys;
 node *root;
 public:
 btree(int n)
 {
  mkeys=n;
  root=NULL;
 }
 void insert(int x);
 void displaytree();
 node *search(int x);
 void delet(int x);
};

node *btree::search(int x)
{
 node *p;
 int i;
 p=root;
 while(p!=NULL)
 {
  for(i=0;i<p->noofkeys;i++)
  if(x==p->data[i].key)
  return(p);
  p=p->nextindex(x);
 }
 return NULL;
}

void btree::displaytree()
{
 q q1,q2;
 node *p;
 q1.enque(root);
 while(!q1.empty())
 {
  q2.makeempty();
  cout<<"\n";
  while(!q1.empty())
  {
   p=q1.deque();
   p->display();
   cout<<" ";
   if(!p->leafnode())
   {
    q2.enque(p->first);
    for(int i=0;i<p->noofkeys;i++)
    q2.enque(p->data[i].next);
   }
  }
  q1=q2;
 }
}

void btree::insert(int x)
{
 int index;
 pair mypair;
 node *p,*q;
 mypair.key=x;
 mypair.next=NULL;
 if(root==NULL)
 {
  root=new node;
  root->insertinanode(mypair);
 }
 else
 {
  p=root;
  while(!(p->leafnode()))
  p=p->nextindex(x);
  if(p->noofkeys<mkeys)
  p->insertinanode(mypair);
  else
  {
   mypair=p->splitanode(mypair);
   while(1)
   {
    if(p==root)
    {
     q=new node;
     q->data[0]=mypair;
     q->first=root;
     q->father=NULL;
     q->noofkeys=1;
     root=q;
     q->first->father=q;
     q->data[0].next->father=q;
     return;
    }
    else
    {
     p=p->father;
     if(p->noofkeys<mkeys)
     {
      p->insertinanode(mypair);
      return;
     }
     else
     mypair=p->splitanode(mypair);
    }
   }
  }
 }
}

void btree::delet(int x)
{
 node *left,*right;
 pair *centre;
 node *p,*q;
 int i,j,centreindex;
 p=search(x);
 for(i=0;p->data[i].key!=x;i++)
 if(!p->leafnode())
 {
  q=p->data[i].next;
  while(!q->leafnode())
  q=q->first;
  p->data[i].key=q->data[0].key;
  p=q;
  x=q->data[0].key;
  i=0;
 }
 for(i=i+1;i<p->noofkeys;i++)
 p->data[i-1]=p->data[i];
 p->noofkeys--;
 while(1)
 {
  if(p->noofkeys>=mkeys/2)
  return;
  if(p==root)
  if(p->noofkeys>0)
  return;
  else
  {
   root=p->first;
   return;
  }
  q=p->father;
  if(q->first==p||q->data[0].next==p)
  {
   left=q->first;
   right=q->data[0].next;
   centre=&(q->data[0]);
   centreindex=0;
  }
  else
  {
   for(i=1;i<q->noofkeys;i++)
   if(q->data[i].next==p)
   break;
   left=q->data[i-1].next;
   right=q->data[i].next;
   centre=&(q->data[i]);
   centreindex=i;
  }
  if(left->noofkeys>mkeys/2)
 {
  right->data[i+1]=right->data[i];
  right->noofkeys++;
  right->data[0].key=centre->key;
  centre->key=left->data[left->noofkeys-1].key;
  left->noofkeys--;
  return;
 }
 else
 if(right->noofkeys>mkeys/2)
 {
  left->data[left->noofkeys].key=centre->key;
  left->noofkeys++;
  centre->key=right->data[0].key;
  for(i=1;i<right->noofkeys;i++)
  right->data[i-1]=right->data[i];
  right->noofkeys--;
  return;
 }
 else
 {
  left->data[left->noofkeys].key=centre->key;
  left->noofkeys++;
  for(j=0;j<right->noofkeys;j++)
  left->data[left->noofkeys+j]=right->data[j];
  left->noofkeys+=right->noofkeys;
  for(i=centreindex+1;i<q->noofkeys;i++)
  q->data[i-1]=q->data[i];
  q->noofkeys--;
  p=q;
 }
}
}

void main()
{
 int i,n,x,op;
 node *p;
 clrscr();
 cout<<"\nEnter number of keys in the node:";
 cin>>n;
 btree b(n);
 do
 {
  cout<<"\n*****MENU*****";
  cout<<"\n1.Insert \n2.Search \n3.Delete \n4.Display \n5.Quit";
  cout<<"\nEnter your choice:";
  cin>>op;
  switch(op)
  {
   case 1:
   cout<<"\nEnter a data:";
   cin>>x;
   b.insert(x);
   cout<<"\nTree after insertion:";
   b.displaytree();
   break;

   case 2:
   cout<<"\nEnter a data:";
   cin>>x;
   p=b.search(x);
   if(p!=NULL)
   {
    cout<<"Found in the node!";
    p->display();
   }
   else
   cout<<"\nElement not found!";
   break;

   case 3:
   cout<<"\nEnter a data:";
   cin>>x;
   p=b.search(x);
   if(p!=NULL)
   {
    b.delet(x);
    b.displaytree();
   }
   else
   cout<<"\nNot found!";
   break;

   case 4:
   b.displaytree();
   break;
  }
 }while(op!=5);
}

BINARY SEARCH TREE

BINARY SEARCH TREE (C++ CODE):

/*TITLE : TO PERFORM OPERATIONS ON BINARY SEARCH TREE

#include<iostream.h>
#include<conio.h>
#include<stdlib.h>

class bt
{
struct node{
int data;
node *lchild,*rchild;
  }*root;

public:
bt()
{
root=NULL;
}
void create();
void recc();
void preorder(node*);
void postorder(node*);
void inorder(node*);
void preorder();
void inorder();
void postorder();
void search(int t);
void del_node();

};
void bt::create()
{
node *temp,*curr,*req;
int ch;
do
{
temp=new node;
temp->lchild=NULL;
temp->rchild=NULL;
cout<<"\nenter the data\n";
cin>>temp->data;
if(root==NULL)
   root=temp;
else
{
req=root;
while(req!=NULL)
{
curr=req;
if(curr->data>temp->data)
ch=1;

else
ch=2;
switch(ch)
{
case 1:
req=curr->lchild;
break;
case 2:
req=curr->rchild;
}
}
switch(ch)
{
case 1:
curr->lchild=temp;
break;
case 2:
curr->rchild=temp;
}
}
cout<<"do you want to enter more data? (1/0)";
cin>>ch;
}while(ch);
}

void bt::recc()
{
if(root==NULL)
{
cout<<"\ntree is empty";
return;
}

int ch;
do
{
cout<<"\n********menu**********\n";
cout<<"1\tpreorder\n2\tinorder\n3\tpostorder\n";
cin>>ch;
switch(ch)
{
case 1:
preorder(root);
break;
case 2:
inorder(root);
break;
case 3:
postorder(root);
break;
}
cout<<"\nDo you want to continue (0/1)\t:";
cin>>ch;
}while(ch);
}

void bt::preorder(node *t)
{
if(t==NULL)
{
return;
}
else
{
cout<<"  "<<t->data;
preorder(t->lchild);
preorder(t->rchild);
}
}

void bt::postorder(node *t)
{
if(t==NULL)
{
return;
}
else
{
postorder(t->lchild);
postorder(t->rchild);
cout<<"  "<<t->data;
}
}
void bt::inorder(node *t)
{

if(t==NULL)
{
return;
}
else
{
inorder(t->lchild);
cout<<"  "<<t->data;
inorder(t->rchild);
}
}

void bt::search(int t)
{
int flag=0;
node *temp=root;
while(temp!=NULL)
{
if(t==temp->data)
{
flag=1;
break;
}
else if(t>temp->data)
temp=temp->rchild;
else
temp=temp->lchild;
}
if(flag==1)
cout<<"\ndata is present\n";
}

void bt::del_node()
{
int t;
cout<<"\nenter the data to be deleted\n";
cin>>t;
int flag=0;
node *par,*curr,*temp=root;
while(temp!=NULL)
{
if(t==temp->data)
{
flag=1;
break;
}
else if(t>temp->data)
{
curr=temp;
temp=temp->rchild;
}
else
{
curr=temp;
temp=temp->lchild;
}
}
if(flag==1)
{
if((temp->lchild==NULL)&&(temp->rchild==NULL))
{
if(curr->lchild==temp)
curr->lchild=NULL;
if(curr->rchild==temp)
curr->rchild=NULL;
delete temp;
}
else if((temp->lchild==NULL)||(temp->rchild==NULL))
{
if(temp->lchild==NULL)
{ temp->data=temp->rchild->data;
delete temp->rchild;
temp->rchild=NULL;
}
else if(temp->rchild==NULL)
{
temp->data=temp->lchild->data;
delete temp->lchild;
temp->lchild=NULL;
}
}

else
{
curr=temp;
temp=temp->rchild;
par=NULL;
while(temp->lchild!=NULL)
{
par=temp;
temp=temp->lchild;
}

if(par!=NULL)
{
par->lchild=temp->rchild;
curr->data=temp->data;
delete temp;
}
else
{
curr->data=temp->data;
curr->rchild=NULL;
delete temp;
}

}
}
else
cout<<"\ndata not present\n";
}

void main()
{
clrscr();
bt a;
int ch,t;
cout<<"\nCreate a tree\n";
a.create();
do
{
cout<<"\n1. inserting\n2. traversal\n3.search \n4. delete\n5.exit\n";
cin>>ch;
switch(ch)
{
case 1:
a.create();
break;
case 2:
a.recc();
break;
case 3: cout<<"\nenter the data to be searched\n";
cin>>t;
a.search(t);
break;
case 4:
a.del_node();
case 5:exit(1);

}
}while(ch);
getch();

}

OPERATIONS ON BINARY TREE

OPERATIONS ON BINARY TREE (C++ CODE):

/* TITLE: TO IMPLEMENT BINARY TREE AND PERFORM OPERATIONS LIKE FINDING HEIGHT AND MIRROR IMAGE


#include<iostream.h>
#include<conio.h>
#define size 10

class tree
{
 private:
 typedef struct bin
 {
  int data;
  struct bin *left;
  struct bin *right;
 }node;

 public:
  node *New,*root;
  node *que[10];
  int front,rear;
  tree();
  void create();
  void insert(node *,node *);
  int height(node *root);
  void leaf(node *root,int *);
  void convert();
  void mirror(node *root);
  void display(node *root);
  void enque(node *temp);
  node *deque();
 };

 tree::tree()
 {
  root=NULL;
  front=rear=-1;
 }

 void tree::create()
 {
  char ans='y';
  do
  {
   New=new node;
   cout<<"Enter the element:\t";
   cin>>New->data;
   New->left=NULL;
   New->right=NULL;

   if(root==NULL)
    root=New;
   else
    insert(root,New);
    cout<<"\nDo u want to enter more elements?(y/n):\t";
    cin>>ans;
   }while(ans=='y'||ans=='Y');
   clrscr();

  }

  void tree::insert(node *root,node *New)
  {
   if(New->data>root->data)
   {
    if(root->right!=NULL)
    insert(root->right,New);
    else
    root->right=New;
   }

   else

    if(New->data<root->data)
    {
     if(root->left!=NULL)
     insert(root->left,New);
     else
     root->left=New;
    }
   }

   int tree::height(node *root)
   {
    int d1,d2;
    if(root==NULL)
    return 0;
    if(root->left==NULL&&root->right==NULL)
    return 0;
    d1=height(root->left);
    d2=height(root->right);
    if(d1>d2)
    return d1+1;
    else
    return d2+1;

   }

   void tree::leaf(node *root,int *count)
   {


    if(root!=NULL)
    {
     if((root->left==NULL)&&(root->right==NULL))
     {
      cout<<" "<<root->data;
      *count=*count+1;
     }
     else
     {
      leaf(root->left,count);
      leaf(root->right,count);
      }
     }
    }

    void tree::convert()
    {
     cout<<"\n Original image is...\n";
     display(root);
     mirror(root);
     cout<<"\nMirror image is created";
     cout<<"\nMirror image is...\n";
     display(root);
    }

    void tree::mirror(node *root)
    {
     node *temp;
     if(root!=NULL)
     {
      mirror(root->left);
      mirror(root->right);
      temp=root->left;
      root->left=root->right;
      root->right=temp;
     }
    }

    void tree::enque(node *temp)
    {
     if(rear==size-1)
     {
      cout<<"Queue is empty\n";
      return;
     }

     rear=rear+1;
     que[rear]=temp;
     }

     node* tree::deque()
     {
      node *temp;
      if(front==rear)
      {
       cout<<"Queue is empty";
       return NULL;
      }
      front++;
      temp=que[front];
      return temp;
      }

      void tree::display(node *root)
      {
       node *temp,*dummy;
       dummy=new node;
       front=rear=-1;
       if(dummy==NULL)
cout<<"Insufficient memory\n";
dummy->left=root;
dummy->right=NULL;
dummy->data=-999;
temp=dummy->left;
enque(temp);
enque(dummy);
temp=deque();
cout<<"\n";
while(front!=rear)
{
if(temp!=dummy)
{
 cout<<" "<<temp->data;
 if(temp->left!=NULL)
 enque(temp->left);
 if(temp->right!=NULL)
 enque(temp->right);
}
else
{
 enque(temp);
 cout<<"\n";
}
temp=deque();

}
       }

      void main()
      {
       int choice;
       tree obj;
       int ht;
       int *count;
       clrscr();
       do
       {
cout<<"\nProgram for implementing simple binary tree";
cout<<"\n1.Create";
cout<<"\n2.Height of binary tree";
cout<<"\n3.Leaf Nodes";
cout<<"\n4.Mirror image";
cout<<"\n5.Level-wise display";
cout<<"\n6.Exit";
cout<<"\n\tEnter your choice:";
cin>>choice;
switch(choice)
{
case 1:obj.create();
break;
case 2:ht=obj.height(obj.root);
cout<<"\The height of the tree is: "<<ht;
break;
case 3:*count=0;
cout<<"\n Leaf nodes are...\n";
obj.leaf(obj.root,count);
cout<<"\nThe total leaf nodes are: "<<*count;
break;
case 4:obj.convert();
break;
case 5:obj.display(obj.root);
getch();
break;

}
}while(choice<=5);
getch();
      }

C CODE FOR AVL TREE

C++ code for AVL TREE :

#include<iostream.h>
#include<conio.h>
class avl
{
private:
  struct node
{
int data;
node *left,*right;
int ht;
};
public:
node *avlroot;
node *insert1(node *,int);
node *delete1(node *,int);
void preorder1(node *);
void inorder1(node *);
int height(node*);
node *rotateright(node *);
node *rotateleft(node *);
node *rr(node *);
node *ll(node *);
node *rl(node *);
node *lr(node *);
int bf(node *);

avl()
{
avlroot=NULL;
}
void insert(int x)
{
avlroot=insert1(avlroot,x);
}
void delet(int x)
{
avlroot=delete1(avlroot,x);
}
void preorder()
{
preorder1(avlroot);
}
void inorder()
{
inorder1(avlroot);
}

void levelwise();

void makenull()
{

avlroot=NULL;
}

};
node *avl::insert1(node *t,int x)
{
if(t==NULL)
{
t=new node;

t->data=x;
t->left=NULL;
t->right=NULL;
}
else
if(x>t->data)
{
t->right=insert1(t->right,x);
if(bf(t)==-2)
if(x>t->right->data)
t=rr(t);
else
t=rl(t);
}
else
if(x<t->data)
{
t->left=insert1(t->left,x);
if(bf(t)==2)
if(x<t->left->data)
t=ll(t);
else
t=lr(t);
}
t->ht=height(t);
return(t);
}

node *avl::delete1(node *t,int x)
{
node *p;
if(t==NULL)
{
return NULL;
}
else
if(x>t->data)
{
t->right=delete1(t->right,x);
if(bf(t)==2)
if(bf(t->left)>=0)
t=ll(t);
else
t=lr(t);
}
else
if(x<t->data)
{
t->left=delete1(t->left,x);
if(bf(t)==-2)
if(bf(t->right)<=0)
t=rr(t);
else
t=rl(t);
}
else
{
if(t->right!=NULL)
{
p=t->right;
while(p->left!=NULL)
p=p->left;

t->data=p->data;
t->right=delete1(t->right,p->data);
if(bf(t)==2)
if(bf(t->left)>=0)
t=ll(t);
else
t=lr(t);
}
else
return(t->left);
}
t->ht=height(t);
return(t);
}

int avl::height(node *t)
{
   int lh,rh;
   if(t==NULL)
   return(0);
   if(t->left==NULL)
   lh=0;
   else
   lh=1+t->left->ht;
   if(t->right==NULL)
   rh=0;
   else
   rh=1+t->right->ht;
   if(lh>rh)
      return(lh);

   return(rh);
}
node *avl::rotateright(node *x)
{
  node *y;
  y=x->left;
  x->left=y->right;
  y->right=x;
  x->ht=height(x);
  y->ht=height(y);
  return(y);
}

node *avl::rotateleft(node *x)
{
node *y;
y=x->right;
x->right=y->left;
y->left=x;
x->ht=height(x);
y->ht=height(y);
return(y);
}

node *avl::rr(node *t)
{
t=rotateleft(t);
return(t);
}
node *avl::ll(node *t)
{
t=rotateright(t);
return(t);
}

node *avl::lr(node *t)
{
t->left=rotateleft(t->left);
t=rotateright(t);
return(t);
}

node *avl::rl(node *t)
{
t->right=rotateright(t->right);
t=rotateleft(t);
return(t);
}

int avl::bf(node *t)
{
int lh,rh;
if(t==NULL)
return(0);
if(t->left==NULL)
lh=0;
else
lh=1+t->left->ht;
if(t->right==NULL)
rh=0;
else
rh=1+t->right->ht;
return(lh-rh);
}

void avl::preorder1(node *t)
{
if(t!=NULL)
{
cout<<" "<<t->data<<"(bf="<<bf(t)<<")";
preorder1(t->left);
preorder1(t->right);
}
}

void avl::inorder1(node *t)
{
if(t!=NULL)
{
inorder1(t->left);
cout<<" "<<t->data<<"(bf="<<bf(t)<<")";
inorder1(t->right);
}
}

void main()
{
   avl a;
   int x,n,i,ch;
   char choice;
   clrscr();
   do
   {
cout<<"\n1.create\n2.print\n3.insert\n4.delete\n5.quit\n";
cout<<"\n Enter your choice:";
cin>>ch;
switch(ch)
{
case 1:
cout<<"\n Enter the no.of elements:";
cin>>n;
cout<<"\n Enter tree data:";
a.makenull();
for(i=0;i<n;i++)
{
cin>>x;
a.insert(x);
}
break;

case 2:
cout<<"\npreorder sequence:\n";
a.preorder();
cout<<"\nInorder sequence:\n";
    a.inorder();
    break;
case 3:
cout<<"\nEnter the data:";
cin>>x;
a.insert(x);
break;

case 4:
cout<<"\n Enter the data:";
cin>>x;
a.delet(x);
break;


    }
    cout<<"do u want to continue y/n:";
    cin>>choice;
  }while(choice=='y');

}