Baum (Datenstruktur)

In der Informatik ist ein Baum eine Datenstruktur und ein abstrakter Datentyp, mit dem sich hierarchische Strukturen abbilden lassen. Die durch die Hierarchie vorgegebenen Objekte nennt man Knoten. Typischerweise speichert jeder Knoten ausgehend von einem ersten Knoten, der Wurzel, eine Liste von Verweisen auf die ihnen untergeordneten Knoten. Diese Verweise heißen Kanten. Es ist dann üblich, bei den untergeordneten Knoten von Kindern und bei dem verweisenden Knoten von einem Elternteil zu sprechen. Auch andere der Genealogie entlehnten Bezeichnungen werden verwendet. Hat ein Knoten selbst keine Kinder, nennt man ihn ein Blatt.

Typischerweise wird gefordert, dass in Bäumen bis auf die Wurzel, die keine Eltern hat, jeder Knoten nur genau ein Elternteil haben darf.

Ein Objekt, das auf sich selbst verweist, ist kein Baum
Dieses Gebilde ist kein Baum, da B zwei Eltern hat
Dieses Gebilde ist kein Baum, da 4 zwei Eltern hat
Zwei nichtleere, unverbundene Bäume ergeben zusammen keinen Baum

Ein wichtiger Spezialfall ist der Binärbaum, in welchem jeder Knoten nur höchstens zwei Kinder haben darf.

Terminologie

Allgemein werden alle denkbaren Begriffe der Graphentheorie entlehnt. Der Unterschied zu Bäumen in der Graphentheorie besteht darin, dass für Datenstrukturen typischerweise den Kanten eine Richtung vorgegeben ist und in diesen Bäumen die Wurzel somit eindeutig bestimmt ist. Hat man eine Wurzel festgehalten, lassen sich zusätzlich zu den Begriffen, die man bei graphentheoretischen Bäumen schon hat – Abstand, Teilbaum, Knotengrad, Isomorphie –, noch Folgendes definieren: Die Tiefe eines Knotens gibt an, wie viele Kanten er von der Wurzel entfernt ist. Die Wurzel hat die Tiefe 0. Die Knoten mit derselben Tiefe bilden zusammen ein Niveau. Die Höhe eines Baumes ist dann die maximale Tiefe eines Knotens.

Basierend auf einem Artikel in:

Wikipedia.de