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

Implementation

Program gif defines the method BreadthFirstTraversal. This method as its argument any object that implements the Tree interface. The idea is that the method is passed the root of the tree to be traversed. The algorithm makes use of the QueueAsLinkedList data structure, which was defined in the preceding section, to hold the appropriate tree nodes.

The running time of the BreadthFirstTraversal algorithm depends on the number of nodes in the tree which is being traversed. Each node of the tree is enqueued exactly once--this requires a constant amount of work. Furthermore, in each iteration of the loop, each node is dequeued exactly once--again a constant amount of work. As a result, the running time of the BreadthFirstTraversal algorithm is O(n) where n is the number of nodes in the traversed tree.

   program7482
Program: Queue application--breadth-first tree traversal.


next up previous contents index

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