3.0 Bäume

Bei der Datenstruktur Liste hatte jedes Element nur einen Nachfolger (das letzte Element gar keinen). Lässt man mehrere Nachfolger zu, so erhält man die Datenstruktur Baum.

Ein Baum

• besteht aus Knoten, in denen Inhalte abgelegt sind und Kanten, die jeweils zwei Knoten (genannt Vorgänger und Nachfolger) verbinden.
• Jeder Knoten hat dabei maximal einen Vorgänger
• (es gibt genau einen Knoten ohne Vorgänger, der als Wurzel bezeichnet wird) und
• beliebig viele Nachfolger.
• Knoten ohne Nachfolger heißen Blatt.
• Knoten, die weder die Wurzel noch Blätter sind heißen innere Knoten.

Baumstrukturen finden an vielen Stellen in der Informatik Verwendung, beispielsweise bei der Speicherung des Datenbestands von Datenbanken. Sie sorgen für effiziente Möglichkeiten zur Ablage und zum Abrufen von Daten.

Beispielbaum:
Oft stellt man den Baum so dar, dass die Kanten nach unten hin zu den Nachfolgerknoten zeigen. So spart man sich das Zeichen von Pfeilen.

Abgrenzung zur allgemeineren Datenstruktur Graph:
Ein Baum ist ein zusammenhängender zyklenfreier ungerichteter Graph.

Spezialfall Binärbaum:
Ein Binärbaum ist ein Baum, in dem jeder Knoten maximal zwei Nachfolger hat.

Verwendet man zur Implementierung eines Baumes das Entwurfsmuster Kompositum, so ergibt sich folgendes Klassendiagramm: Sowohl die Wurzel, als auch innere Knoten und Blätter sind als Knoten angelegt. Die Klasse Abschluss kommt an den Stellen zum Einsatz, an denen es keine Nachfolger gibt. Die Ablage der Nachfolger kann beispielsweise über ein Array oder eine Liste geschehen. In vielen Anwendungsfällen ist die Speicherung in einem Array durchaus üblich (insbesondere da die Höchstzahl der Nachfolger häufig beschränkt wird).

Ein Binärbaum ist ein Baum, bei dem jeder Knoten maximal zwei Nachfolger besitzt. Das Klassendiagramm für die Implementierung eines Binärbaums unter Verwendung des Entwurfsmusters Kompositum ändert sich nur geringfügig: Die Kardinalität 2 anstelle von 0..2 im Klassendiagramm trifft (aus technischer Sicht) daher zu, als bei fehlenden Nachfolgeknoten Abschlussobjekte ihren Platz einnehmen.