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

Binary Tree Traversals

 

Program gif defines the DepthFirstTraversal method of the BinaryTree class. This method supports all three tree traversal methods--preorder, inorder, and postorder. The implementation follows directly from the definitions given in Section gif. The traversal is implemented using recursion. That is, the method calls itself recursively to visit the subtrees of the given node. Note that the recursion terminates properly when an empty tree is encountered since the method does nothing in that case.

   program16548
Program: BinaryTree class DepthFirstTraversal method.

The traversal method takes as its argument any object that implements the PrePostVisitor interface defined in Program gif. As each node is ``visited'' during the course of the traversal, the PreVisit, InVisit, and PostVisit methods of the visitor are invoked on the object contained in that node.


next up previous contents index

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