Iterating over a tree


for(Iterator i = tree.preOrderIterator(); i.hasNext(); )
{
  Node n = (Node)i.next();
  ...
  stuff
  ...
}
Writing iterators like this, as part of writing some new data structures, is pretty straightforward. For a simple tree adt, writing the set of three different iterators takes only a few minutes. I knocked up a quick sample tree and iterators in about 10 minutes.

Here, we can change the iterator at the top there and the body of the loop remains the same.

If we know our particular tree needs to be walked in a particular way - perhaps it's an expression tree so you want post-order - we can use our general tree as the implementation and map the iterator() method to the appropriate Tree.*Iterator. Even within the same tree you might want to walk in different ways at different times. You might do a post-order walk to evaluate an expression tree, but an in-order walk for a human readable print out.