|
We have seen
traversal of graphs -- DFS and BFS. Similarly, when we want to visit
each and every element of a tree, there are three different ways to do
the traversal -- preorder, inorder and postorder. Remember, these
traversal methods are limited to Binary trees only and not for any other tree.
As you know every tree-node has a leftchild-link
:: Value-field :: rightchild-link structure, in INORDER
traversal, for every node in the tree we first visit its left sub-tree
(if its there); then visit the node itself; and then the right sub-tree
(if its there). Follow the example -
 |
We start from the root
i.e A. We are supposed to visit its left sub-tree then visit the
node itself and its right sub-tree. Here, A has a left sub-tree
rooted at B. So, I move to B and check for its left sub-tree (as
I'm supposed to do it for every node). Again, B has a left
sub-tree rooted at D. So, I check for D's left sub-tree now, but D
doesn't have any left sub-tree and thus I'll visit node D
first and check for its right sub-tree. As D doesn't have any
right sub-tree, we'll track back and visit node B;
and check for its right sub-tree. B has a right sub-tree rooted at
E and so we move to E. Well, E doesn't have any left or right
sub-trees so we just visit E
and track back to B. We already have visited B, so we track back
to A. We are yet to visit the node itself and so we visit A
first; then we go for checking the right sub-tree of A, which is
rooted at C. As C doesn't have any left or right tree we visit C.
So, the INORDER becomes - D
B E A C |
Similarly, in PREORDER, we visit the
current node first, then we visit its left sub-tree and then its right
sub-tree. In POSTORDER, for every node, we visit the left sub-tree first
and then the right sub-tree and finally the node itself.
Algorithm:-
Step-1: For the current
node check whether it has a left child. If it has then go to step-2 or
else step-3
Step-2: Repeat step-1 for this left child
Step-3: Visit (i.e printing in our case) the current node
Step-4: For the current node check whether it has a right child. If it
has then go to step-5
Step-5: Repeat step-1 for this right child
This is the recursive
algorithm for INORDER traversal.
C implementation:-
struct NODE
{
struct NODE *left;
int value;
struct NODE *right;
}
inorder(struct NODE *curr)
{
if(curr->left != NULL) inorder(curr->left); /*step-1
& step-2*/
printf("%d", curr->value); /*step-3*/
if(curr->right != NULL) inorder(curr->right); /*step-4*/
}
Related Operations:
Trees
– concepts
Binary tree creation
Traversals of a binary tree – preorder, inorder and postorder
Binary threaded tree
Non-recursive implementation of traversals
Expressions-to-Trees
Balanced trees / AVL trees – Creation and Balancing of a binary tree
Balanced m-way tree / B-tree – Creation and balancing
|
|
