Data Structures Program to create a binary tree and perform recursive and non-recursive traversals

Description :
A binary tree is a data structure in which each node has at most two child nodes called  as “left” and “right”. The tree has a header, which contains a link to a designated node (the root node). The root node has no parent.


Code :
#include<stdio.h>
#include<conio.h>
#include<iostream.h>
#include<alloc.h>
typedef struct node
{
int data;
struct node *left;
struct node *right;
}node;
class tree
{
public:
node *root;
tree()
{
root=NULL;
}

node* create();
void insert(node *root,node *New);
void inorder(node *root);
void preorder(node *root);
void postorder(node* root);
void nonrec_inorder(node *root);
void nonrec_preorder(node *root);
void nonrec_postorder(node* root);
};
class stack
{
node *data[30];
int top;
public:
stack()
{
top=-1;
}
int empty()
{
if(top==-1)
return 1;
return 0;
}
void push(node *root)
{
data[++top]=root;
}
node *pop()
{
return (data[top--]);
}
};
void main()
{
char ch;
int choice;
tree o;
clrscr();
cout<<”\n\n\t\t\t\t\t\t\t\t\t\t……BINARY TREE TRAVERSALS……”;
do
{
cout<<”\n\nMENU: “;
cout<<”\n\n1.Create\n\n2.Inorder(Recursive)\n\n3.Preorder(Recursive)\n\n4.Postorder(Recursive)\n\n5.Inorder(Non-Recursive)\n\n6.Preorder(Non-Recursive)\n\n7.Postorder(Non-Recursive)” ;
cout<<”\n\nEnter Your Choice: “;
fflush(stdin);
cin>>choice;
switch(choice)
{
case 1:
o.create();
break;
case 2 :
cout<<”\nInorder Recursive Traversal: “;
o.inorder(o.root);
break;
case 3 :
cout<<”\nPreorder Recursive Traversal: “;
o.preorder(o.root);
break;
case 4 :
cout<<”\nPostorder Recursive Traversal: “;
o.postorder(o.root);
break;
case 5 :
cout<<”\nInorder Non-Recursive Traversal: “;
o.nonrec_inorder(o.root);
break;
case 6:
cout<<”\nPreorder Non-Recursive Traversal: “;
o.nonrec_preorder(o.root);
break;
case 7:
cout<<”\nPostorder Non-Recursive Traversal: “;
o.nonrec_postorder(o.root);
break;
default:
cout<<”\n\nPlease Enter Correct Choice.”;
}
cout<<”\n\nDo You Want To Continue?(y/n): “;
fflush(stdin);
cin>>ch;
}while(ch==’y’ || ch==’Y');
getch();
}
node* tree::create()
{
node *New;
char ans;
do
{
New=new node;
New->left=NULL;
New->right=NULL;
cout<<”\n\nEnter the data: “;
cin>>New->data;
if(root==NULL)
{
root=New;
}
else
{
insert(root,New);
}
cout<<”\nDo you want to create more nodes?(y/n): ” ;
fflush(stdin);
cin>>ans;
}while(ans==’y’ || ans==’Y');
return root;
}
void tree::insert(node *root,node *New)
{
char ch1;
cout<<”\n\nInsert in left subtree or right subtree of “<<root->data<<” ?(l/r): “;
fflush(stdin);
cin>>ch1;
if(ch1==’l’ || ch1==’L')
{
if(root->left==NULL)
{
root->left=New;
}
else
{
insert(root->left,New);
}
}
if(ch1==’r’ || ch1==’R')
{
if(root->right==NULL)
{
root->right=New;
}
else
{
insert(root->right,New);
}
}
}
void tree::inorder(node *root)
{
node *temp;
temp=root;
if(temp!=NULL)
{
inorder(temp->left);
cout<<” “<<temp->data;
inorder(temp->right);
}
}
void tree::preorder(node *root)
{
node *temp;
temp=root;
if(temp!=NULL)
{
cout<<” “<<temp->data;
preorder(temp->left);
preorder(temp->right);
}
}
void tree::postorder(node *root)
{
node *temp;
temp=root;
if(temp!=NULL)
{
postorder(temp->left);
postorder(temp->right);
cout<<” “<<temp->data;
}
}
void tree::nonrec_inorder(node *root)
{
stack s;
node *temp=root;
cout<<”\t”;
while(temp!=NULL)
{
s.push(temp);
temp=temp->left;
}
while(!s.empty())
{
temp=s.pop();
cout<<” “<<temp->data;
temp=temp->right;
while(temp!=NULL)
{
s.push(temp);
temp=temp->left;
}
}
}
void tree::nonrec_preorder(node *root)
{
stack s;
node *temp=root;
cout<<”\t”;
while(temp!=NULL)
{
cout<<” ” <<temp->data;
s.push(temp);
temp=temp->left;
}
while(!s.empty())
{
temp=s.pop();
temp=temp->right;
while(temp!=NULL)
{
cout<<” “<<temp->data;
s.push(temp);
temp=temp->left;
}
}
}
void tree::nonrec_postorder(node *root)
{
stack s,s1;
node *temp=root;
cout<<”\t”;
while(temp!=NULL)
{
s.push(temp);
s1.push(NULL);
temp=temp->left;
}
while(!s.empty())
{
temp=s.pop();
if(s1.pop()==NULL)
{
s.push(temp);
s1.push((node *)1);
temp=temp->right;
while(temp!=NULL)
{
s.push(temp);
s1.push(NULL);
temp=temp->left;
}
}
else
cout<<” “<<temp->data;
} }