Bäume und Wälder


Zur Ablage von hierarchisch strukturierten Informationen verwendet man häufig Baumstrukturen. Wir beginnen mit zwei ernst gemeinten  Definitionen: Nach dieser Definition kann ein Wald  leer sein, ein Baum  dagegen nicht, da er zumindest die Wurzel enthält. Wir definieren weiter: 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.

Einhängen
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