Tuesday 15 October 2013

Traverse tree without recursion

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

Blogger Widgets