|
Data Structures and Algorithms
with Object-Oriented Design Patterns in C# |
Program 
defines the DepthFirstTraversal method
of the AbstractTree class.
The traversal method takes one argument--any object that implements the PrePostVisitor interface
defined in Program .
Program: AbstractTree class DepthFirstTraversal method.
A PrePostVisitor is a visitor with three methods,
PreVisit, InVisit, PostVisit,
and the propderty IsDone.
During a depth-first traversal the PreVisit and PostVisit
methods are each called once for every node in the tree.
(The InVisit method is provided for binary trees
and is discussed in Section ).
Program: PrePostVisitor interface.
The depth-first traversal method first calls the PreVisit method with the object in the root node. Then, it calls recursively the DepthFirstTraversal method for each subtree of the given node. After all the subtrees have been visited, the PostVisit method is called. Assuming that the IsEmpty, Key, and GetSubtree operations all run in constant time, the total running time of the DepthFirstTraversal method is
where n is the number of nodes in the tree,
is the running time of PreVisit,
and 
is the running time of 
.
Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.