Java Reference
In-Depth Information
Note:
Traversals of a binary tree
A preorder traversal visits the root of a binary tree before visiting the nodes in its two subtrees.
An inorder traversal visits the root between visiting the nodes in its two subtrees.
A postorder traversal visits the root after visiting the nodes in its two subtrees.
A level-order traversal visits nodes from left to right within each level of the tree, beginning
with the root.
Question 7
Suppose that visiting a node means simply displaying the data in the node. What
are the results of each of the following traversals of the binary tree in Figure 23-2? Preorder,
postorder, inorder, and level order.
A general tree has traversals that are in level order, preorder, and postorder. An inorder traversal is
not well defined for a general tree.
A level-order traversal visits nodes level by level, beginning at the root. This traversal is just
like a level-order traversal of a binary tree, except that nodes in a general tree can have more than
two children each.
A preorder traversal visits the root and then visits the nodes in each of the root's subtrees. A
postorder traversal first visits the nodes in each of the root's subtrees and then visits the root last.
Figure 23-12 gives an example of a preorder traversal and a postorder traversal for a general tree.
FIGURE 23-12
The visitation order of two traversals of a general tree:
(a) preorder; (b) postorder
(a)
(a)
(b)
(b)
1
1
16
16
2
2
8
8
10
10
16
16
6
6
8
8
14
14
15
15
3
3
15
15
4
4
13
13
7
7
9
9
11
11
12
12
5
5
7
7
9
9
12
12
6
6
4
4
5
5
14
14
1
1
2
2
3
3
10
10
11
11
13
13
Postorder traversal
Postorder traversal
Preorder traversal
Preorder traversal
Question 8
In what order will a level-order traversal visit the nodes of the tree in Figure 23-12?
Trees come in many shapes and have varied applications. Writing one Java interface for an ADT tree
that satisfies every use would be an unwieldy task. Instead we will write several interfaces that we can
combine as needed for a particular application. We will include these interfaces in a package that also
