/**
 * Template for algorithms traversing a binary tree using an Euler
 * tour. The subclasses of this class will redefine some of the
 * methods of this class to create a specific traversal.
 */
public abstract class EulerTour {
  protected InspectableBinaryTree tree; 
  public Object execute(BinaryTree T) {
    tree = T;
    return null;  // nothing interesting to return
  }
  protected Object eulerTour(Position p) {
    TraversalResult r = initResult();
    if (tree.isExternal(p)) {
      visitExternal(p, r);
    } else {
      visitLeft(p, r);
      r.leftResult = eulerTour(tree.leftChild(p)); // recursive traversal
      visitBelow(p, r);
      r.rightResult = eulerTour(tree.rightChild(p)); // recursive traversal
      visitRight(p, r);
    }
    return result(r);
  }
  // methods that can be redefined by the subclasses
  protected void visitExternal(Position p, TraversalResult r) {}
  protected void visitLeft(Position p, TraversalResult r) {}
  protected void visitBelow(Position p, TraversalResult r) {}
  protected void visitRight(Position p, TraversalResult r) {}
  protected TraversalResult initResult() { return new TraversalResult(); }
  protected Object result(TraversalResult r) { return r.finalResult; }
}