written 2.5 years ago by |
Traversing a binary tree is a process of visiting each node in the tree exactly once in a symmetric way.
Unlike linear data structures in which the elements are traversed sequentially, tree is a non linear data structure in which the elements can be traversed in many different ways.
There are different algorithms for tree traversal:
A. Pre-order algorithm:
To traverse a non empty binary tree in pre order, the following operations are performed recursively at each node.
The algorithm starts with the root node of the tree and continues by,
visiting the root node.
Traversing the left sub tree.
Traversing the right sub tree.
- The ps order traversal of the tree is given as A, B, C. root node first, the left sub tree next and then the right sub tree.
- In this algorithm, the left sub tree is always traversed before the right sub tree.
Example.
Preorder traversal order: A, B D, G, H ,C , E , C , F , I , J ,K .
B. In order algorithm:
To traverse a non empty binary tree in in order, the following operations are performed recursively at each node.
The algorithm starts with the next node of the tree and continues by :
Traversing the left sub tree.
Visiting the root node.
Traversing the right sub tree.
- The in - order traversal of the tree is given as B, A and C.
- In this algorithm, left sub tree first, the root node next and then the right sub tree will be traversed.
In-order traversal order:
G,D,H,L,B,E,A,C,I,F,K,J.
C. Post order algorithm:
To traverse a non empty binary tree in post order, the following operations are performed recursively at each node.
The algorithm starts with the root node of the tree and continues by,
Traversing the left sub tree.
Traversing the right sub tree.
Visiting the root node.
- The post order traversal of the tree is B, C and A.
- In this algorithm, the left sub tree is always traversed before the right sub tree, and the root node.
Post-order traversal order:
G,L,H,D,E,B,I,K,J,F,C,A.