import java.util.*;

class Knoten<T>{
	Knoten<T> links;
	T inhalt;
	Knoten<T> rechts;
	Knoten(T el){ inhalt = el;}
	Knoten(T el, Knoten<T> li, Knoten<T> re){ 
		inhalt = el;
		links = li;
		rechts = re;
		}
}

class TelEintrag{
	String name;
	String nr;
	TelEintrag(String s, String n){ name=s;nr=n;}
	public String toString(){  
      return "( "+ name + ": " + nr +" )";
     }	
}

class BinärBaum <T> implements Iterable<T>{
	private Knoten<T> wurzel;
	
	BinärBaum(Knoten<T> w){wurzel =w;}
	
	
	// definiert den Iterator, den iterator zurückgibt
	enum Order{ PREORDER, POSTORDER, INORDER, LEVELORDER}
	private Order order = Order.PREORDER; 
	
	void setOrder (Order o){ order =o;}
	
	boolean istLeer(){ return wurzel == null;}
	
	int rekAnzKnoten(Knoten<T> k){
	  if  (k == null) return 0;
	  return 1 + rekAnzKnoten(k.links) + rekAnzKnoten(k.rechts);
	  }
	
	int anzKnoten(){
	  if  (istLeer()) return 0;
	  return 1 + rekAnzKnoten(wurzel.links) + rekAnzKnoten(wurzel.rechts);
	  }
	  
	int rekTiefe(Knoten<T> k){
	  if  (k == null) return 0;
	  return 1 + Math.max(rekTiefe(k.links), rekTiefe(k.rechts));
	  }
	
	int tiefe(){
	  if  (istLeer()) return 0;
	  return 1 + Math.max(rekTiefe(wurzel.links), rekTiefe(wurzel.rechts));
	  }  
	
	

    void LoescheLinkenTeilBaum(Knoten<T> bp){
        if (bp != null)
          if (bp.links != null){
           LoescheTeilBaeume(bp.links);
           bp.links =null;
           }
        }
        
    void LoescheRechtenTeilBaum(Knoten<T> bp){
        if (bp != null)
          if (bp.rechts != null){
           LoescheTeilBaeume(bp.rechts);
           bp.rechts =null;
           }
        }  
        
    void LoescheTeilBaeume(Knoten<T> bp){
        LoescheLinkenTeilBaum(bp);
        LoescheRechtenTeilBaum(bp);
        }    
        
    void TesteLoescheTeilBaeume(){
        LoescheTeilBaeume(wurzel.rechts);
        }    

   
   ArrayList<T> genArrayList(){
   	  ArrayList<T> myArrayList = new ArrayList<T>(anzKnoten());
   	  switch (order){
   	    case PREORDER:   preOrder(myArrayList);   break;
   	    case POSTORDER:  postOrder(myArrayList);  break;
   	    case INORDER:    inOrder(myArrayList);    break;
   	    case LEVELORDER: levelOrder(myArrayList); break;
   	  }
   	  return myArrayList;
     }
   
   public Iterator<T> iterator(){ // implementiert iterable. Je nachdem welchen Wert das Feld order hat, wird Pre-, Post-, In- oder Levelorder zurückgegeben
    	return genArrayList().iterator();	
	 }   
   
   void preOrder(ArrayList<T> ml){
		  rekPreorder(wurzel, ml); 
	   }
	void rekPreorder(Knoten<T> k, ArrayList<T> ml){
		if (k != null){
			ml.add(k.inhalt);
			rekPreorder(k.links, ml);
			rekPreorder(k.rechts, ml);
			}
		}

    void postOrder(ArrayList<T> ml){ rekPostorder(wurzel, ml);}

    void rekPostorder(Knoten<T> k, ArrayList<T> ml){
        if (k != null){
           rekPostorder(k.links, ml);
           rekPostorder(k.rechts, ml);
           ml.add(k.inhalt);
           }
        }

    void inOrder(ArrayList<T> ml){ rekInorder(wurzel, ml);}

    void rekInorder(Knoten<T> k, ArrayList<T> ml){
        if (k != null){
           rekInorder(k.links, ml);
           ml.add(k.inhalt);
           rekInorder(k.rechts, ml);
           }
        }

    void levelOrder(ArrayList<T> ml){
		BoundedQueue q = new BoundedQueue(anzKnoten());
		try{
			q.enQ(wurzel);
			while (!q.isEmpty() ) {
					Knoten<T> k = (Knoten<T>) q.getNext();
					ml.add(k.inhalt);
				  if (k.links != null)  q.enQ(k.links);
					if (k.rechts != null) q.enQ(k.rechts);
				 }
			 }
			catch(Exception e){System.out.println("Exception "+e);}
		}
		
		public String toString(){  
      StringBuilder sb = new StringBuilder() ;
      for (T e : this) sb.append(e+" ");
      return sb.toString();
     }	
		
