Tree Traversals implementation in C++
|
|
|
Download Attachment
|
#include < iostream.h>
#include < conio.h>
#include < malloc.h>
struct tree
{
struct tree *left;
int info;
struct tree *right;
}*root,*ptr,*newnode,*par,*stack[100];
int loc=0;
void create();
void find(int);
void preorder();
void inorder();
void postorder();
void main()
{
int i;
clrscr();
for(i=0;i<5;i++)
{
create();
}
preorder();
inorder();
postorder();
getch();
}
void create()
{
int item;
cout<<"\nEnter the info: ";
cin>>item;
find(item);
if(loc==1)
{
}
else
{
newnode=(struct tree*)malloc(sizeof(struct tree));
newnode->info=item;
newnode->left=NULL;
newnode->right=NULL;
if(par==NULL)
{
root=newnode;
}
else if(iteminfo)
{
par->left=newnode;
}
else
{
par->right=newnode;
}
}
}
void find(int item)
{
struct tree *save;
if(root==NULL)
{
loc=0;
par=NULL;
return;
}
else if(item==root->info)
{
loc=1;
par=NULL;
return;
}
else if(iteminfo)
{
ptr=root->left;
save=root;
}
else
{
ptr=root->right;
save=root;
}
while(ptr!=NULL)
{
if(item==ptr->info)
{
loc=1;
par=save;
return;
}
else if(iteminfo)
{
save=ptr;
ptr=ptr->left;
}
else
{
save=ptr;
ptr=ptr->right;
}
}
loc=0;
par=save;
}
void preorder()
{
int top=0;
stack[0]=NULL;
ptr=root;
cout<<"\nPreorder Traversal of Tree is:\n";
while(ptr!=NULL)
{
cout<info<<" ";
if(ptr->right!=NULL)
{
top=top+1;
stack[top]=ptr->right;
}
if(ptr->left!=NULL)
{
ptr=ptr->left;
}
else
{
ptr=stack[top];
top=top-1;
}
}
}
void inorder()
{
int top=0;
stack[0]=NULL;
ptr=root;
cout<<"\nInorder Traversal of Tree is:\n";
again:
while(ptr!=NULL)
{
top=top+1;
stack[top]=ptr;
ptr=ptr->left;
}
ptr=stack[top];
top=top-1;
while(ptr!=NULL)
{
cout<info<<" ";
if(ptr->right!=NULL)
{
ptr=ptr->right;
goto again;
}
ptr=stack[top];
top=top-1;
}
}
void postorder()
{
int top=0,temp,track[100];
stack[0]=NULL;
track[0]=-1;
ptr=root;
cout<<"\nPostorder Traversal of Tree is:\n";
again:
while(ptr!=NULL)
{
top=top+1;
stack[top]=ptr;
track[top]=0;
if(ptr->right!=NULL)
{
top=top+1;
stack[top]=ptr->right;
track[top]=1;
}
ptr=ptr->left;
}
ptr=stack[top];
temp=track[top];
top=top-1;
while(temp==0)
{
cout<info<<" ";
ptr=stack[top];
temp=track[top];
top=top-1;
}
if(temp==1)
{
top=top+1;
track[top]=0;
top=top-1;
goto again;
}
}
|
|
|
|
|
|
|
|
|
|
Share this article
| Print |
Article read by 3393 times
|
|
|
|