Binärbaum: Knoten und Struktur

Ein Binärbaum besteht aus Knoten mit höchstens zwei Kindern (left, right). Die Wurzel hat keinen Elternknoten. Ein Blatt hat keine Kinder.

Beispiel: Wurzel A mit linkem Kind B und rechtem Kind C. B hat das linke Kind D.

Bäume modellieren Hierarchien, Ausdrucksbäume und Suchräume. Die rekursive Struktur (Knoten plus zwei Teilbäume) passt zu rekursiven Algorithmen.

Höhe als Tiefe: Maximum Depth of Binary Tree [1].

Wo gebraucht

Suchindizes, Syntaxbäume, Entscheidungsbäume, Heap-Form (als Array), UI-Layout-Hierarchien. Binärbäume sind das Minimalmodell für hierarchische Daten mit zwei Kindzeigern.

Vertiefung

Ein Binärbaum besteht aus Knoten mit höchstens zwei geordneten Kindpositionen. Links und rechts sind strukturell verschieden, selbst wenn beide Teilbäume dieselben Werte enthalten. Der leere Teilbaum wird meist durch null repräsentiert.

Die Baumform ist von der Schlüsselordnung zu trennen. Ein allgemeiner Binärbaum besitzt keine Suchinvariante. Erst ein binärer Suchbaum ordnet kleinere und grössere Schlüssel relativ zum Knoten.

Für einen endlichen Baum mit n Knoten existieren genau n - 1 Eltern-Kind-Kanten. Diese Eigenschaft folgt daraus, dass ausser der Wurzel jeder Knoten genau einen Elternknoten besitzt.

Schwierigkeitsstufen

1. Wurzel, Blatt und Teilbaum bestimmen.
2. Struktur- und Suchordnung unterscheiden.
3. Kantenanzahl eines endlichen Baums begründen.

Fallstricke

Zwei Kindpositionen bedeuten nicht, dass jeder Knoten zwei Kinder hat. Ein gemeinsamer Kindknoten oder Zyklus erzeugt zudem keinen Baum im üblichen Sinn.