Tree Enumerators

Data Structures and Algorithms with Object-Oriented Design Patterns in C#

Tree Enumerators

This section describes the implementation of an enumerator which can be used to step through the contents of any tree instance. For example, suppose we have declared a variable tree which refers to a BinaryTree. Then we can view the tree instance as a container and print its contents as follows:

Tree tree = new BinaryTree();
// ...
IEnumerator e = tree.GetEnumerator();
while (e.MoveNext())
{
    Object obj = e.Current;
    Console.WriteLine(obj);
}

Every concrete class that implements the Container interface must provide a GetEnumerator method. This method returns an object that implements the IEnumerator interface defined in Section . The enumerator can then be used to systematically visit the contents of the associated container.

We have already seen that when we systematically visit the nodes of a tree, we are doing a tree traversal. Therefore, the implementation of the enumerator must also do a tree traversal. However, there is a catch. A recursive tree traversal method such as DepthFirstTraversal keeps track of where it is implicitly using the C# virtual machine stack. However, when we implement an enumerator we must keep track of the state of the traversal explicitly. This section presents an enumerator implementation which does a preorder traversal of the tree and keeps track of the current state of the traversal using a stack from Chapter .

Program introduces the private nested class Enumerator declared within the AbstractTree class. The Enumerator class implements the IEnumerator interface defined in Section . The Enumerator contains two fields--tree and stack. As shown in Program , the GetEnumerator method of the AbstractTree class returns a new instance of the Enumerator class each time it is called.

program15736
Program: AbstractTree class GetEnumerator method and the Enumerator class.