Tree Iterators

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

Tree Iterators

According to the object hierarchy defined in Chapter , every class derived from the Container class must provide an associated Iterator class. This section describes the implementation of the Tree::Iter class which can be used to step through the contents of any tree instance.

For example, suppose we have declared a variable tree which is of type BinaryTree. Then we can view the tree instance as a container and print its contents as follows:

BinaryTree tree;
Iterator& i = tree.NewIterator;
while (!i.IsDone ()) {
    cout << *i << endl;
    ++i;
}
delete &i;

Every concrete class derived from the Container abstract base class must provide a NewIterator function. The purpose of this function is to create an instance of the appropriate type of Iterator and to associate that iterator with the corresponding container. The iterator 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 iterator must also do a tree traversal. However, there is a catch. A recursive tree traversal routine such as DepthFirstTraversal keeps track of where it is implicitly using the processor stack. However, when we implement an iterator we must keep track of the state of the traversal explicitly. This section presents an iterator 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 gives the declaration of the Tree::Iter class. The NewIterator member function of the abstract class Tree is implemented as follows:

Iterator& Tree::NewIterator () const
    { return *new Iter (*this); }