Binary Tree traversal C Program

Saturday, 1 March 2014



#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
typedef struct treenode
{
int data;
struct treenode *left,*right;
}treenode;
typedef struct stack
  { treenode *data[20];
    int top;
  }stack;
void init(stack *s)
 { s->top=-1;
 }
treenode * pop(stack *s)
 { treenode *p;
    p=s->data[s->top];
   s->top=s->top-1;
   return(p);
 }
void  push(stack *s, treenode *p)
  { s->top=s->top+1;
    s->data[s->top]=p;
  }
int empty(stack *s)
 { if(s->top==-1)
     return(1);
   return(0);
 }
int full(stack *s)
  {  if(s->top==19)
return(1);
     return(0);
  }

treenode *create();
void inorder(treenode *T);
void preorder(treenode *T);
void postorder(treenode *T);
void non_rec_preorder(treenode *T);
void non_rec_inorder(treenode *T);
void non_rec_postorder(treenode *T);
void main()
{
treenode *root=NULL,*p;
int x,op;
clrscr();
do
 { printf("\n\n1)Create\n2)Preorder(recursive)");
   printf("\n3)Inorder(recursive)\n4)Posorder(Recursive)");
   printf("\n5)Preorder(Non-Recursive)\n6)Inorder(Non-Recursive)");
   printf("\n7)Postorder(Non-Recursive\n8)Quit");
   printf("\nEnter Your Choice :");
   scanf("%d",&op);
    switch(op)
     {
case 1:root=create();break;
case 2: preorder(root);break;
case 3: inorder(root);break;
case 4: postorder(root);break;
case 5: non_rec_preorder(root);break;
case 6: non_rec_inorder(root);break;
case 7: non_rec_postorder(root);break;

    }
}while(op!=8);
}


void inorder(treenode *T)
{
if(T!=NULL)
{
inorder(T->left);
printf("%d  ",T->data);
inorder(T->right);
}
}

void preorder(treenode *T)
 {     if(T!=NULL)
 { printf("%d  ",T->data);
   preorder(T->left);
   preorder(T->right);
 }
 }
void postorder(treenode *T)
 {     if(T!=NULL)
 {
   postorder(T->left);
   postorder(T->right);
   printf("%d  ",T->data);
 }
 }
void non_rec_preorder(treenode *T)
 { stack s;
     init(&s);
     printf("\n");
     if(T==NULL)
      return;
      while(T!=NULL)
       {  printf("%d  ",T->data);
push(&s,T);
T=T->left;
       }
      while(!empty(&s))
       { T=pop(&s);
T=T->right;
while(T!=NULL)
 { printf("%d  ",T->data);
   push(&s,T);
   T=T->left;
 }
       }

 }
void non_rec_inorder(treenode *T)
 {   stack s;
     init(&s);
     printf("\n");
     if(T==NULL)
      return;
      while(T!=NULL)
       { push(&s,T);
T=T->left;
       }
      while(!empty(&s))
       { T=pop(&s);
printf("%d  ",T->data);
T=T->right;
while(T!=NULL)
 { push(&s,T);
   T=T->left;
 }
       }
 }
 void non_rec_postorder(treenode *T)
  { stack s,s1;
    treenode *flag;
     init(&s);init(&s1);
     printf("\n");
     if(T==NULL)
      return;
      while(T!=NULL)
       { push(&s,T);push(&s1,NULL);
T=T->left;
       }
      while(!empty(&s))
       { T=pop(&s);flag=pop(&s1);
if(flag!=NULL)
 printf("%d  ",T->data);
else
 {push(&s,T);push(&s1,(treenode*)1);
  T=T->right;
  while(T!=NULL)
  { push(&s,T);push(&s1,NULL);
    T=T->left;
  }
}
       }
  }



 treenode *create()
  { treenode *root,*b[31];
   int x,i;
 //For creation of a tree, tree is mapped to an array
   for(i=1;i<30;i++)
      b[i]=NULL;

  /*left child of ith node will be at 2*i and right child at 2*i+1*/
  printf("\nPlease Enter data of root node(-1 for does not exist): ");
  scanf("%d",&x);
  if(x==-1)
    return(root);
  b[1]=(treenode*)malloc(sizeof(treenode));
  b[1]->data=x;
  b[1]->left=b[1]->right=NULL;
  for(i=1;i<=15;i++)
   if(b[i]!=NULL)
    { printf("\nEnter Left child of %d (-1 for does not exist): ",b[i]->data);
      scanf("%d",&x);
      if(x!=-1)
       {
b[2*i]=(treenode*)malloc(sizeof(treenode));
b[2*i]->data=x;
b[2*i]->left=NULL;
b[2*i]->right=NULL;
b[i]->left=b[2*i];
       }
      printf("\nEnter right child of %d (-1 for does not exist) : ",b[i]->data);
      scanf("%d",&x);
     if(x!=-1)
       {b[2*i+1]=(treenode*)malloc(sizeof(treenode));
b[2*i+1]->data=x;
b[2*i+1]->left=NULL;
b[2*i+1]->right=NULL;
b[i]->right=b[2*i+1];
       }
    }

 return(b[1]);
}


