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;}
	
	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);
        }    

   
   public Iterator<T> iterator(){ // Levelorder Iterator
    	ArrayList<T> myArrayList = new ArrayList<T>(anzKnoten());
    	LinkedList<Knoten<T>> queue = new LinkedList<Knoten<T>>();
    	queue.add(wurzel);
			while (!queue.isEmpty() ) {
			  Knoten<T> k = queue.removeFirst();
			  myArrayList.add(k.inhalt);
				if (k.links  != null) queue.add(k.links);
				if (k.rechts != null) queue.add(k.rechts);
				}
    	return myArrayList.iterator();	
	 }   
   
		
		public String toString(){  
      StringBuilder sb = new StringBuilder() ;
      for (T e : this) sb.append(e+" ");
      return sb.toString();
     }	
   }
	
 class BinärBaumLevelOrder{
 	 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)
         ));

     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"))
       ));

     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);
     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());
     }
     
 }