Comp 271 lab 8 - tree iterators
Goals
- constructing tree iterators using stacks and queues
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.