Tree Iterators

Data Structures and Algorithms with Object-Oriented Design Patterns in Python

Tree Iterators

This section describes the implementation of an iterator 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 = BinaryTree()
# ...
it = iter(tree)
while True:
    try:
	print it.next()
    except StopIteration:
	break

The loop above can also be written using a Python for loop like this:

for obj in tree:
    print obj

Every concrete class that extends the abstract Container class must provide an __iter__ method. This method returns an instance of a class that extends the abstract Iterator class defined in Section . 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 method such as depthFirstTraversal keeps track of where it is implicitly using the Python virtual machine 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 defines the nested class Tree.Iterator. The Tree.Iterator class extends the abstract Iterator class defined in Section . The Iterator contains two instance attributes--_container and _stack. As shown in Program , the __iter__ method of the abstract Tree class returns a new instance of the Tree.Iterator class each time it is called.

program15756
Program: Abstract Tree class __iter__ method and the Tree.Iterator class.