import java.util.*;

public class BinaryTree extends Tree
 { protected Object obj;
   protected BinaryTree left, right; //visible in subclasses
   // NB. there are other ways of implementing a binary tree

   public BinaryTree(Object obj, BinaryTree left, BinaryTree right)
    { this.obj=obj; this.left=left; this.right=right; } // constructor

   public BinaryTree(Object obj) {this(obj, empty, empty);}

   public Object     contents() { return obj; }     // these extras
   public BinaryTree left()     { return left; }    // define the essence
   public BinaryTree right()    { return right; }   // of BinaryTree-ness


   public Tree subTree(int i) // required by Tree
    { if(i == 0) return left;
      else if(i == 1) return right;
      else return BinaryTree.empty; // ? or throw exception ?
    }

   public int fanOut() { return 2; } // required by Tree


   protected interface EmptyBinaryTreeMarker { }
    // NB. sub-classes of BinaryTree can contain implementations of EBTM

   public  boolean isEmpty() { return this instanceof EmptyBinaryTreeMarker; }

   protected static class EmptyTree
    extends BinaryTree implements EmptyBinaryTreeMarker
    { public EmptyTree() { super(null); }
      private void err(String s)
       { throw new RuntimeException("method " + s + " on BinaryTree.empty");
       }
      public Object     contents() { err("contents"); return null; }
      public BinaryTree left()     { err("left"); return null; }
      public BinaryTree right()    { err("right"); return null; }
      public Tree       subTree(int i) { err("subTree"); return null; }
      public int        fanOut()   { err("fanOut"); return 0; }
    }//EmptyTree

   public  static final BinaryTree empty = new EmptyTree();


   private class Infix implements Enumeration // see java.util
    { private boolean more, leftDone, contentsDone;
      private Enumeration subInfix = null;

      public Infix()
       { more = ! BinaryTree.this.isEmpty();
	 leftDone = ! more;  contentsDone = leftDone;
	 if(more) if(BinaryTree.this.left.isEmpty()) leftDone=true;
	          else/*not empty*/ subInfix = BinaryTree.this.left.infix();
       }//constructor

      public boolean hasMoreElements() { return more; }

      public Object nextElement()
       { if( ! leftDone )
	  { if(subInfix.hasMoreElements()) return subInfix.nextElement();
            else { subInfix = null; leftDone = true; /* and drop through */ }
	  }//else leftDone
         if( ! contentsDone )
	  { contentsDone = true;
	    more = ! BinaryTree.this.right.isEmpty();
	    if(more) subInfix = BinaryTree.this.right.infix();
	    return BinaryTree.this.contents();
          }//else contentsDone, so in right subtree
	  Object obj = subInfix.nextElement();
	  more = subInfix.hasMoreElements();
	  return obj;
       }//nextElement
    }//infix

   public Enumeration infix() { return new Infix(); }
 }//BinaryTree

// L. Allison, Computer Science and Software Engineering, Monash University