Page 115 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes }
}
Consider the following example.
Given the preorder and inorder traversal of a binary tree. Draw the tree and write down its
postorder traversal.
Inorder: Z, A, Q, P, Y, X, C, B
Preorder: Q, A, Z, Y, P, C, X, B
To obtain the binary tree take the first node in preorder, it is a root node, we then search for this

node in the inorder traversal, all the nodes to the left of this node in the inorder traversal will be
the part of the left sub-tree, and all the nodes to the right of this node in the inorder traversal will
be the part of the right sub-tree. We then consider the next node in the preoder, if it is a part of
the left sub-tree, then we make it as left child of the root, otherwise if it is part of the right sub-tree
then we make it as part of right sub-tree. This procedure is repeated recursively to get the tree
shown below in Figure 5.11:
Figure 5.11: A Unique Binary Tree Constructed using the Inorder and Postorder

Q

A Y

P
Z C

X B

The post order for this tree is:
Z, A, P, X, B, C, Y, Q

The following function counts the number of leaf node in a binary tree.
int count(tnode *p)
{
if(p == NULL)
count = 0;
else
if((p->1child == NULL) && (p->rchild == NULL))
count = 1;
else
count = count(p->1child) + count(p->rchild);
}
The following procedure swaps the left and the right child of every node of a given binary tree.

void swaptree(tnode *p)
{

110 LOVELY PROFESSIONAL UNIVERSITY