|
Data Structures and Algorithms
with Object-Oriented Design Patterns in C# |
Program 
defines the standard operations
provided by enumerators,
the MoveNext and Reset methods,
and the Current property.
The Enumerator uses the stack to keep track nodes in the tree
to be enumerated.
As long as the stack is not empty,
the Current property provides a get accessor
that returns the key of the tree node at the top of the stack.
Clearly, the running time for this accessor is O(1).
Program: AbstractTree Enumerator class Current property, MoveNext and Reset methods.
The MoveNext method advances the enumerator to the next item and returns true as long as there are still more items in the container. If the stack is empty, the enumeration has not yet begun. In this case, the MoveNext method pushes the root node of the tree onto the stack (provided the tree is not empty). If the stack is not empty, MoveNext method pops the top tree from the stack and then pushes its subtrees onto the stack (provided that they are not empty). Notice the order is important here. In a preorder traversal, the first subtree of a node is traversed before the second subtree. Therefore, the second subtree should appear in the stack below the first subtree. That is why the subtrees are pushed in reverse order. The running time for MoveNext is O(d) where d is the degree of the tree node at found at the top of the stack.
Copyright © 2001 by Bruno R. Preiss, P.Eng. All rights reserved.