Posts
IMPLEMENTATION TREE TRAVERSAL
(INORDER – PREORDER – POST ORDER)
Exercise.No:6
NOTE:
* For any queries comment below, instantly the solution will be posted *
TO LEARN C PROGRAMMING FOLLOW THIS YOUTUBE CHANNEL: Code with u - YouTube
AIM:
To write the program to implement the Tree Traversal.
ALGORITHM:
1. Read the integers
2. Create the functions for preorder, in order and post order
3. Perform push and pop operations.
FOR INORDER
Inorder(pos t)
T!=null
Inorder(t-> left)
Printf(“%s”, t->data);
Inorder(t->right)
FOR PREORDER
Preorder(pos t)
T!=null
Printf(“%s”, t->data);
Preorder(t->left)
Inorder(t->right)
FOR POSTORDER
Postorder(pos t)
Postorder(t->left)
postorder(t->right)
Printf(“%s”, t->data);
4. Visit in the order left, root, right,
5. Display the visited nodes
PROGRAM:
// program showing various operations on Expression tree. Tree is created
// from a postfix expression
#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
typedef struct treenode
{
char 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;
}
treenode *create();
void inorder(treenode *T);
void preorder(treenode *T);
void postorder(treenode *T);
void main()
{
treenode *root=NULL,*p;
int x, op;
do
{
printf("\n\n1)Create\n2)Preorder");
printf("\n3)Inorder\n4)Postorder\n5)Quit");
printf("\n Enter 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;
}
}while(op<5);
}
void inorder(treenode *T)
{
if(T!=NULL)
{
inorder(T->left);
printf("%c", T->data);
inorder(T->right);
}
}
void preorder(treenode *T)
{ if(T!=NULL)
{ printf("%c", T->data);
preorder(T->left);
preorder(T->right);
}
}
void postorder(treenode *T)
{ if(T!=NULL)
{
postorder(T->left);
postorder(T->right);
printf("%c", T->data);
}
}
treenode * create()
{
char a[50];
int i;
treenode *p,*q,*root;
stack s;
init(&s);
printf("\n Enter a postfix expression : ");
scanf("%s",&a);
for(i=0;a[i]!='\0';i++)
{
if(isalnum(a[i]))
{
p=(treenode*)malloc(sizeof(treenode));
p->left=p->right=NULL;
p->data=a[i];
push(&s,p);
}
else
{
q=pop(&s);
p=pop(&s);
root=(treenode*)malloc(sizeof(treenode));
root->left=p;
root->right=q;
root->data=a[i];
push(&s,root);
}
}
root=pop(&s);
return(root);
}
OUTPUT:
1)Create
2)Preorder
3)Inorder
4)Postorder
5)Quit
Enter Your Choice :1
Enter a postfix expression: pk-ap+*
1)Create
2)Preorder
3)Inorder
4)Postorder
5)Quit
Enter Your Choice :2
*-pk+ap
1)Create
2)Preorder
3)Inorder
4)Postorder
5)Quit
Enter Your Choice :3
p-k*a+p
1)Create
2)Preorder
3)Inorder
4)Postorder
5)Quit
Enter Your Choice :4
pk-ap+*
1)Create
2)Preorder
3)Inorder
4)Postorder
5)Quit
Enter Your Choice :5
RESULT:
Thus, the program Tree Traversal was implemented and executed successfully.