		/*public String toString(){  
      StringBuilder sb = new StringBuilder() ;
      for (T e : this) sb.append(e);
      return sb.toString();
     }*/	
   
   /*public String toString(){  
      StringBuilder sb = new StringBuilder("(") ;
      boolean first = true;
      for (T e : this){
         if (first) first=false;
         else sb.append( ", ");
         sb.append(e);
        }
      sb.append(")");
      return sb.toString();
   }*/	
	
  public static void main(String ... args) {
  	 System.out.println("Baum Tester");
     System.out.println("BAUMBEISPIEL");
     BinärBaum<Character> buchstabenBaum = new BinärBaum<Character>(new Knoten<Character>('B',
         new Knoten<Character>('A',null, new Knoten<Character>('B')),
         new Knoten<Character>('U', new Knoten<Character>('M',
             new Knoten<Character>('E',new Knoten<Character>('E'), new Knoten<Character>('I',new Knoten<Character>('I'),new Knoten<Character>('L'))),
             new  Knoten<Character>('S',new Knoten<Character>('P'),null))      
         , null)
         ));
     buchstabenBaum.setOrder(Order.PREORDER);
     System.out.print("Preorder:   ");
     System.out.println(buchstabenBaum);
     buchstabenBaum.setOrder(Order.POSTORDER);
     System.out.print("Postorder:  ");
     System.out.println(buchstabenBaum);
     buchstabenBaum.setOrder(Order.INORDER);
     System.out.print("Inorder:    ");
     System.out.println(buchstabenBaum);
     buchstabenBaum.setOrder(Order.LEVELORDER);
     System.out.print("Levelorder: ");
     System.out.println(buchstabenBaum);
     
     System.out.println();
     System.out.println("Operator Baum");
     
     BinärBaum<String> opBaum = new BinärBaum<String>(new Knoten<String>("-",
        new Knoten<String>("+/-",new Knoten<String>("12"),null),
        new Knoten<String>("-",new Knoten<String>("*", 
            new Knoten<String>("3"), new Knoten<String>("( )^2",
                new Knoten<String>("-", new Knoten<String>("7"),new Knoten<String>("5")),
                null)),
          new Knoten<String>("9"))
       ));
     opBaum.setOrder(Order.PREORDER);
     System.out.print("Preorder:   ");
     System.out.println(opBaum);
     opBaum.setOrder(Order.POSTORDER);
     System.out.print("Postorder:  ");
     System.out.println(opBaum);
     opBaum.setOrder(Order.INORDER);
     System.out.print("Inorder:    ");
     System.out.println(opBaum);
     opBaum.setOrder(Order.LEVELORDER);
     System.out.print("Levelorder: ");
     System.out.println(opBaum);
     
     Knoten<TelEintrag> ferdi = new Knoten<TelEintrag>(new TelEintrag("Ferdi","66 23 10")); 
  	 Knoten<TelEintrag> fritz = new Knoten<TelEintrag>(new TelEintrag("Fritz","26 28 87"), ferdi,null); 
  	 Knoten<TelEintrag> gitte = new Knoten<TelEintrag>(new TelEintrag("Gitte","37 37 92")); 
  	 Knoten<TelEintrag> gerd = new Knoten<TelEintrag>(new TelEintrag("Gerd","24 78 56"), fritz, gitte); 
  	 Knoten<TelEintrag> eva = new Knoten<TelEintrag>(new TelEintrag("Eva","45 28 87"), null, gerd); 
  	 Knoten<TelEintrag> xaver = new Knoten<TelEintrag>(new TelEintrag("Xaver","72 63 63")); 
  	 Knoten<TelEintrag> ulrich = new Knoten<TelEintrag>(new TelEintrag("Ulrich","78 37 73"), null, xaver); 
  	 Knoten<TelEintrag> hans = new Knoten<TelEintrag>(new TelEintrag("Hans","16 17 28"), eva, ulrich);
  	 System.out.println();
     System.out.println("Telefon Nummern Baum");
     
     BinärBaum<TelEintrag> telBaum = new BinärBaum<TelEintrag>(hans);
     telBaum.setOrder(Order.PREORDER);
     System.out.print("Preorder:   ");
     System.out.println(telBaum);
     telBaum.setOrder(Order.POSTORDER);
     System.out.print("Postorder:  ");
     System.out.println(telBaum);
     telBaum.setOrder(Order.INORDER);
     System.out.print("Inorder:    ");
     System.out.println(telBaum);
     telBaum.setOrder(Order.LEVELORDER);
     System.out.print("Levelorder: ");
     System.out.println(telBaum);
     
     System.out.println("Baumtiefe:");
     System.out.println(telBaum.tiefe());
     System.out.println(opBaum.tiefe());
     System.out.println(buchstabenBaum.tiefe());
     System.out.println("Anzahl der Knoten:");
     System.out.println(telBaum.anzKnoten());
     System.out.println(opBaum.anzKnoten());
     System.out.println(buchstabenBaum.anzKnoten());
     }
     
 }    
  
  
  /*public static void main(String ... args) {
        System.out.println("Baum Tester");
        System.out.println("");
        String Beispiel = "BAUMBEISPIEL";
        BinärBaum<Character> buchstabenBaum = new BinärBaum<Character>();
        for (char c : Beispiel.toCharArray()) buchstabenBaum.einfuegen(c);
        System.out.println("Anzahl Knoten: "+buchstabenBaum.anzKnoten());
        buchstabenBaum.setOrder(Order.PREORDER);
        System.out.print("Preorder:   ");
        System.out.println(buchstabenBaum);
        buchstabenBaum.setOrder(Order.POSTORDER);
        System.out.print("Postorder:  ");
        System.out.println(buchstabenBaum);
        buchstabenBaum.setOrder(Order.INORDER);
        System.out.print("Inorder:    ");
        System.out.println(buchstabenBaum);
        buchstabenBaum.setOrder(Order.LEVELORDER);
        System.out.print("Levelorder: ");
        System.out.println(buchstabenBaum);
            }
        
        
        /*System.out.println("LoeschTest!");
        
        buchstabenBaum.TesteLoescheTeilBaeume();
        if (buchstabenBaum.istLeer())System.out.println("Loeschen: Der Baum ist leer!");
        else {
            System.out.print("Preorder:   ");
            buchstabenBaum.preOrder(MeinBesucher );
            System.out.print("\nPostorder:  ");
            buchstabenBaum.postOrder(MeinBesucher );
            System.out.print("\nInorder:    ");
            buchstabenBaum.inOrder(MeinBesucher );
            System.out.print("\nLevelorder: ");
            try { buchstabenBaum.levelOrder(MeinBesucher, L );}
            catch(QueueFehler q){System.out.println("Fehler bei Levelorder: "+q); }  
            }
    }
}*/