OUTPUT:-

1)Create
2)Preorder(recursive)
3)Inorder(recursive)
4)Posorder(Recursive)
5)Preorder(Non-Recursive)
6)Inorder(Non-Recursive)
7)Postorder(Non-Recursive
8)Quit
Enter Your Choice :1

Please Enter data of root node(-1 for does not exist): 45

Enter Left child of 45 (-1 for does not exist): 23

Enter right child of 45 (-1 for does not exist) : 47

Enter Left child of 23 (-1 for does not exist): -1

Enter right child of 23 (-1 for does not exist) : -1

Enter Left child of 47 (-1 for does not exist): 56

Enter right child of 47 (-1 for does not exist) : -1

Enter Left child of 56 (-1 for does not exist): 90

Enter right child of 56 (-1 for does not exist) : 33

Enter Left child of 90 (-1 for does not exist): -1

Enter right child of 90 (-1 for does not exist) : -1

Enter Left child of 33 (-1 for does not exist): -1

Enter right child of 33 (-1 for does not exist) : -1

1)Create
2)Preorder(recursive)
3)Inorder(recursive)
4)Posorder(Recursive)
5)Preorder(Non-Recursive)
6)Inorder(Non-Recursive)
7)Postorder(Non-Recursive
8)Quit

Enter Your Choice :2
45  23  47  56  90  33

1)Create
2)Preorder(recursive)
3)Inorder(recursive)
4)Posorder(Recursive)
5)Preorder(Non-Recursive)
6)Inorder(Non-Recursive)
7)Postorder(Non-Recursive
8)Quit
Enter Your Choice :3
23  45  90  56  33  47

1)Create
2)Preorder(recursive)
3)Inorder(recursive)
4)Posorder(Recursive)
5)Preorder(Non-Recursive)
6)Inorder(Non-Recursive)
7)Postorder(Non-Recursive
8)Quit
Enter Your Choice :4
23  90  33  56  47  45

1)Create
2)Preorder(recursive)
3)Inorder(recursive)
4)Posorder(Recursive)
5)Preorder(Non-Recursive)
6)Inorder(Non-Recursive)
7)Postorder(Non-Recursive
8)Quit
Enter Your Choice :5

45  23  47  56  90  33

1)Create
2)Preorder(recursive)
3)Inorder(recursive)
4)Posorder(Recursive)
5)Preorder(Non-Recursive)
6)Inorder(Non-Recursive)
7)Postorder(Non-Recursive
8)Quit
Enter Your Choice :6

23  45  90  56  33  47

1)Create
2)Preorder(recursive)
3)Inorder(recursive)
4)Posorder(Recursive)
5)Preorder(Non-Recursive)
6)Inorder(Non-Recursive)
7)Postorder(Non-Recursive
8)Quit
Enter Your Choice :7

23  90  33  56  47  45

1)Create
2)Preorder(recursive)
3)Inorder(recursive)
4)Posorder(Recursive)
5)Preorder(Non-Recursive)
6)Inorder(Non-Recursive)
7)Postorder(Non-Recursive
8)Quit
Enter Your Choice :8

No comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...
Related Posts Plugin for WordPress, Blogger...
 

Most Reading

Labels