Comp 271 lab 8 - tree iterators

Goals

Overview

Start with the itertree.zip project. The TreeMaker class builds ordered trees T1 and T2 (there's no reason for requiring here that the trees be ordered, except that it was marginally easier to build them that way, because the order alone determined the tree structure). There are also methods to print the trees via pre-order and in-order traversal.

It is relatively easy to use recursion to traverse a given tree, in either pre-order, in-order, or post-order forms. But how can we get an iterator to work? Recursion has to keep "going" because all its state is on the runtime stack; you can't pause and freeze that.

To build an iterator, we'll use the stack-based approach. Replacing the stack with a queue, this also works for level-wise (breadth-first) traversal (which we can't do recursively).

I've done the in-order-traversal iterator: we start by pushing all the left subtrees (see the example code); we'll call this "pushing the leftmost branch". Then, when we pop a node (and eventually return its value), we first see if its right subtree is nonempty. If it is, we push the leftmost branch of the right subtree before returning the value. This means that, after the value, we'll visit the full right subtree.

You are to build iterators for pre-order traversal and level-order traversal. Note that defining an iterator means, as usual, filling in the details (primarily the next() method) of the appropriate "inner classes".

For the pre-order iterator, the next() method will pop a node, push the left() and right() subtrees, and return the current value; this is probably the easiest of all the traversals.

For the level-order iterator, you will have to finish a simple Queue class; I suggest building it in the "trivial" way on ArrayList (ie dequeue deletes and returns the item at position 0, which is inefficient but will do for now). Then use your pre-order traversal code as a model, except use the queue instead of the stack (and enqueue instead of push, etc).

Test your pre-order to verify that it prints the data in the same order as the recursive pre-order traversal.

To submit your project, create a zipfile and email it to me at pld@cs.luc.edu.