Pages

Monday 27 August 2012

Traversing a tree inorder and post and preorder without using recursion

Traversing a tree inorder and post and preorder using non recursive technique:



#include<stdio.h>
#include<conio.h>
#include<malloc.h>
#define STACKSIZE 20

struct treenode
{
    int data;
    struct treenode *left;
    struct treenode *right;
} *root=NULL;

// stack functions
int top=-1; struct treenode *stack[STACKSIZE];
void push(struct treenode *temp)
{
    if(top<STACKSIZE)
    {
        top++;
        stack[top]=temp;
        }
        else
        printf("stack overflow");
}

int pop()
{
    int i;
    if(top==-1)
    {
        printf("stackunderflow");
        }
    else
    i=stack[top--];
    return i;
   
}
int isstackempty()
{
    if(top==-1)
    return 1;
    else return 0;
}
//end of stackfunctions

struct treenode * buildtree()
{
    struct treenode *temp1,*temp2,*temp3,*temp4,*temp5;
     root=(struct treenode *)malloc(sizeof(struct treenode));
      temp1=(struct treenode *)malloc(sizeof(struct treenode));
       temp2=(struct treenode *)malloc(sizeof(struct treenode));
        temp3=(struct treenode *)malloc(sizeof(struct treenode));
         temp4=(struct treenode *)malloc(sizeof(struct treenode));
    
     root->data=4;
     root->left=temp1;
     temp1->data=5;
     root->right=temp2;
     temp2->data=6;
     temp1->left=temp3;
     temp3->data=7;
     temp3->left=temp3->right=NULL;
     temp1->right=temp4;
     temp4->data=8;
     temp4->left=NULL;
     temp4->right=NULL;
      temp2->left=temp2->right=NULL;
  printf("\n tree buildedsuccessfull"); 
       return root;
}

 void inorder(struct treenode *root)
 {
    struct treenode *temp;
    temp=root;
    while(1)
    {
    while(temp!=NULL)
       {
            push(temp);
            temp=temp->left;
        }
    if(isstackempty()) return;
    temp=pop();
    printf("%d    ",temp->data);
    temp=temp->right;
     }
  }   
void preorder(struct treenode *root)
 {
    struct treenode *temp;
    temp=root;
    while(1)
    {
    while(temp!=NULL)
       { 
            printf("%d   ",temp->data);
            push(temp);
            temp=temp->left;
        }
    if(isstackempty()) return;
    temp=pop();
    temp=temp->right;
     }
  }   
       
void postorder(struct treenode *root)
 {
    struct treenode *temp,*q;
    temp=root;
    while(1)
    {
    while(temp!=NULL)
       {
            push(temp);
            temp=temp->left;
        }
    if(isstackempty()) return;
    temp=pop();
    if(((int)temp)<0)
    {
        temp=((unsigned int)temp)*-1;
    printf("%d    ",temp->data);
    temp=NULL;
     }
     else
     {
            q=temp;
            temp=temp->right;
        q=((unsigned int)q)*-1;
        push(q);
            }
  }
}
 
     
//main
void main()
{
    int k=1,j;
    struct treenode *root;
    while(k)
    {
        printf("\n enter 1 to build tree");
        printf("\n enter 2 to print preorder");
        printf("\n enter 3 to print inorder");
        printf("\n enter 4 print postoreder");
        scanf("%d",&k);
       
        switch(k)
        {
         case 1:
       
            root=buildtree();
            break;
           
        case 2:
            preorder(root);
            break;
       
           case 3:
                  inorder(root);
                break;
           
        case 4:
            postorder(root);
            break;
           
            }
       
       
        }
}

No comments: