/** 
  * 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 BinaryTree tree;
  /** Execution of the traversal. This abstract method must be
   * specified in a concrete subclass. */
  public abstract Object execute(BinaryTree T);
  /** Initialization of the traversal */
  protected void init(BinaryTree T) { tree = T; }
  /** Template method */
  protected Object eulerTour(Position v) {
    TraversalResult r = new TraversalResult();
    visitLeft(v, r);
    if (tree.hasLeft(v))
      r.left = eulerTour(tree.left(v)); // recursive traversal
    visitBelow(v, r);
    if (tree.hasRight(v))
      r.right = eulerTour(tree.right(v)); // recursive traversal
    visitRight(v, r);
    return r.out;
  }
  // Auxiliary methods that can be redefined by subclasses:
  /** Method called for the visit on the left */
  protected void visitLeft(Position v, TraversalResult r) {}
  /** Method called for the visit on from below */
  protected void visitBelow(Position v, TraversalResult r) {}
  /** Method called for the visit on the right */
  protected void visitRight(Position v, TraversalResult r) {}
}