Data Structures and Algorithms
with Object-Oriented Design Patterns in C++
The first depth-first traversal method
we consider is called
preorder traversal .
Preorder traversal is defined recursively as follows.
To do a preorder traversal of a general tree:
- Visit the root first; and then
- do a preorder traversal each of the subtrees of the root
one-by-one in the order given.
Preorder traversal gets its name from the fact that it visits the root first.
In the case of a binary tree,
the algorithm becomes:
- Visit the root first; and then
- traverse the left subtree; and then
- traverse the right subtree.
For example, a preorder traversal of the tree shown in Figure
visits the nodes in the following order:
![displaymath63846](img1145.gif)
Notice that the preorder traversal visits the nodes of the tree
in precisely the same order in which they are written
in Equation
.
A preorder traversal is often done when it is necessary
to print a textual representation of a tree.
Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.