Page 221 - DCAP407_DATA_STRUCTURE

Data Structure

A binary tree can be traversed in various ways. But the standard methods of traversal are:
1. Preorder traversal
2. Inorder traversal
3. Postorder traversal

12.2 Preorder Traversal
The preorder traversal of a non-empty binary tree is defined as follows:
1. First, visit the root node
2. Next, traverse the left sub-tree of root node in preorder
3. Finally, traverse the right sub-tree of root node in preorder

The figure 12.1 depicts the functioning of preorder traversal.

Figure 12.1: Preorder Traversal

The algorithm for preorder traversal is as follows:
Input – ROOT is the pointer to the root node of binary tree

Output – Visiting all nodes in preorder manner
Data Structure – Linked structure of binary tree
Steps
Preorder(Node *ptr)
1. ptr = ROOT //Start from ROOT
2. If (ptr ≠ null) then //If it is non-empty node

3. Visit (ptr) //Visit the node
4. Preorder (ptrllink) //Traverse left sub-tree of node in preorder
manner
5. Preorder (ptrrlink) //Traverse right sub-tree of node in preorder
manner
6. EndIf
7. Stop

Consider the binary tree shown in figure 12.2. The binary tree is represented
in such a way that the nodes in the binary tree are traversed in preorder
traversal manner.

214 LOVELY PROFESSIONAL UNIVERSITY