Bäume und Wälder
Zur Ablage von hierarchisch strukturierten Informationen
verwendet man häufig Baumstrukturen.
Wir beginnen mit zwei ernst gemeinten Definitionen:
- Ein Wald ist eine Menge von Bäumen.
- Ein Baum besteht aus einem Knoten, genannt Wurzel,
und einem Wald der Unterbäume.
Nach dieser Definition kann ein Wald leer sein,
ein Baum dagegen nicht,
da er zumindest die Wurzel enthält.
Wir definieren weiter:
- Ein Teilbaum ist eine Teilmenge
eines Baumes, die selbst ein Baum ist.
- Ein Blatt ist ein Teilbaum,
der keine Unterbäume mehr enthält.
Es ist eine bequeme Tradition, im Zusammenhang mit Bäumen die Analogie
zu einer (merkwürdigerweise meist rein männlichen) Familie
auszunutzen, und von Sohn, Vater, Bruder
eines Knotens zu sprechen (Großväter, Onkel und Neffen
kommen auch gelegentlich vor).
Wir veranschaulichen uns Bäume meist als verzweigte Strukturen,
oder aber einfach als Dreiecke mit der Wurzel oben(!),
wenn es uns auf die innere Struktur nicht ankommt.
Auch in der Informatik wachsen die Bäume nicht in den Himmel;
daß man gewöhnlich die Wurzel oben zeichnet,
liegt wohl daran, daß man meist mit ihr beginnt und die
Zeichenfläche von oben nach unten füllt;
die Darstellung mit links liegender Wurzel trifft man gelegentlich
an, aber eher selten.
Es liegt nahe, einen Wald als eine
verkettete Liste der Bäume
zu realisieren; dann sind, weil die Unterbäume eines Baumes
ein Wald sind, deren Wurzeln auch miteinander verkettet.
Als Anker für diese Liste verwenden
wir einen Verweis vom gemeinsamen Vater dieser Wurzelknoten
auf den Listenkopf, den ältesten Sohn,
und die Wurzelverkettung der Unterbäume geht von ihm
auf die jüngeren Brüder.
Damit sind von der Wurzel des ältesten Baumes im Wald
alle Knoten je über eine Folge von Zeigern erreichbar.
Wir kommen hier, wie auch schon bei den
doppelt verketteten Listen,
mit zwei Verweisen je Knoten aus,
jedoch ergibt sich eine völlig andere Struktur.
zurück |
Inhalt | Index |
vor |
Vorlesung
Klaus Lagally, 22. Februar 2000, 19:36