/******************************************************
Name : Jabir Daud Pathan
Name : Jabir Daud Pathan
Program : Create Binary Tree And Perform Recursive
And Non-Recursive Traversals
*******************************************************/
/*---------------<< Header File
>>------------------*/
#include<conio.h>
#include<iostream.h>
#include<stdlib.h>
struct node
{
int data;
node *left,*right;
node(int x)
{
data=x;
left=right=NULL;
}
};
/*----------<< Declaration of class tree
>>----------*/
class tree
{
private:
node *root;
public :
tree()
// Default constructor
{
root=NULL;
}
node*create();
void preorder_rec(node*); // [ Functions
void inorder_rec(node*); //
declaraton ]
void postorder_rec(node*);
void inorder_nonrec(node*);
void preorder_nonrec(node*);
void postorder_nonrec(node*);
};
/*------------<< Declaration of class stack
>>------------*/
class stack
{
private:
node *data[20];
int top;
public :
stack()
{
top=-1;
}
int empty()
{
if(top==-1)
return 1;
return 0;
}
void push(node*p)
{
data[++top]=p;
}
node *pop()
{
return(data[top--]);
}
};
/*----------<< Function defination for create
>>------------*/
node*tree::create()
{
node *p;
int x;
cout<<"\nEnter a data[-1 for no
data] : ";
cin >> x;
if(x==-1)
return NULL;
p=new node(x);
cout<<"\nEnter left child of
"<<x ;
p->left=create();
cout<<"\nEnter right child of
"<<x;
p->right=create();
return p;
}
/*--<<Function
defination for preorder traversal using recursion>>--*/
void
tree::preorder_rec(node *t)
{
if(t)
{
cout<<" "<<t->data;
preorder_rec(t->left);
preorder_rec(t->right);
}
}
/*--<<Function
defination for inorder traversal using recursion>>--*/
void
tree::inorder_rec(node *t)
{
if(t)
{
inorder_rec(t->left);
cout<<" "<<t->data;
inorder_rec(t->right);
}
}
/*--<<Function
defination for postorder traversal using recursion>>--*/
void
tree::postorder_rec(node *t)
{
if(t)
{
postorder_rec(t->left);
postorder_rec(t->right);
cout<<" "<<t->data;
}
}
/*--<<Function
defination for non_recursive preorder traversal>>--*/
void
tree::preorder_nonrec(node*curr)
{
stack s;
if(curr==NULL)
{
cout<<"Tree is not
created";
}
for(;;)
{
while(curr!=NULL)
{
cout<<" "<<curr->data;
s.push(curr);
curr=curr->left;
}
if(!s.empty())
{
curr=s.pop();
curr=curr->right;
}
}
}
/*--<<Function
defination for non_recursive inorder traversal>>--*/
void
tree::inorder_nonrec(node*curr)
{
stack s;
if(curr==NULL)
{
cout<<"Tree is not
created";
}
for(;;)
{
while(curr!=NULL)
{
s.push(curr);
curr=curr->left;
}
if(!s.empty())
{
curr=s.pop();
cout <<"
"<<curr->data;
curr=curr->right;
}
}
}
/*--<<Function
defination for non_recursive postorder traversal>>--*/
void
tree::postorder_nonrec(node*curr)
{
stack p,k;
if(curr==NULL)
{
cout<<"Tree is not
created";
}
while(curr!=NULL)
{
p.push(curr);
k.push(NULL);
curr=curr->left;
}
while(!p.empty())
{
curr=p.pop();
if(k.pop()==NULL)
{
p.push(curr);
k.push((node*)1);
curr=curr->right;
while(curr!=NULL)
{
p.push(curr);
k.push(NULL);
curr=curr->left;
}
}
else
cout<<"
"<<curr->data;
}
}
/*-------------<< Main Function Starts >>------------*/
void main()
{
tree t;
//creating object of class tree
node*root;
int ch;
char ans;
do
{
clrscr();
cout<<"\n\n\n\t\t\t<< BINARY
TREE TRAVERSAL >>";
cout<<"\n\n\t\t\t1.Recursive
Traversal";
cout<<"\n\n\t\t\t2.Non_recursive
Traversal";
cout<<"\n\n\t\t\t3.Exit";
cout<<"\n\n\t\t\t---------------------------";
cout <<"\n\n\t\t\tEnter Your
Choice : ";
cin>>ch;
switch(ch)
{
case 1:
do
{
clrscr();
cout<<"\n\n\t\t\t<<
RECURSIVE TRAVERSAL >>";
cout<<"\n\n\t\t\t-----<< MENU >>-----";
cout<<"\n\n\t\t\t1.Create
Tree";
cout<<"\n\t\t\t2.Preorder
Traversal";
cout<<"\n\t\t\t3.Inorder
Traversal";
cout<<"\n\t\t\t4.Postorder
Traversal";
cout<<"\n\t\t\t5.Exit";
cout<<"\n\n\t\t\t--------------------";
cout <<"\n\n\t\t\tEnter Your
Choice :";
cin>>ch;
switch(ch)
{
case 1:
root=t.create();
// function call
break;
case 2:
cout<<"\nPreorder
Traversal :";
t.preorder_rec(root);
break;
case 3:
cout<<"\nInorder
Traversal :";
t.inorder_rec(root);
break;
case 4:
cout<<"\nPostorder
Traversal :";
t.postorder_rec(root);
break;
case
5:
exit(0);
break;
}
cout<<"\n\n\n\tDo you want to
continue(y/n): ";
ans=getche();
}while(ans=='y'||ans=='Y');
break;
case 2:
do
{
clrscr();
cout<<"\n\n\t\t\t<<
NON_RECURSIVE TRAVERSAL >>";
cout<<"\n\n\t\t\t-----<<
MENU >>-----";
cout<<"\n\n\t\t\t1.Create
Tree";
cout<<"\n\t\t\t2.Preorder
Traversal";
cout<<"\n\t\t\t3.Inorder
Traversal";
cout<<"\n\t\t\t4.Postorder
Traversal";
cout<<"\n\t\t\t5.Exit";
cout<<"\n\n\t\t\t--------------------";
cout <<"\n\n\t\t\tEnter Your
Choice :";
cin>>ch;
switch(ch)
{
case 1:
root=t.create();
break;
case 2:
cout<<"\nPreorder Traversal
:";
t.preorder_nonrec(root);
break;
case
3:
cout<<"\nInorder Traversal
:";
t.inorder_nonrec(root);
break;
case
4:
cout<<"\npostorder Traversal
:";
t.postorder_nonrec(root);
break;
case
5:
exit(0);
break;
}
cout<<"\n\n\n\tDo you want to continue(y/n): ";
ans=getche();
}while(ans=='y'||ans=='Y');
break;
case 3:
exit(0);
break;
}
cout<<"\n\n\n\tDo you want to
continue(y/n): ";
ans=getche();
}while(ans=='y'||ans=='Y');
getch();
}
/*-------------<< End Of Main Function >>---------------*/
/*-----------------<< OUTPUT
SCREEN >>-------------------*/
<< BINARY TREE
TRAVERSAL >>
1.Recursive Traversal
2.Non_recursive
Traversal
3.Exit
---------------------------
Enter Your Choice : 1
<< RECURSIVE
TRAVERSAL >>
-----<< MENU
>>-----
1.Create Tree
2.Preorder Traversal
3.Inorder Traversal
4.Postorder Traversal
5.Exit
--------------------
Enter Your Choice :1
Enter a data[-1
for no data] : 10
Enter left child
of 10
Enter a data[-1
for no data] : 8
Enter left child
of 8
Enter a data[-1
for no data] : 7
Enter left child
of 7
Enter a data[-1
for no data] : -1
Enter right
child of 7
Enter a data[-1
for no data] : -1
Enter right
child of 8
Enter a data[-1
for no data] : 9
Enter left child
of 9
Enter a data[-1
for no data] : -1
Enter right
child of 9
Enter a data[-1
for no data] : -1
Enter right
child of 10
Enter a data[-1
for no data] : 11
Enter left child
of 11
Enter a data[-1
for no data] : -1
Enter right
child of 11
Enter a data[-1
for no data] : -1
Do you want to continue(y/n):y
<< RECURSIVE
TRAVERSAL >>
-----<< MENU
>>-----
1.Create Tree
2.Preorder Traversal
3.Inorder Traversal
4.Postorder Traversal
5.Exit
--------------------
Enter Your Choice :2
Preorder
Traversal : 10 8
7 9 11
Do you want to continue(y/n):y
<< RECURSIVE
TRAVERSAL >>
-----<< MENU
>>-----
1.Create Tree
2.Preorder Traversal
3.Inorder Traversal
4.Postorder Traversal
5.Exit
--------------------
Enter Your Choice :3
Inorder
Traversal : 7 8
9 10 11
Do you want to continue(y/n):y
<< RECURSIVE
TRAVERSAL >>
-----<< MENU
>>-----
1.Create Tree
2.Preorder Traversal
3.Inorder Traversal
4.Postorder Traversal
5.Exit
--------------------
Enter Your Choice :4
Postorder
Traversal : 7 9
8 11 10
Do you want to continue(y/n):n
Do you want to continue(y/n):y
<< BINARY TREE
TRAVERSAL >>
1.Recursive Traversal
2.Non_recursive
Traversal
3.Exit
---------------------------
Enter Your Choice : 2
<< NON_RECURSIVE
TRAVERSAL >>
-----<< MENU
>>-----
1.Create Tree
2.Preorder Traversal
3.Inorder Traversal
4.Postorder Traversal
5.Exit
--------------------
Enter Your Choice :1
Enter a data[-1
for no data] : 10
Enter left child
of 10
Enter a data[-1
for no data] : 5
Enter left child
of 5
Enter a data[-1
for no data] : 6
Enter left child
of 6
Enter a data[-1
for no data] : -1
Enter right
child of 6
Enter a data[-1
for no data] : -1
Enter right
child of 5
Enter a data[-1
for no data] : 7
Enter left child
of 7
Enter a data[-1
for no data] : -1
Enter right
child of 7
Enter a data[-1
for no data] : -1
Enter right
child of 10
Enter a data[-1
for no data] : 8
Enter left child
of 8
Enter a data[-1
for no data] : 9
Enter left child
of 9
Enter a data[-1
for no data] : -1
Enter right
child of 9
Enter a data[-1
for no data] : -1
Enter right
child of 8
Enter a data[-1
for no data] : 10
Enter left child
of 10
Enter a data[-1
for no data] : -1
Enter right
child of 10
Enter a data[-1
for no data] : -1
Do you want to continue(y/n):y
<< NON_RECURSIVE
TRAVERSAL >>
-----<< MENU
>>-----
1.Create Tree
2.Preorder Traversal
3.Inorder Traversal
4.Postorder Traversal
5.Exit
--------------------
Enter Your Choice :2
Preorder
Traversal : 10 5 6 7 8 9 10
Do you want to continue(y/n):y
<< NON_RECURSIVE
TRAVERSAL >>
-----<< MENU
>>-----
1.Create Tree
2.Preorder Traversal
3.Inorder Traversal
4.Postorder Traversal
5.Exit
--------------------
Enter Your Choice :3
Inorder
Traversal : 6 5 7 10 9 8 10
Do you want to continue(y/n):y
<< NON_RECURSIVE
TRAVERSAL >>
-----<< MENU
>>-----
1.Create Tree
2.Preorder Traversal
3.Inorder Traversal
4.Postorder Traversal
5.Exit
--------------------
Enter Your Choice :4
Postorder
Traversal : 6 7 5 9 10 8 10
Do you want to continue(y/n):n
Do you want to continue(y/n):y
<< BINARY TREE
TRAVERSAL >>
1.Recursive Traversal
2.Non_recursive
Traversal
3.Exit
---------------------------
Enter Your Choice : 3
No comments:
Post a Comment