class BoundedQueue{
// Der Behälter             
  private Object[] theQueue;
  private int maxSize=100; //default

// Das vorderste Element:
  private int front=0;
// Die Position für das nächste Element:
  private int back=0;                   

// Falls length==0 ist Queue leer
  private int length=0;

/** Konstruktor für Queue mit Kapazität size;
    size muss genügend gross sein. Z.B. > 10  */ 
  public BoundedQueue(int size){
    if (size > 10) maxSize=size;
    theQueue = new Object[maxSize]; 
  }
  
 /** Default-Konstruktor */
  public BoundedQueue(){ 
    theQueue = new Object[maxSize]; 
  } 
  
  boolean isFull(){
    return (front == back) && (length > 0);
  }
  
  boolean isEmpty(){
    return (length == 0);
  }
  
  
  private int next1(int n){return (n+1)%maxSize;}
  
  private int next(int n){ return (n == (maxSize-1)) ? 0 : ++n ; } 
  
  void enQ(Object o) throws Exception{
    if (isFull()) throw new Exception("Queue Full");
    else{
      theQueue[back] = o;
      back = next(back);
      length++;
     }
  }
  void deQ() throws Exception{
    if (isEmpty()) throw new Exception("Queue Empty");
    else{
      front = next(front);
      length--;
    }
  }
  
  Object front()throws Exception{
    if (isEmpty()) throw new Exception("Queue is Empty");
      return theQueue[front];
  }
  
  Object getNext() throws Exception{  
    Object result = front();
    deQ();
    return result;
  }
  

  public String toString(){  
      String ausdruck = "[" + length + "]";
      for(int k=front,n=1; n <= length; n++ ){
         ausdruck += (" " + theQueue[k].toString());
         k=next(k);
      }
      return ausdruck;
  }
  void show(){
    System.out.println(toString());
  }
  
}

class BStack{
  // Stack repräsentiert durch theStack[0 .. zeiger-1]
   private Object[] theStack;
   private int zeiger;
   
  /** Konstruktor für Stack gewünschter Grösse */
    BStack(int kapazität){
       theStack = new Object[kapazität];
   }    
   /** Prüft ob Stack leer ist */
    boolean isEmpty(){ return zeiger==0;}

   /** Legt neues Element auf den Stack */
    void push(Object e) throws Exception{
      if(zeiger >= theStack.length)
         throw new Exception("push on full stack");
      else theStack[zeiger++] = e;
    }
   /** Entferne oberstes Element */
    void pop()throws Exception{ 
       if(zeiger>0) zeiger--; 
       else throw new Exception("pop on empty stack");
    } 
   /** Liefert oberstes Element */
    Object top()throws Exception{ 
        if(isEmpty()) 
           throw new Exception("top of empty stack");
        else return theStack[zeiger-1];
    }
   /** Liefert oberstes Element und entfernt es vom Stack */
    Object getNext()throws Exception{
       Object e = top();
       pop();
       return e;
    }
}