Logo Data Structures and Algorithms with Object-Oriented Design Patterns in C++
next up previous contents index

Preorder Traversal

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:

  1. Visit the root first; and then
  2. 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:
  1. Visit the root first; and then
  2. traverse the left subtree; and then
  3. traverse the right subtree.
For example, a preorder traversal of the tree shown in Figure gif visits the nodes in the following order:

displaymath63846

Notice that the preorder traversal visits the nodes of the tree in precisely the same order in which they are written in Equation gif. A preorder traversal is often done when it is necessary to print a textual representation of a tree.


next up previous contents index

Bruno Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.