Pages

Showing posts with label inorder traversal of tree without using recursion. Show all posts
Showing posts with label inorder traversal of tree without using recursion. Show all posts

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;
           
            }
       
       
        }
}