Create binary tree and perform recursive and non-recursive traversals

//1. Create binary tree and perform recursive and non-recursive traversals
/*  Binary tree*/
#include<iostream.h>
#include<conio.h>
#include<stdio.h>
#define max 100
class node
{
public :
int data;
node *lt,*rt;
};
node * root;
class bsttree
{
public :
bsttree()
{
root=NULL;
};
node* create();
node * getnode();
void inorder_rec(node *);
void postorder_rec(node *);
void preorder_rec(node *);
void inorder();
void postorder();
void preorder();
};

class stack
{
private :
node * item[max],*pt;
int top;
public :
stack()
{
top=-1;
}
void push(node *pt)
{
if(isfull())
cout<<"\nFull stack ";
else
{
top++;
item[top]=pt;
}
}
node * pop()
{
if(isempty())
cout<<"\nEmpty stack ";
else
{
pt=item[top];
top--;
}
return pt;
}
int isempty()
{
if(top==-1)
return 1;
else
return 0;
}
int isfull()
{
if(top==max-1)
return 1;
else
return 0;
}
node * gettopright()
{
return item[top]->rt;
}

};
node * bsttree::getnode()
{
node * newnode;
newnode=new node;
if(newnode==NULL)
cout<<"\nMemory allocation error ";
else
{
cout<<"\nEnter data : ";
cin>>newnode->data;
newnode->rt=newnode->lt=NULL;
}
return newnode;
}

node* bsttree:: create()
{
node * newnode,*pt;
char ch;
newnode=getnode();
pt=newnode;
cout<<"\nIs left child present of"<<pt->data<<": ";
flushall();
cin>>ch;
if(ch=='y')
pt->lt= create();
cout<<"\nIs right child present of"<<pt->data<<": ";
flushall();
cin>>ch;
if(ch=='y')
pt->rt=create();

return pt;
}
void bsttree::inorder_rec(node * pt)
{
if(pt!=NULL)
{
inorder_rec(pt->lt);
cout<<"\t"<<pt->data;
inorder_rec(pt->rt);
}
}
void bsttree::preorder_rec(node * pt)
{
if(pt!=NULL)
{
cout<<"\t"<<pt->data;
preorder_rec(pt->lt);
preorder_rec(pt->rt);
}
}
void bsttree::postorder_rec(node * pt)
{
if(pt!=NULL)
{
postorder_rec(pt->lt);
postorder_rec(pt->rt);
cout<<"\t"<<pt->data;
}
}

void bsttree::inorder()
{
stack s;
node * pt;
if(root==NULL)
{
cout<<"\nEmpty re ";
}
else
{
cout<<"\nInorder : ";
pt=root;
while(1)
{
while(pt!=NULL)
{
s.push(pt);
pt=pt->lt;
}
if(s.isempty())
{
break;
}
pt=s.pop();
cout<<"\t"<<pt->data;
pt=pt->rt;
}
}
}
void bsttree::preorder()
{
stack s;
node * pt;
if(root==NULL)
{
cout<<"\nEmpty re ";
}
else
{
cout<<"\nPreorder : ";
pt=root;
while(1)
{
while(pt!=NULL)
{
cout<<"\t"<<pt->data;
if(pt->rt!=NULL)
{
s.push(pt->rt);
}
pt=pt->lt;
}
if(s.isempty())
{
break;
}
pt=s.pop();
}
}
}
void bsttree::postorder()
{
node * pt;
stack s;
if(root==NULL)
cout<<"\nEmpty Tree ";
else
{
pt=root;
while(1)
{
while(pt!=NULL)
{
s.push(pt);
pt=pt->lt;
}
pt=s.pop();
if(pt->rt==NULL)
{
cout<<"\t"<<pt->data;
while(!s.isempty()&&pt==s.gettopright())
{
pt=s.pop();
cout<<"\t"<<pt->data;
}
pt=s.gettopright();
}
else
{
s.push(pt);
pt=pt->rt;
}
if(s.isempty())
break;
}
}
}
void main()
{
clrscr();
int ch;
bsttree obj;
do
{
cout<<"\n1.Create\n2.Preorder rec\n3.Postorder rec\n4.Inorder rec ";
cout<<"\n5.Preorder\n6.Postorder\n7.Inorder\n8.Exit";
cout<<"\nEnter choice no : ";
cin>>ch;
switch(ch)
{
case 1:
root=obj.create();
break;
case 2:
obj.preorder_rec(root);
break;
case 3:
obj.postorder_rec(root);
break;
case 4:
obj.inorder_rec(root);
break;
case 5:
obj.preorder();
break;
case 6:
obj.postorder();
break;
case 7:
obj.inorder();
break;
}
}while(ch!=8);
}
/*
OUTPUT


1.Create
2.Preorder rec
3.Postorder rec
4.Inorder rec
5.Preorder
6.Postorder
7.Inorder
8.Exit
Enter choice no : 1

Enter data : 12

Do u want to add nore node (y/n)Y

Enter data : 20

Do u want to add nore node (y/n)Y

Enter data : 5

Do u want to add nore node (y/n)Y

Enter data : 6

Do u want to add nore node (y/n)Y

Enter data : 4

Do u want to add nore node (y/n)N

Enter data : 1

Do u want to add nore node (y/n)n

1.Create
2.Preorder rec
3.Postorder rec
4.Inorder rec
5.Preorder
6.Postorder
7.Inorder
8.Exit
Enter choice no : 2
12      20       5       4       1       6
1.Create
2.Preorder rec
3.Postorder rec
4.Inorder rec
5.Preorder
6.Postorder
7.Inorder
8.Exit
Enter choice no : 3
1       4       6       5       20       12
1.Create
2.Preorder rec
3.Postorder rec
4.Inorder rec
5.Preorder
6.Postorder
7.Inorder
8.Exit
Enter choice no : 4
1       4       5       6       12       20
1.Create
2.Preorder rec
3.Postorder rec
4.Inorder rec
5.Preorder
6.Postorder
7.Inorder
8.Exit
Enter choice no : 5

Preorder :      12      20       5       4       1       6
1.Create
2.Preorder rec
3.Postorder rec
4.Inorder rec
5.Preorder
6.Postorder
7.Inorder
8.Exit
Enter choice no : 6

Postorder: 1       4       6       5       20      12
1.Create
2.Preorder rec
3.Postorder rec
4.Inorder rec
5.Preorder
6.Postorder
7.Inorder
8.Exit
Enter choice no : 7

Inorder :       1       4       5       6       12      20
1.Create
2.Preorder rec
3.Postorder rec
4.Inorder rec
5.Preorder
6.Postorder
7.Inorder
8.Exit
Enter choice no : 8
*/