import java.util.*;

public abstract class Tree
 { public abstract Object  contents();
   public abstract Tree    subTree(int i);
   public abstract int     fanOut();
   public abstract boolean isEmpty();


   public boolean isLeaf()
    { for(int i = 0; i < this.fanOut(); i++) // 0 .. fanOut-1
         if( ! this.subTree(i).isEmpty() ) return false;
      return true; // every child isEmpty
    }//isLeaf()


   public String toString() // overrides Object
    { if(this.isEmpty()) return "()";
      //else
      StringBuffer strB=new StringBuffer("(");
      Object obj = this.contents();
      if(obj != null) strB.append(obj.toString());
      for(int i = 0; i < this.fanOut(); i++) // for each subtree
         strB.append( this.subTree(i).toString() );
      strB.append(")");
      return strB.toString();
    }//toString()

   public String toString(int selector)
    { if(selector == 1) return this.toString2D("");//see below
      /*else*/ return this.toString(); //default, see above
    }

   private String toString2D(String lhs)
    { if(this.isEmpty()) return "";
      StringBuffer strB = new StringBuffer();
      Object obj = this.contents();  String objStr;
      if(obj == null) objStr = ""; else objStr = obj.toString();
      StringBuffer pad = new StringBuffer(objStr+" |");
      for(int i=0; i < objStr.length(); i++) pad.setCharAt(i, ' ');
      for(int i = this.fanOut()-1; i >= 1; i--)
         strB.append( this.subTree(i).toString2D(lhs + pad.toString()));
      strB.append(lhs + objStr + "-|\n");
      if(this.fanOut() > 0)
         strB.append( this.subTree(0).toString2D(lhs + pad.toString()));
      return strB.toString();
    }//toString2D


   private class Prefix implements Enumeration // see java.util
    { private Stack stck = new Stack();
      public Prefix() { if(!Tree.this.isEmpty()) stck.push(Tree.this); }
      public boolean hasMoreElements() { return ! stck.empty(); }
      public Object nextElement()
       { Tree t = (Tree)stck.peek();  stck.pop();
	 for(int i = t.fanOut() - 1; i >= 0; i--)
	  { Tree ti = t.subTree(i); if(!ti.isEmpty()) stck.push(ti); }
	 return t.contents();
    }  }//Prefix

   public Enumeration prefix() { return new Prefix(); }


   private class Postfix implements Enumeration // see java.util
    { private Enumeration subPostfix;
      private int sti /*sub tree index */,  tfo /* tree fan out */;
      private boolean more;

      public Postfix()
       { sti = -1; subPostfix = null;
	 more = ! Tree.this.isEmpty();
	 if(more) tfo = Tree.this.fanOut(); else tfo = 0;
       }//constructor

      public boolean hasMoreElements() { return more; }

      public Object nextElement()
       { if(subPostfix != null)
	    if(subPostfix.hasMoreElements())
	       return subPostfix.nextElement();
	    else subPostfix = null;
	 //subPostfix == null
	 for(sti++; sti < tfo && Tree.this.subTree(sti).isEmpty(); sti++)
	    { /* skip */ }
         if(sti < tfo) // ! empty ...sti
	  { subPostfix = Tree.this.subTree(sti).postfix();
            return subPostfix.nextElement();
          }
         // else sti >= tfo
	 more = false;  return Tree.this.contents(); // root last
    }  }//Postfix

   public Enumeration postfix() { return new Postfix(); }

 }//Tree

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