Tree traversal is used to print data in a binary tree. There are two main types of tree traversal. Depth-first and Breadth-first. Depth-first traversal can be further divided into three types: pre-order traversal, in-order traversal and post-order traversal. Lets get started.
Depth-first
Pre-order Traversal
- Visit the root.
- Traverse the left subtree in pre-order
- Traverse the right subtree in pre-order
In-order Traversal
- Traverse the left subtree in in-order
- Visit the root.
- Traverse the right subtree in in-order
Post-order Traversal
- Visit the root.
- Traverse the left subtree in post-order
- Traverse the right subtree in post-order
Those the main ideas behind the three depth-first traversals. To give you a clearer understanding, here are the basic algorithms for each traversal.
Pre-order traversal algorithm
In-order traversal algorithm
Post-order traversal algorithm
Breadth-first
Level-order Traversal
- Visit the nodes starting from the top until the bottom. Print them from left to right.
Now, let us look at some examples.
1.
Pre-order sequence: A B D G E C F
In-order sequence: G D B E A C F
Post-order sequence: G D E B F C A
Level-order sequence: A B C D E F G
2.
Pre-order sequence: A B D E G C F H
In-order sequence: D B G E A C F H
Post-order sequence: D G E B H F C A
Level-order sequence: A B C D E F G H
3.
Pre-order sequence: A B D F H I E G C
In-order sequence: F H I D B G E A C
Post-order sequence: I H F D G E B C A
Level-order sequence: A B C D E F G H I
If you followed the algorithms correctly, you would get the same answers. You could practice using those algorithms until you get a hang of it. I will add more examples in the future so that you can practice more cases. I will also post another tutorial about traversals that will teach you how to output the different sequences in a fast and simple way. But for now, that's all.
0 comments:
Post a Comment