Bäume

Bäume allgemein

Bäume gehören zu den wichtigsten Datenstrukturen in der Informatik. Unter einem Baum versteht man eine Datenstruktur, bei der jedes Element mindestens zwei Nachfolger hat. Hier eine interessante rekursive Definition:

Ein Baum ist entweder leer oder besteht aus einem Baum mit mindestens zwei Nachfolgern.

Im folgenden Bild sehen wir einen typischen Baum. Mit Sicherheit ist dieser Baum nicht leer. Gemäß der obigen Definition könnte man das Element 100 als "Baum mit zwei Nachfolgern" bezeichnen.

Ein typischer Baum

Auch das Element 50 ist ein "Baum mit mindestens zwei Nachfolgern", genauso wie das Element 80. Das Element 50 hat ebenfalls mindestens zwei Nachfolger, das Element 4 sogar vier Nachfolger.

Betrachten wir nun einmal das Element 212. Auch dieses Element hat mindestens zwei Nachfolger, allerdings handelt es sich bei diesen beiden Nachfolgern um leere Bäume. In Graphiken wie Abb. 1 werden leere Bäume normalerweise nicht mit eingezeichnet. Wollte man dies aber tun, müsste man Pfeile zeichnen, die auf den Wert null zeigen.

Fachbegriffe

Die Wurzel des Baumes in Abb. 1 besteht aus der Zahl 100. Die Wurzel befindet sich auf dem Niveau 0 und hat zwei Nachfolger auf dem Niveau 1. Die grün gezeichneten Elemente 212, 30 und so weiter sind Blätter des Baumes, und die gelb gezeichneten Elemente 50, 80 und 4 sind innere Knoten. Die Tiefe bzw. Höhe des Baumes lässt sich leicht ablesen, sie hat den Wert 4, da der Baum genau vier Ebenen hat. Die Ordnung des Baumes hat den Wert 4, denn mehr als vier Nachfolger hat hier kein Element.

Ein anderer Baum

Eine baumartige Datenstruktur würde sich zum Beispiel gut eignen, um alle Nachfahren eines bestimmten Menschen zu speichern. Der Uropa Karl hat zwei Kinder, das Kind Kurt hat selbst wieder drei Kinder, die Tochter Mary nur zwei. Die drei Kinder von Kurt haben selbst keine Kinder, während die Tochter Kim von Mary vier Kinder hat. Olga ist dagegen kinderlos.

Binärbäume

Im Informatikunterricht der gymnasialen Oberstufe spielt vor allem ein Typ von Bäumen eine besonders wichtige Rolle, nämlich die Binärbäume. Unter einem Binärbaum versteht man einen Baum, bei dem jeder Knoten exakt zwei Nachfolger hat, einen linken und einen rechten. Diese Nachfolger sind selbst wieder Binärbäume, wie die folgende rekursive Definition zeigt.

Schauen wir uns dazu mal einen solchen Binärbaum näher an:

Die Wurzel hat zwei Nachfolger, nämlich die 212 als linken Nachfolger und die 140 als rechten Nachfolger. Der innere Knoten 212 hat die 33 als linken und die 17 als rechten Nachfolger. Die 33 hat einen linken Nachfolger; der rechte Nachfolger ist leer und wird daher nicht gezeichnet. Einen solchen Knoten bezeichnet man auch als Halbblatt. Die 17 hat zwei leere Nachfolger, ist also ein Blatt.

In der Definition des Begriffs Binärbaum tauchte noch ein interessanter Aspekt auf: Wenn der Binärbaum nicht leer ist, hat er einen linken und einen rechten Binärbaum als Nachfolger. Diesen Sachverhalt soll das nächste Bild verdeutlichen:

Der linke Nachfolger der Wurzel ist selbst wieder ein Binärbaum, genauso wie der rechte Nachfolger. Die 212 ist dann die Wurzel des linken Nachfolgers, und die 140 ist die Wurzel des rechten Nachfolgers. Auch die 212 und die 140 haben wieder je einen linken und einen rechten Nachfolger. Die 33 ist zum Beispiel die Wurzel des linken Nachfolgers der 212, und die 222 ist die Wurzel des rechten Nachfolgers der 140. Allerdings hat die 222 keine weiteren Nachfolger, ist also nicht nur die Wurzel des rechten Teilbaums, sondern gleichzeitig auch ein Blatt.