516
Graphs and Trees
b has now been completely traversed. Backing up to a, it is time to traverse a’s
right subtree. A preorder traversal of the tree rooted at c causes c to be written,
then traversal goes to c’s left subtree, which results in f, h, and i being written.
Backing up to c, traversing c’s right subtree produces g. The subtree rooted at c
has now been completely traversed, and the algorithm terminates. The preorder
traversal produced
a, b, d, e, c, f, h, i, g
a
c
b
d
e
g
i
h
f
Figure 6.45
example 26
Using the tree of Figure 6.45 again, an inorder traversal (left, root, right), travels
down to the farthest left subtree, rooted at d. An inorder traversal here traverses the
left subtree (empty), writes out the root, d, then traverses the right subtree (empty).
Backing up the tree to b, b’s left subtree has been traversed, so it is time to write
out the root, b. Proceeding then to b’s right subtree, e is written. Backing up to a,
a’s left subtree has been traversed, so the root, a, is written out. Proceeding to a’s
right subtree, an inorder traversal says to go to the farthest left subtree first, which
would cause the h to be written. After that, f and i are written, then the root c, then
the right subtree of c, which is g. The nodes are therefore written as
d, b, e, a, h, f, i, c, g
A postorder traversal (left, right, root) would produce
d, e, b, h, i, f, g, c, a
example 27
Consider the tree shown in Figure 6.46, which is not a binary tree. A preorder traversal first writes the root a and then does a preorder traversal on the left subtree,
rooted at b. The preorder traversal of this subtree writes out b and then proceeds
to a preorder traversal of the left subtree of b, which is rooted at d. Node d is
written and then a preorder traversal of the left (the only) subtree of d, which
is rooted at i, is done. After writing out i, the traversal backs up to consider any
other subtrees of d; there are none.
Backing up to b, there are other subtrees of b. Processing these left to right,
nodes e and then f are written. All the subtrees of b have now been traversed; backing up to node a to look for subtrees farther to the right reveals a subtree rooted at
c. The algorithm writes out the root c, then moves to its leftmost subtree rooted at
reminDer
For a binary tree:
Preorder traversal is root,
left, right.
Inorder traversal is left,
root, right.
Postorder traversal is left,
right, root.
Graphs and Trees
b has now been completely traversed. Backing up to a, it is time to traverse a’s
right subtree. A preorder traversal of the tree rooted at c causes c to be written,
then traversal goes to c’s left subtree, which results in f, h, and i being written.
Backing up to c, traversing c’s right subtree produces g. The subtree rooted at c
has now been completely traversed, and the algorithm terminates. The preorder
traversal produced
a, b, d, e, c, f, h, i, g
a
c
b
d
e
g
i
h
f
Figure 6.45
example 26
Using the tree of Figure 6.45 again, an inorder traversal (left, root, right), travels
down to the farthest left subtree, rooted at d. An inorder traversal here traverses the
left subtree (empty), writes out the root, d, then traverses the right subtree (empty).
Backing up the tree to b, b’s left subtree has been traversed, so it is time to write
out the root, b. Proceeding then to b’s right subtree, e is written. Backing up to a,
a’s left subtree has been traversed, so the root, a, is written out. Proceeding to a’s
right subtree, an inorder traversal says to go to the farthest left subtree first, which
would cause the h to be written. After that, f and i are written, then the root c, then
the right subtree of c, which is g. The nodes are therefore written as
d, b, e, a, h, f, i, c, g
A postorder traversal (left, right, root) would produce
d, e, b, h, i, f, g, c, a
example 27
Consider the tree shown in Figure 6.46, which is not a binary tree. A preorder traversal first writes the root a and then does a preorder traversal on the left subtree,
rooted at b. The preorder traversal of this subtree writes out b and then proceeds
to a preorder traversal of the left subtree of b, which is rooted at d. Node d is
written and then a preorder traversal of the left (the only) subtree of d, which
is rooted at i, is done. After writing out i, the traversal backs up to consider any
other subtrees of d; there are none.
Backing up to b, there are other subtrees of b. Processing these left to right,
nodes e and then f are written. All the subtrees of b have now been traversed; backing up to node a to look for subtrees farther to the right reveals a subtree rooted at
c. The algorithm writes out the root c, then moves to its leftmost subtree rooted at
reminDer
For a binary tree:
Preorder traversal is root,
left, right.
Inorder traversal is left,
root, right.
Postorder traversal is left,
right, root.