IT is tough to traverse tree without recursion . It needed strong concept that how things going on during traversal. Anyway you can easily dit using stack. see this video .......
I your doubt is steel not clear ..see program carefully & do all operation of program step by step
C program :
#include<stdio.h>
#include<stdlib.h>
struct node
{
struct node *left;
struct node *right;
char data;
};
typedef struct node node;
void insert(node **,char);
node *stack[100]; //use in none recursive traversal :
int top=-1;
main()
{
node *root=NULL;
int n,i;
char m;
printf("\n no of node u want :");
scanf("%d",&n);
getchar();
for(i=0;i<n;i++)
{
printf("\n inter %dth data elemnt :",i+1);
scanf("%c",&m);
getchar();
insert(&root,m);
}
printf("\n preorder traversal without rec :\n");
pre_without_rec(root);
printf("\n inorder traversal without rec :\n");
in_without_rec(root);
printf("\n postorder traversal without rec :\n");
post_without_rec(root);
}
void insert(node **tr,char num)
{
if(*tr==NULL)
{
*tr=(node*)malloc(sizeof(node));
(*tr)->data=num;
(*tr)->left=NULL;
(*tr)->right=NULL;
}
else
{
if(num< (*tr)->data)
{
insert(&(*tr)->left,num);
}
else
{
insert(&(*tr)->right,num);
}
}
}
pre_without_rec(node *tr)
{
stack[++top]=tr;
while(top!=-1)
{
tr=stack[top--];
if(tr!=NULL)
{
printf(" %c ",tr->data);
stack[++top]=tr->right;
stack[++top]=tr->left;
}
}
}
in_without_rec(node *tr)
{
while(top!=-1 || tr!=NULL)
{
if(tr!=NULL)
{
stack[++top]=tr;
tr=tr->left;
}
else
{
tr=stack[top--];
printf(" %c ",tr->data);
tr=tr->right;
}
}
}
post_without_rec(node *tr)
{
int flag[100];
int top_prev;
stack[++top]=NULL;
do
{
while(tr!=NULL)
{
stack[++top]=tr;
flag[top]=1;
if(tr->right!=NULL)
{
stack[++top]=tr->right;
flag[top]=-1;
}
tr=tr->left;
}
top_prev=top;
tr=stack[top--];
while(flag[top_prev]==1)
{
printf(" %c ",tr->data);
top_prev=top;
tr=stack[top--];
}
}while(tr!=NULL);
}
OUTPUT :traverse tree without recursion |
No comments:
Post a Comment
THANKS FOR UR GREAT COMMENT