Page 229 - DCAP407_DATA_STRUCTURE

Data Structure

---->T7 T8 T4 T2 µT9 LRNT5T6 LRNT3 T1//After visiting T5 LRN
---->T7 T8 T4 T2 µµT9T5T6 LRNT3 T1//After visiting T9 LRN

---->T7 T8 T4 T2 T9 T5µµT6 T3 T1//After visiting T6 LRN
---->T7 T8 T4 T2 T9 T5T6 T3 T1
Hence, the postorder traversal for the tree shown in figure 12.2 is T7 T8 T4 T2
T9 T5 T6 T3 T1
The post order traversal starts with left sub-tree, then moves to the right sub-tree, and then finally to the
root. Considering the postorder traversal using stacks, each node is stacked twice during the traversal of
left sub-tree and right sub-tree. To distinguish between the left sub-tree and right sub-tree, a traversing
flag is used. During the traverse of right sub-tree, flag is set to 1. This helps in checking the flag field of
the corresponding node. If the flag of a node is negative, then right sub-tree is traversed, else the left
sub-tree is traversed. The algorithm for postorder of binary tree using stacks is as follows:
Step 1: If the tree is empty then
{

write (“Empty tree”)
return
}
else
Initialize the stack and pointer value to the root of tree
Step 2: Start an infinite loop and repeat till step 5

Step 3: Repeat while pointer value is no NULL, stack current pointer value. Set pointer value to left sub-
tree
Step 4: Repeat while top pointer on stack is negative
Pop pointer off stack
write (value of pointer)

If the stack is empty
then return
Step 5: Set pointer value to the right sub-tree of the value on top of the stack.
Step 6: Stack the negative value of the pointer to right sub-tree

Program for inorder, preorder and postorder tree traversals
#include<stdio.h>
#include<conio.h>

struct node //Declare node as struct variable
{
int data; //Declare data with data type int
struct node *right, *left; // The node stores pointers to the right and left sub-trees.
}root,*p,*q; // declare root as a variable of type node and p and q
as pointers to node

222 LOVELY PROFESSIONAL UNIVERSITY