Page 227 - DCAP407_DATA_STRUCTURE

Data Structure

(iii) If the entered digit is equal to the info stored in the node, then it displays a message
“Duplicates node: program exited” and exits.
(d) The function inorder() is then defined. It accepts a pointer to a tree and a digit to be inserted
in the tree as parameters
(i) It checks if the tree is empty or non-empty.
(ii) If the tree is non-empty, it traverses the left sub-tree first, then prints the value of the
variable info stored in the node and then traverses the right sub-tree.
In the inorder traversal, the nodes traversal starts with visiting right sub-tree, root and left sub-tree.
While traversing using stacks, the left sub-tree in a binary tree is traversed by moving down the tree
towards left and then pushing node with data into the stack until the left sub-tree pointer node is
NULL. Once the left sub-tree is traversed, the stack becomes non-empty, then we can pop the elements
from the stack and print the data, and then traverse the pointer towards right sub-tree. This process
continues until right sub-tree is NULL. The algorithm for inorder traversal using stacks is as follows:
Step 1: If the tree is empty then
{
write( “empty tree”)
return
}

else
Place the pointer to the root of the tree on the stack
Step 2: Repeat step 4 while stack is not empty.
Step 3: Repeat while pointer value is not NULL and stack the pointer to the left sub-tree.
Repeat while the pointer is not NULL.
Write (Node containing data)
If the right sub-tree is not empty, then stack the pointer to the right sub-tree and set pointer to the right
sub-tree.

In the inorder traversal, if we replace left by right and right by left, converse inorder
traversal is obtained. The converse inorder traversal displays the tree contents in a tree
fashion.

12.4 Postorder Traversal
The postorder traversal of a non-empty tree is defined as follows:

1. First, traverse the left sub-tree of the root node in postorder.
2. Next, the right sub-tree of the root node in postorder.
3. Finally, visit the root node.

220 LOVELY PROFESSIONAL UNIVERSITY