import java.util.*;

class Knoten<E extends Comparable<E>>{
	E inhalt;
	Knoten<E> links;
	Knoten<E> rechts;
	Knoten(E el){ inhalt = el;}
	
	boolean fertigTest; // für post- und inorder Iteration
}

class BesucherKlasse<E>{
	void f(E e){if (e != null) System.out.print(e);}
}

class BinärBaum <E extends Comparable<E>> implements Iterable<E>{
	private Knoten<E> wurzel;
	
	// definiert den Iterator, den iterator zurückgibt
	private int order = 1; // preorder=1 postorder=2 inorder=3 levelorder sonst
	
	
	void setOrder (int o){ order =o;}
	
	boolean istLeer(){ return wurzel == null;}
	
	int rekanzKnoten(Knoten<E> k){
	  if  (k == null) return 0;
	  else return 1 + rekanzKnoten(k.links) + rekanzKnoten(k.rechts);
	  }
	
	int anzKnoten(){
	  if  (istLeer()) return 0;
	  else return 1 + rekanzKnoten(wurzel.links) + rekanzKnoten(wurzel.rechts);
	  }
	
	

    void einfuegen(E e){
        if (wurzel == null) wurzel = new Knoten<E>(e);
        else rekEinfuegen(e, wurzel);
        }

    private void rekEinfuegen(E e, Knoten<E> bp){
        /*Character ch1 = (Character) e;
        Character ch2 = (Character) bp.inhalt;*/
        if (e.compareTo(bp.inhalt) <= 0){
            if (bp.links == null) bp.links = new Knoten<E>(e);
            else rekEinfuegen(e, bp.links);
            }
        else{
            if (bp.rechts == null) bp.rechts = new Knoten<E>(e);
            else rekEinfuegen(e, bp.rechts);
            }
        }

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

public Iterator<E> iterator(){ // implementiert iterable. Je nachdem welchen Wert das Feld order hat, wird Pre-, Post-, In- oder Levelorder zurückgegeben
    	
    	if (order ==1) return new Iterator<E>() { // Preorder Iterator
    		  private int knotenZahl = anzKnoten();
    		  private int restKnotenZahl = knotenZahl;
    		  private BStack s = new BStack(knotenZahl);
    	    private boolean first = true;
    	    		   
          public boolean hasNext() {
          	return restKnotenZahl > 0; 
          	}
	    
			    public E next() { 
            Knoten<E> k = null;
            try{
            	if (first){
	            	s.push(wurzel);
	            	first = false;
	             }
	          	if(s.isEmpty()) throw new  IllegalStateException(); 
					    k = (Knoten<E>) s.getNext();
					    if (k.rechts != null) s.push(k.rechts);
					    if (k.links != null)  s.push(k.links);
						  restKnotenZahl--;
						  }
			       catch(Exception e){System.out.println("Exception "+e);}
            return k.inhalt;
            }
            
            public void remove() {
            	throw new UnsupportedOperationException();
            	}
	    };
	    else if (order ==2) return new Iterator<E>() { // Postorder Iterator  	    		   
          private int knotenZahl = anzKnoten();
    		  private int restKnotenZahl = knotenZahl;
    		  private BStack s = new BStack(knotenZahl);
    	    private boolean first = true;
    	    		   
          public boolean hasNext() {
          	return restKnotenZahl > 0; 
          	}
	    
			    public E next() { 
            Knoten<E> k = null;
            try{
            	if (first){
            		wurzel.fertigTest = false;
	            	s.push(wurzel);
	            	first = false;
	             }
	          	boolean fertig = false;
	          	while (!fertig){
		          	if(s.isEmpty()) throw new  IllegalStateException(); 
						    k = (Knoten<E>) s.getNext();
						    if (k.fertigTest) fertig = true;
						    else{
						      k.fertigTest = true; 
						      s.push(k);
						      if (k.rechts != null) {
						      	k.rechts.fertigTest = false;
						      	s.push(k.rechts);
						       }
						      if (k.links != null){
						      	k.links.fertigTest = false;
						      	s.push(k.links);
						      }
						     }
						   }
							restKnotenZahl--;
							}
			       catch(Exception e){System.out.println("Exception "+e);}
            
            return k.inhalt;
            }
            
            public void remove() {
            	throw new UnsupportedOperationException();
            	}
	    };
	    else if (order ==3) return new Iterator<E>() { // Inorder Iterator  	    		   
          private int knotenZahl = anzKnoten();
    		  private int restKnotenZahl = knotenZahl;
    		  private BStack s = new BStack(knotenZahl);
    	    private boolean first = true;
    	    		   
          public boolean hasNext() {
          	return restKnotenZahl > 0; 
          	}
	    
			    public E next() { 
            Knoten<E> k = null;
            try{
            	if (first){
            		wurzel.fertigTest = false;
	            	s.push(wurzel);
	            	first = false;
	             }
	          	boolean fertig = false;
	          	while (!fertig){
		          	if(s.isEmpty()) throw new  IllegalStateException(); 
						    k = (Knoten<E>) s.getNext();
						    if (k.fertigTest) fertig = true;
						    else{
						      if (k.rechts != null) {
						      	k.rechts.fertigTest = false;
						      	s.push(k.rechts);
						       }
						      k.fertigTest = true; 
						      s.push(k);
						      if (k.links != null){
						      	k.links.fertigTest = false;
						      	s.push(k.links);
						      }
						     }
						   }
							restKnotenZahl--;
							}
			       catch(Exception e){System.out.println("Exception "+e);}
            
            return k.inhalt;
            }
            
            public void remove() {
            	throw new UnsupportedOperationException();
            	}
	    };
	    else return new Iterator<E>() { // Levelorder Iterator
    		  private int knotenZahl = anzKnoten();
    		  private int restKnotenZahl = knotenZahl;
    		  private BoundedQueue q = new BoundedQueue(knotenZahl);
    	    private boolean first = true;
    	    		   
          public boolean hasNext() {
          	return restKnotenZahl > 0; 
          	}
	    
			    public E next() { 
            Knoten<E> k = null;
            try{
            	if (first){
	            	q.enQ(wurzel);
	            	first = false;
	             }
	          	if(q.isEmpty()) throw new  IllegalStateException(); 
					    k = (Knoten<E>) q.getNext();
					    if (k.links != null) q.enQ(k.links);
						  if (k.rechts != null) q.enQ(k.rechts);
						  restKnotenZahl--;
						  }
			       catch(Exception e){System.out.println("Exception "+e);}
            return k.inhalt;
            }
            
            public void remove() {
            	throw new UnsupportedOperationException();
            	}
	    };
	 }   
   
