Dynamische Datenstrukturen: Baum
Ein Baum ist eine Datenstruktur zur Organisation und Speicherung von Daten. Ein Baum besteht aus beliebig vielen Knoten, die durch Kanten verbunden sind. Es gibt zwischen zwei beliebig wählbaren Knoten nur einen Weg.
Bestandteile eines Baums
- Wurzel: Der Knoten, der keine Eltern hat.
- Eltern: Vorgänger eines bestimmten Knotens.
- Kind: Nachfolger eines bestimmten Knotens.
- Blatt: Knoten, die keine Kinder haben.
- Teilbaum: Knoten mit all ihren Nachfolgern.
- Höhe: Länge des Pfades von der Wurzel zu einem Knoten.
Hinweis: Um zu bestimmen, ob ein Baum geordnet ist, muss die Art der Ordnung angegeben sein.
Vergleich von Bäumen
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.
Anwendungsbeispiele von Bäumen
- KO-System bei der Fußball Weltmeisterschaft
- Organigramm in Unternehmen
- Dateistruktur im Rechner
- Hierarchische Strukturierung von Informationen, z.B. Entscheidungsbäume
Binärbaum
Ein Baum ist ein Binärbaum, wenn alle Knoten maximal zwei Kinder haben und zwischen dem linken und dem rechten Teilbaum unterschieden wird.
Tabellarische Darstellung
| Index | Inhalt | Linkes Kind | Rechtes Kind |
|---|---|---|---|
| 0 | W | 1 | 2 |
| 1 | X | 3 | NULL |
| 2 | Y | NULL | NULL |
| 3 | Z | NULL | NULL |
Besondere Binärbäume
Sortiert (Binärer Suchbaum)
Für jeden Knoten gilt:
- Der linke Teilbaum enthält nur Knoten, die kleiner sind.
- Der rechte Teilbaum enthält nur Knoten, die größer sind.
Voll
Jeder Knoten ist ein Blatt oder besitzt zwei Kinder.
Vollständig
Der Baum ist voll und alle Blätter befinden sich auf der gleichen Höhe.