Quellcode zum Baum

public class Baum {

    private class Knoten {
            char wert;
            Baum links, rechts;

            Knoten(char wert) { // ensures links != null && rechts != null
                this.wert = wert;
                links = new Baum();
                rechts = new Baum();
            }
    }

    public Knoten knoten;

    /** Konstruktor, initialisiert den Baum */
    public Baum() {
            knoten = null;
    }

    /** Fügt ein Element in den Baum ein*/
    public void insert(char element) {
            if (knoten == null)  // wenn noch kein element vorhanden
                    knoten = new Knoten(element); // Element wird erstes Element
            else if (element < knoten.wert) // wenn doch was drin ist, ab in den linken Baum
                    knoten.links.insert(element);
            else // rechts eintragen, auch wenn gleich
                    knoten.rechts.insert(element); 
    }

    /** Druckt den Baum aus */
    public void show(int blank) {
            if (knoten != null) {
                    for (int i = 0; i < blank; i++)
                            System.out.print(" ");
                    System.out.print(knoten.wert);
                    System.out.println();
                    if (knoten.links != null)
                            knoten.links.show(blank-1);
                    if (knoten.rechts != null)
                            knoten.rechts.show(blank+1);
            }
    }

    /** Löscht aus dem Baum */
    public void loeschen(char element) {
            if (knoten == null) // Baum ist leer
                    return; // element ist nicht vorhanden; Alternativ: Ausnahme auslösen
            else if (element < knoten.wert)
                    knoten.links.loeschen(element); // suchen im linken Teilbaum
            else if (knoten.wert < element)
                    knoten.rechts.loeschen(element); // suchen im rechten Teilbaum
            // else element.equal(knoten.wert) // Element gefunden
            else if (knoten.links.knoten == null) { // höchstens ein Nachfolger
                    if (knoten.rechts.knoten == null) // kein Nachfolger; Fall 1
                        knoten = null; // gefundenen Knoten einfach vernichten
                    else // ein Nachfolger rechts; Fall 2
                        knoten = knoten.rechts.knoten; // rechten Teilbaum umhängen
                 }
            else if (knoten.rechts.knoten == null) // ein Nachfolger links; Fall 2
                    knoten = knoten.links.knoten; // linken Teilbaum umhängen
                    // else zwei Nachfolger: Fall 3
                    /* das kleinste Element im rechten (größeren) Teilbaum wird gesucht,
                       dann mit dem gefundenen Element ausgetauscht und gelöscht: */
            else    if (knoten.rechts.knoten.links.knoten == null) {
                    // rechts hat keinen linken Nachfolger: kann kopiert und aushängt werden
                        knoten.wert = knoten.rechts.knoten.wert; // Inhalt von rechts kopieren
                        knoten.rechts = knoten.rechts.knoten.rechts; // Knoten aushängen
                    } else  { // das kleinste Element in rechts suchen, austauschen und löschen:
                        Baum vorgaenger = knoten.rechts.vorgaengerDesKleinsten();
                        Baum kleinster = vorgaenger.knoten.links;
                        // kleinster hat höchstens einen (rechten) Nachfolger
                        this.knoten.wert = kleinster.knoten.wert; // Inhalt kopieren
                        vorgaenger.loeschen(kleinster.knoten.wert); // kleinsten Knoten löschen
                    }
    }

    private Baum vorgaengerDesKleinsten() {
            // liefert den Baum, dessen linker Nachfolger den kleinsten Wert hat
            if (knoten.links.knoten.links.knoten == null)
            // links hat keinen linken Nachfolger
                    return this;
            else
                    return knoten.links.vorgaengerDesKleinsten(); // rekursiv
    }

}