514
Graphs and Trees
Tree Traversal algorithms
If a tree structure is being used to store data, it is often helpful to have a systematic
mechanism for writing out the data values stored at all the nodes, which can be
accomplished by traversing the tree, that is, visiting each of the nodes in the tree
structure, The three common tree traversal algorithms are preorder, inorder, and
postorder traversal.
In the three traversal methods, it is helpful to use the recursive view of a
tree, where the root of a tree has branches down to roots of subtrees. We will
therefore assume that a tree T has a root r; any subtrees are labeled left to right as
T 1 , T 2 , … , T t (Figure 6.44). Because we are using a recursive definition of a tree,
it will be easy to state the tree traversal algorithms in recursive form.
T 2
T t
T 1
r 2
r t
r 1
r
. . .
Figure 6.44
The terms preorder, inorder, and postorder refer to the order in which the root
of a tree is visited compared to the subtree nodes. In preorder traversal, the root
of the tree is visited first and then the subtrees are processed left to right, each in
preorder.
alGoritHm Preorder
Preorder (tree T )
//Writes the nodes of a tree with root r in preorder
write(r)
for i = 1 to t do
Preorder(T i )
end for
end Preorder