Program - Binary tree traversal
Preorder traversal of
binary tree
preorder(node)
Step-1 : [do through step 3]
if
node ≠ NULL
output
info[node]
Step-2 : call preorder(left_child[node])
Step-3 : call preorder(right_child[node])
Step-4 : exit
Inorder traversal of
binary tree
inorder(node)
Step-1 : [do through step 4]
if
node ≠ NULL
Step-2 : call inorder(left_child[node])
Step-3
: Output info[node]
Step-4 : call inorder(right_child[node])
Step-5 : exit
Postorder traversal of
binary tree
postorder(node)
Step-1 : [do through step 4]
if
node ≠ NULL
Step-2 : call postorder(left_child[node])
Step-3 : call postorder(right_child[node])
Step-4
: output info[node]
Step-5 : exit
Program
// Traversing
binary tree
// (preorder, inorder ,postorder
#include<stdio.h>
#include<conio.h>
struct tree
{
char info;
struct
tree *leftchild;
struct
tree *rightchild;
};
struct tree * create_tree(char*,int,int);
void output(struct tree*,int);
void preorder(struct tree *);
void inorder(struct tree *);
void postorder(struct tree *);
struct tree * create_tree(char *list,int low,int
up)
{
struct
tree *node;
int
mid=(low+up)/2;
node=(struct
tree *)malloc(sizeof(struct tree));
node->info=list[mid];
if(low>=up)
{
node->leftchild=NULL;
node->rightchild=NULL;
return(node);
}
if(low<=mid-1)
node->leftchild=create_tree(list,low,mid-1);
else
node->leftchild=NULL;
if(mid+1<=up)
node->rightchild=create_tree(list,mid+1,up);
else
node->rightchild=NULL;
return(node);
}
void output(struct tree *t,int level)
{
int i;
if(t)
{
output(t->rightchild,level+1);
printf("\n");
for(i=0;i<level;i++)
printf("
");
printf("%c",t->info);
output(t->leftchild,level+1);
}
}
void preorder(struct tree *node)
{
if(node)
{
printf("%c",node->info);
preorder(node->leftchild);
preorder(node->rightchild);
}
}
void inorder(struct tree *node)
{
if(node)
{
inorder(node->leftchild);
printf("%c",node->info);
inorder(node->rightchild);
}
}
void postorder(struct tree *node)
{
if(node)
{
postorder(node->leftchild);
postorder(node->rightchild);
printf("%c",node->info);
}
}
void main()
{
char
list[100];
int
num=0;
char
info,ch;
struct
tree *t=(struct tree *)malloc(sizeof(struct tree));
clrscr();
t=NULL;
printf("Input
choice 'b' to break:");
ch=getchar();
fflush(stdin);
while(ch!='b')
{
printf("Input
information of the node:");
scanf("%c",&info);
list[num++]=info;
fflush(stdin);
printf("Input
choice 'b' to break:");
ch=getchar();
fflush(stdin);
}
printf("\nNumber
of elements in the list is %d",num);
num--;
t=create_tree(list,0,num);
output(t,1);
printf("\n\nPre-order
Traversal: \n");
preorder(t);
printf("\n\nIn-order
Traversal: \n");
inorder(t);
printf("\n\nPost-order
Traversal: \n");
postorder(t);
getch();
}
