Java Reference
In-Depth Information
Visiting the nodes in the left subtree before visiting those in the right subtree is simply a conven-
tion. Whether we visit the root before, between, or after visiting these two subtrees, however,
defines three common orders for a traversal.
In a
preorder traversal
, we visit the root
before
we visit the root's subtrees. We then visit all
the nodes in the root's left subtree before we visit the nodes in the right subtree. Figure 23-8 num-
bers the nodes in a binary tree in the order in which a preorder traversal visits them. After first vis-
iting the root, we visit the nodes in the root's left subtree. Since this subtree is a binary tree,
visiting its nodes in preorder means that we visit its root before visiting its left subtree. The tra-
versal continues in this recursive manner until all nodes are visited.
FIGURE 23-8
The visitation order of a preorder traversal
1
2
7
6
3
8
9
4
5
10
11
23.12
An
inorder traversal
visits the root of a binary tree
between
visiting the nodes in the root's sub-
trees. In particular, it visits nodes in the following order:
Visit all the nodes in the root's left subtree
Visit the root
Visit all the nodes in the root's right subtree
Figure 23-9 numbers the nodes in a binary tree in the order in which an inorder traversal visits
them. Recursively visiting the nodes in the left subtree results in visiting the leftmost leaf first. We
visit that leaf's parent next and then the parent's right child. We visit the tree's root after we have
visited all of the nodes in the root's left subtree. Finally, we visit the nodes in the root's right subtree
in this recursive manner.
FIGURE 23-9
The visitation order of an inorder traversal
6
4
8
2
5
7
10
1
3
9
11
