Section 6.2 Trees and Their Representations
517
praCTiCe 21 Do a preorder, inorder, and postorder traversal of the tree in Figure 6.47.
a
d
b
e
c
f g
i
h
Figure 6.47
■
g and writes out g. Processing the subtrees of g, the nodes j and k are written; then
backing up to c, its remaining subtree is processed, producing h. Node c has no
other subtrees; backing up to a, a has no other subtrees, and the algorithm terminates. The list of nodes in preorder traversal is
a, b, d, i, e, f, c, g, j, k, h
To do an inorder traversal of the tree in Figure 6.46, process left subtrees
first, leading down to node i, which has no subtrees. Therefore i is written out.
Backing up to d, the left (only) subtree of d has been traversed, so d is written out.
Since node d has no further subtrees, the algorithm backs up to b. The left subtree
of b has been processed, so b is written out and then its remaining subtrees are
traversed, writing out e and f. Backing up to a, a is written out, and then the right
subtree of a is processed, leading to nodes j, g, k, c, and h, in that order, and we are
done. Thus the inorder list of nodes is
i, d, b, e, f, a, j, g, k, c, h
The following list of nodes results from a postorder traversal:
i, d, e, f, b, j, k, g, h, c, a
a
c
b
d
e
f g
i
j
k
h
Figure 6.46