C Program on traversing binary tree

Once you have created a binary tree , you can display it’s contents in several ways. The process of moving through a tree is known as tree traversal. The traversal of a binary tree involves visiting each node in the tree exactly once. There are three popular methods of  binary tree traversal – inorder , preorder and post order traversal . Traversing a binary tree means visiting the root node , it’s left and right sub trees. The only difference among the methods is the order in which these three operations are performed.

To traverse a binary tree in in order , we perform the following operations :-

      1.Traverse the left sub tree in order

      2.Visit the root.

      3.Traverse the right sub tree in order.

To traverse a tree in pre order

      1.Visit the root.

      2.Traverse the left sub tree in pre order

      3.Traverse the right sub tree in pre order

To traverse a tree in post order

      1.Traverse the left sub tree in post order

      2.Traverse the right sub tree in post order

      3.Visit the root.

For example consider a tree whose nodes can contain operators and operands.

The postorder traversal of the tree gives the postfix form of the expression :- 78+

The preorder traversal of the tree gives the prefix form of the expression :-    +78

The inorder traversal of the tree gives the infix form of the expression :-        7+8

The following diagram represents a binary tree with 8 nodes  and we will see how this tree can be traversed in inorder, preorder and postorder methods.

  

Firstly we will see how this tree will be traversed in preorder method.In preorder root is traversed first, then the left subtree in preorder style and lastly the right subtree in preorder style.So the traverse will be

s (root , after this traversing through the left branch starts)à d (root )àa (left)àe (right)à (main left branch ends here , so traversing through the main right branch starts from here ) t (root)ày(no left node, so right branch)à u (left)à z ( right)  [ s d a e t y u z ]

In case of inorder method , left subtree is traversed first in inorder method , then the root and lastly the right subtree in inorder method.So the traverse will be like : a (left node of left subtree) àd (root) àe (right ) às ( left subtree ends here , so the root) à t ( no left node , so the root) àu (left )ày (root)àz (right) [a  d  e  s  t  u  y  z]

In case of postorder method , the style is left , right , root in postorder method. So if the above binary tree is traversed in postorder method then traverse will be like : a à e à d à (left subtree ends here , now traversing through right subtree will start) à u  à  z à y à t  à s  [ a  e  d  u  z  y  t  s ]

The C Program on traversal of a tree

# include< stdio.h>

# include< stdlib.h>

#include< conio.h>

struct node

{

char info;

struct node *left;

struct node *right;

};

void pre_order (struct node *n)

{

if (n)

{

printf(" %c", n->info);

pre_order(n->left);

pre_order(n->right);

}

}

void in_order (struct node *n)

{

if (n)

{

in_order(n->left);

printf(" %c", n->info);

in_order(n->right);

}

}

void post_order (struct node *n)

{

if (n)

{

post_order(n->left);

post_order(n->right);

printf(" %c", n->info);

}

}

struct node * create()

{

 struct node *node;

 char x;

 node=(struct node *)malloc(sizeof(struct node));

 printf("\nEnter the value:-");

 scanf("%c",&x);

 node->info=x;

 node->left=NULL;

 node->right=NULL;

 return node;

}

struct node *add(struct node *t,struct node *root)

{

if(root==NULL)

{

root=t;

return root;

}

else

{

if(t->info<=root->info)

{

root->left=add(t,root->left);

printf("\nAdded to left of node %c",root->info);

 }

else

{

 root->right=add(t,root->right);

 printf("\nAdded to right of node %c",root->info);

 }

 return root;

}

}

void  output(struct node *t, int level)

{

int i;

if (t)

{

output(t->right, level+1);

printf("\n");

for (i = 0; i < level; i++)

printf("   ");

printf("%c,%d (level)", t->info,level);

printf("\n");

 output(t->left, level+1);

}

}

void main()

{

int info, xx=0;

char choice='y';

struct node *t,*root=NULL,*rr;

clrscr();

while(choice != 'n')

{

t=create ();

 if(xx==0)

 rr=t;

xx++;

printf("\n Tree is ");

root=add(t,root);

output(rr,0);

fflush(stdin);

printf("\n Enter choice--'n' to break:");

scanf("%c",&choice);

}

printf("\n Pre-order traversal\n");

pre_order (rr);

printf("\n In-order traversal\n");

in_order (rr);

printf("\n Post-order traversal\n");

post_order (rr);

getch();

}