   void preOrder(BesucherKlasse<E> besucher){
		  rekPreorder(wurzel, besucher); 
	   }
	void rekPreorder(Knoten<E> k, BesucherKlasse<E> besucher){
		if (k != null){
			besucher.f(k.inhalt);
			rekPreorder(k.links, besucher);
			rekPreorder(k.rechts, besucher);
			}
		}

    void postOrder(BesucherKlasse<E> bes){ rekPostorder(wurzel, bes);}

    void rekPostorder(Knoten<E> k, BesucherKlasse<E> bes){
        if (k != null){
           rekPostorder(k.links, bes);
           rekPostorder(k.rechts, bes);
           bes.f(k.inhalt);
           }
        }

    void inOrder(BesucherKlasse<E> bes){ rekInorder(wurzel, bes);}

    void rekInorder(Knoten<E> k, BesucherKlasse<E> bes){
        if (k != null){
           rekInorder(k.links, bes);
           bes.f(k.inhalt);
           rekInorder(k.rechts, bes);
           }
        }

    void levelOrder(BesucherKlasse<E> besucher, int l){
		BoundedQueue q = new BoundedQueue(l);
		try{
			q.enQ(wurzel);
			do {
					Knoten<E> k = (Knoten<E>) q.getNext();
					if (k != null){
						besucher.f(k.inhalt);
						if (k.links != null)q.enQ(k.links);
						if (k.rechts != null)q.enQ(k.rechts);
						}
				}while (!q.isEmpty() );
			}
			catch(Exception e){System.out.println("Exception "+e);}
		}
		
		public String toString(){  
      StringBuilder sb = new StringBuilder() ;
      for (E e : this) sb.append(e);
      return sb.toString();
   }	
   
   /*public String toString(){  
      StringBuilder sb = new StringBuilder("(") ;
      boolean first = true;
      for (E 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("");
        String Beispiel = "BAUMBEISPIEL";
        int L = Beispiel.length();
        BinärBaum<Character> MeinBaum = new BinärBaum<Character>();
        BesucherKlasse<Character> MeinBesucher = new BesucherKlasse<Character>();

        for (char c : Beispiel.toCharArray()) MeinBaum.einfuegen(c);
        System.out.println("Anzahl Knoten: "+MeinBaum.anzKnoten());

        if (MeinBaum.istLeer())System.out.println("Sch...! Der Baum blieb leer!");
        else {
            System.out.print("Preorder:   ");
            MeinBaum.preOrder(MeinBesucher );
            System.out.println();
            MeinBaum.setOrder(1);
            System.out.print("Preorder:   ");
            System.out.println(MeinBaum);
            System.out.print("Postorder:  ");
            MeinBaum.postOrder(MeinBesucher );
            System.out.println();
            MeinBaum.setOrder(2);
            System.out.print("Postorder:  ");
            System.out.println(MeinBaum);
            System.out.print("Inorder:    ");
            MeinBaum.inOrder(MeinBesucher );
            System.out.println();
            MeinBaum.setOrder(3);
            System.out.print("Inorder:    ");
            System.out.println(MeinBaum);
            System.out.print("Levelorder: ");
            MeinBaum.levelOrder(MeinBesucher, L );
            System.out.println();
            MeinBaum.setOrder(4);
            System.out.print("Levelorder: ");
            System.out.println(MeinBaum);
            }
        
        
        /*System.out.println("LoeschTest!");
        
        MeinBaum.TesteLoescheTeilBaeume();
        if (MeinBaum.istLeer())System.out.println("Loeschen: Der Baum ist leer!");
        else {
            System.out.print("Preorder:   ");
            MeinBaum.preOrder(MeinBesucher );
            System.out.print("\nPostorder:  ");
            MeinBaum.postOrder(MeinBesucher );
            System.out.print("\nInorder:    ");
            MeinBaum.inOrder(MeinBesucher );
            System.out.print("\nLevelorder: ");
            try { MeinBaum.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;
    }
}