Trees | tree traversals, pre-order post order and in-order traversal | set 2

Introduction:

In a previous post, we have seen how to construct a basic tree[we constructed binary tree].If you don't have any experience with writing tree structures, then you may very well visit the first post and then continue this one. Now, we want to show what are the ways to traverse a binary tree. There are mainly 3 ways to traverse the binary tree. The ways are in-order, pre-order and post-order. 

Algorithms:

The in-order traversal is a process of traversing the left subtree first, then the root and at the last, right subtree. The algorithm is recursive; i.e. the algorithm of in-order is similar:

Traverse left sub-tree

traverse the root

Traverse right sub-tree

Here, as the left-subtree will be traversed again in the same way with the left node considered as root. Therefore, the program works recursively.

The post-order is again a recursive. But in this case, it traverses the root at the last. Therefore it is called post-order. The algorithm is:

Traverse left sub-tree

Traverse right sub-tree

traverse the root

The pre-order is again a recursive one. In this case, the root is traversed first and the rest is same. Therefore, it is called pre-order. The algorithm in this case is:

traverse the root

Traverse left sub-tree

Traverse right sub-tree

Programming implementation:

Now, I present a programming implementation of the same. Look below:

#include <stdio.h>

#include <stdlib.h> //without this calloc can not be used

typedef struct node //tree structure definition

{

 int data;

 struct node *left;

 struct node *right;

}branch; // here we have set it as branch

branch *createnode(int value) //createnode is the function to create a node of the tree and return it

{  

 branch *stick;

 stick=(branch *)calloc(1,sizeof(branch));

 stick->data=value;

 stick->left=NULL;

 stick->right=NULL;

 return stick;

}

void pre_order(branch *root)

{

if(root==NULL)

{return;}

printf("%d ",root->data);

pre_order(root->left);

pre_order(root->right);

}

void post_order(branch *root)

{

if(root==NULL)

{return;}

post_order(root->left);

post_order(root->right);

printf("%d ",root->data);

}

void in_order(branch *root)

{

if(root==NULL)

{return;}

in_order(root->left);

printf("%d ",root->data);

in_order(root->right);

}

//driver program

int main(void)

{

    branch *root=createnode(2);

    root->left=createnode(5);

    root->right=createnode(1);

    root->left->left=createnode(4);

    root->left->right=createnode(9);

    root->right->left=createnode(0);

    root->right->right=createnode(6);

    printf("the preorder representation is:");

    pre_order(root);

    printf("\n the in-order representation is:");

    in_order(root);

    printf("\n the post-order representation is:");

    post_order(root);

     return 0;

}

Success #stdin #stdout 0s 9424KB

the preorder representation is:2 5 4 9 1 0 6 
 the in-order representation is:4 5 9 2 0 1 6 
 the post-order representation is:4 9 5 0 6 1 2