Java Reference
In-Depth Information
The left subtree of this tree stores the value
0
and has an empty right subtree. We
know that each of the occurrences of
<left>
is going to be replaced by an appropri-
ate traversal:
•
Preorder traversal:
[2, 0,
<left-left>
,
<right>
]
•
Inorder traversal:
[
<left-left>
, 0, 2,
<right>
]
•
Postorder traversal:
[
<left-left>
, 0,
<right>
, 2]
Then each occurrence of
<left-left>
would be replaced with an appropriate tra-
versal for the subtree that has
7
as its root. The following are the complete traversal
results:
•
Preorder traversal:
[2, 0, 7, 6, 5, 3, 1, 8, 9, 4]
•
Inorder traversal:
[6, 7, 5, 0, 2, 8, 1, 3, 9, 4]
•
Postorder traversal:
[6, 5, 7, 0, 8, 1, 4, 9, 3, 2]
There is another way to find the three different traversals. Imagine that each
node in the tree is an island and that each link is a solid wall. Then imagine a sail-
boat sailing in from the upper left part of the tree and sailing around the tree,
always hugging the coastline, and continuing around until it sails past the root on
the right-hand side:
2
0
3
7
1
9
6
5
8
4
The sailboat sails past the root node three different times. It passes it first on the
left, then underneath, and then on the right. If you think about it the right way,
you'll realize that the sailboat passes each of the nodes three times. Even for a leaf
node like the one on the left that stores
6
, it has to pass on the left, underneath, and
on the right. It does them all in a row for a leaf node, but it still passes by in all
three directions.
If you print the values as the sailboat passes them on the left, you get a preorder
traversal. If you print the values as the sailboat passes underneath, you get an inorder
traversal. And if you print the values as the sailboat passes them on the right, you get
a postorder traversal. This technique is useful for double-checking your understand-
ing of the different traversals.
Search WWH ::
Custom Search