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

class Knoten{
	Object inhalt;
	Knoten links;
	Knoten rechts;
	Knoten(Object el){ inhalt = el;}
}

class BinaerBaum{
	private Knoten wurzel;
	private Knoten cursor;
	boolean istLeer(){ return wurzel == null;}

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

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

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


    void preOrder(BesucherKlasse besucher){
		rekPreorder(wurzel, besucher); 
	}
	void rekPreorder(Knoten k, BesucherKlasse besucher){
		if (k != null){
			besucher.f(k.inhalt);
			rekPreorder(k.links, besucher);
			rekPreorder(k.rechts, besucher);
			}
		}

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

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

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

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

    void levelOrder(BesucherKlasse besucher, int l) throws QueueFehler{
		Queue q = new Queue(l);
		q.enQueue(wurzel);
		do {
				Knoten k = q.deQueue();
				if (k != null){
					besucher.f(k.inhalt);
					q.enQueue(k.links);
					q.enQueue(k.rechts);
					}
			}while (!q.istLeer() );
		}
		
		
}


public class BaumT {

    public static void main(String args[]) {
        System.out.println("Baum Tester");
        System.out.println("");
        String Beispiel = "BAUMBEISPIEL";
        int L = Beispiel.length();
        BinaerBaum MeinBaum = new BinaerBaum();
        BesucherKlasse MeinBesucher = new BesucherKlasse();

        for (int i = 0; i < L; i++){
            char c = Beispiel.charAt(i);
            System.out.print(c);
            Character e = new Character(c);
            MeinBaum.einfuegen(e);
            }
        System.out.println();

        if (MeinBaum.istLeer())System.out.println("Sch...! Der Baum blieb 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); }  
            }
        System.out.println("");
        
        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 QueueFehler extends Exception{
    public QueueFehler(){super();}
    public QueueFehler(String s){super(s);}
}

class Queue{
    private Knoten[] inhalt = null;
    private boolean voll = false;
    private int Anfang = 0;
    private int Ende = 0;
    private int MaxIndex;

    Queue(int sz){
      inhalt = new Knoten[sz+1];
      MaxIndex = sz-1;
      }

    private int next(int n){
        if ( n == MaxIndex) return 0;
        return ++n;
        }

    boolean istLeer (){ return (Anfang == Ende) && ! voll;}
    boolean istVoll (){ return voll;}

    void enQueue (Knoten z) throws QueueFehler{
     if (inhalt == null) throw new QueueFehler("QueueFehler: Keine Queue gefunden !");
     if (istVoll()) throw new QueueFehler("QueueFehler: Queue Überlauf !");
     inhalt[Ende] = z;
     Ende = next(Ende);
     voll = (Anfang == Ende);
     }

    Knoten deQueue () throws QueueFehler {
     if (inhalt == null) throw new QueueFehler("QueueFehler: Keine Queue gefunden !");
     if (istLeer()) throw new QueueFehler("QueueFehler: Zugriff auf leere Queue !");
     Knoten z = inhalt[Anfang];
     Anfang = next(Anfang);
     voll = false;
     return z;
     }
}