Title: Quellcode zum Baum
Course: Informatik GK - Abi 2007

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