Das Prinzip Binärbaum

Stapel und Schlange sind Ketten: Jedes Element hat höchstens einen Nachfolger. Im Binärbaum verzweigt sich die Kette — jedes Element darf zwei Nachfolger haben.

• Binärbaum:Knoten mit einem Inhalt und höchstens zwei Kindern — einem linken und einem rechten.
• Wurzel:der oberste Knoten; nur er hat keinen Elternknoten.
• Blatt:Knoten ohne Kinder. Alle anderen Knoten heißen innere Knoten.
• Kante:Verbindung vom Elternknoten zum Kind; es gibt genau einen Weg von der Wurzel zu jedem Knoten.
• Teilbaum:ein Knoten mit allem, was unter ihm hängt. Jeder Knoten ist Wurzel seines Teilbaums.
• Leerer Baum:Baum ohne Inhalt und ohne Teilbäume. Ein Blatt hat zwei leere Teilbäume.
• Tiefe:Zahl der Kanten von der Wurzel bis zum Knoten; die Wurzel hat Tiefe 0. Knoten gleicher Tiefe bilden eine Ebene.
• Höhe:Zahl der Ebenen, also größte Tiefe + 1. Der leere Baum hat Höhe 0.

Klicke einen Knoten an (oder Tab + Enter): Er wird in Wurzel, linken und rechten Teilbaum zerlegt. Zerlege weiter, bis nur noch einzelne Knoten und leere Bäume übrig sind — oder lass es mit ▶ Ebene für Ebene laufen. Pfeiltasten wandern durch den Baum.

Halte fest: Jeder Binärbaum zerfällt in eine Wurzel und zwei Teilbäume — und die sind wieder Binärbäume. Am Ende bleiben nur einzelne Knoten und leere Bäume übrig.

Im Abitur heißt die Klasse BinTree. Ein Objekt ist immer ein ganzer (Teil-)Baum — nie ein einzelner Knoten.

• BinTree()erzeugt einen leeren Baum.
• BinTree(x)erzeugt ein Blatt: Wurzel mit Inhalt x, links und rechts ein leerer Baum.
• isEmpty()liefert true, wenn der Baum leer ist.
• getItem()liefert den Inhalt der Wurzel.
• setItem(x)setzt den Inhalt der Wurzel; ein leerer Baum bekommt dabei zwei leere Teilbäume.
• isLeaf()liefert true, wenn beide Teilbäume leer sind.
• getLeft() / getRight()liefern den linken bzw. rechten Teilbaum.
• setLeft(b) / setRight(b)hängen den Baum b als linken bzw. rechten Teilbaum ein.
• setEmpty()macht den Baum zum leeren Baum.

BinTree<String> b = new BinTree<String>("B");
BinTree<String> c = new BinTree<String>("C");
BinTree<String> a = new BinTree<String>("A");
a.setLeft(b);                                  // B wird linker Teilbaum von A
a.setRight(c);                                 // C wird rechter Teilbaum von A
b.getRight().setItem("D");                     // leerer Baum wird zum Blatt D
System.out.println(a.getLeft().getItem());     // B
System.out.println(a.isLeaf() + " " + c.isLeaf());   // false true
System.out.println(b.getLeft().isEmpty());     // true

• Rekursiv denken:Was für den ganzen Baum gilt, berechnet man aus Wurzel, linkem und rechtem Teilbaum.
• Abbruch:beim leeren Baum — dort gibt es nichts mehr zu zerlegen.

static int hoehe(BinTree<String> b) {
    if (b.isEmpty()) {
        return 0;                                  // leerer Baum: keine Ebene
    }
    return 1 + Math.max(hoehe(b.getLeft()), hoehe(b.getRight()));
}
// hoehe(a) liefert für den Baum oben 3 (Ebenen A – B – D)