Dynamische Datenstrukturen: Baum
Ein Baum ist eine Datenstruktur zur Organisation und Speicherung von Daten. Ein Baum besteht aus beliebig vielen Knoten. Zwei Knoten werden durch eine Kante verbunden. In dem abgebildeten Beispiel werden die Knoten 1 und Knoten 2 durch eine Kante verbunden. Es handelt sich um einen Baum, wenn es zwischen zwei beliebig wählbaren Knoten nur einen Weg gibt.
Bestandteile eines Baums
| Begriff | Beschreibung |
|---|---|
| Wurzel | Der Knoten, der keine Eltern hat, wird als Wurzel bezeichnet (= oberster Knoten in einem Baum). |
| Eltern | Ist der Vorgänger eines bestimmten Knotens. |
| Kind | Ein Kind ist der Nachfolger eines bestimmten Knotens. |
| Blatt | Knoten, die keine Kinder haben, werden als Blätter bezeichnet (= unterste Knoten). |
| Teilbaum | Knoten mit all ihren Nachfolgern (direkte und indirekte) werden als Teilbaum bezeichnet. |
| Höhe | Ist die Länge des Pfades von der Wurzel zu einem Knoten. Hierbei ist die Anzahl der Knoten ausschlaggebend, die auf dem Weg vom Knoten bis zur Wurzel sind. |
Bei vielen Bäumen spielt die Anordnung ihrer Knoten bzw. Teilbäume eine Rolle. Die Bäume heißen dann geordnet.
Anmerkung: Um zu bestimmen, ob ein Baum geordnet ist, muss die Art der Ordnung (Ordnungsrelation wie z.B. von A bis Z, von Z bis A, Zahlen aufsteigend, Zahlen absteigend, …) ebenfalls angegeben sein. Denn aus der Visualisierung eines einzigen Baums sind Fragen nach der Ordnung nicht beantwortbar.
Frage:
Die folgenden Bäume sind geordnet. Kann zwischen ihnen unterschieden werden oder sind sie gleich?
Baum T1 vs. Baum T2
Ja, sie können unterschieden werden, da für den Baum T1 das linke Kind von W den Inhalt X hat und für den Baum T2 das rechte Kind von W.
Antwort:
Ja, sie können unterschieden werden, da für den Baum T1 das linke Kind von W den Inhalt X hat und für den Baum T2 das rechte Kind von W.
Anwendungsbeispiele von Bäumen
- KO-System bei der Fußball Weltmeisterschaft.
- Organigramm in Unternehmen.
- Dateistruktur im Rechner.
- Zentrales Konzept einer hierarchischen Strukturierung von Informationen, z.B. Entscheidungsbäume.
Binärbaum
Ein Baum ist ein Binärbaum, wenn:
- alle Knoten maximal zwei Kinder haben
- zwischen dem linken und dem rechten Teilbaum unterschieden wird („geordnet“)
Anmerkung: Die Datenstruktur Binärbaum kann auch leer sein. Siehe hierzu: D. Knuth, Art of Computer Programming, Volume 1 (Fundamental Algorithms), 1997, Seite 312.
Schreibweise
Bäume können auch mit Hilfe einer tabellarischen Form beschrieben werden. Hierzu muss für jeden Knoten der Index (in der Regel eine laufende Nummer), der Inhalt des Knotens, das linke Kind und das rechte Kind angegeben werden. Hat ein Knoten keine Kinder, so wird NULL geschrieben.
Tabellarische Darstellung:
|
 |
