Java Reference
In-Depth Information
23.13
A
postorder traversal
visits the root of a binary tree
after
visiting the nodes in the root's subtrees.
In particular, it visits nodes in the following order:
Visit all the nodes in the root's left subtree
Visit all the nodes in the root's right subtree
Visit the root
Figure 23-10 numbers the nodes in a binary tree in the order in which a postorder traversal vis-
its them. Recursively visiting the nodes in the left subtree results in visiting the leftmost leaf
first. We then visit that leaf's sibling and then their parent. After visiting all the nodes in the
root's left subtree, we visit the nodes in the root's right subtree in this recursive manner. Finally
we visit the root.
FIGURE 23-10
The visitation order of a postorder traversal
11
5
10
3
6
9
4
1
2
7
8
23.14
A
level-order traversal
—the last traversal we will consider—begins at the root and visits nodes
one level at a time. Within a level, it visits nodes from left to right. Figure 23-11 numbers the nodes
in a binary tree in the order in which a level-order traversal visits them.
FIGURE 23-11
The visitation order of a level-order traversal
1
3
2
4
5
6
7
8
9
10
11
The level-order traversal is an example of a
breadth-first traversal
. It follows a path that
explores an entire level before moving to the next level. The preorder traversal is an example of a
depth-first traversal
. This kind of traversal fully explores one subtree before exploring another.
That is, the traversal follows a path that descends the levels of a tree as deeply as possible until it
reaches a leaf.
