Section 6.2 Trees and Their Representations
515
In inorder traversal, the left subtree is processed by an inorder traversal,
then the root is visited, and then the remaining subtrees are processed from left to
right, each in inorder. If the tree is a binary tree, the result is that the root is visited
between processing of the two subtrees. In a nonbinary tree, if there is a single
subtree joined to its parent by a vertical arc, that is considered the left subtree and
there are no additional subtrees.
Finally, in postorder traversal, the root is visited last, after all subtrees have
been processed from left to right in postorder.
alGoritHm Postorder
Postorder (tree T)
//Writes the nodes of a tree with root r in postorder
for i = 1 to t do
Postorder(T i )
end for
write(r)
end Postorder
example 25
For the binary tree of Figure 6.45, the preorder traversal algorithm (root, left,
right) says to write the root first, a, and then process the left subtree. At the left
subtree, rooted at b, a preorder traversal writes the root, b, and moves again to the
left subtree, which is the single node d. This single node is the root of a tree, so
it is written out. Then d’s left subtree (empty) and d’s right subtree (empty) are
traversed. Backing up to the tree rooted at b, its left subtree has been traversed,
so now the right subtree is traversed, producing node e. The subtree rooted at
alGoritHm Inorder
Inorder (tree T )
//Writes the nodes of a tree with root r in inorder
Inorder(T 1 )
write(r)
for i = 2 to t do
Inorder(T i )
end for
end Inorder