Dies ist eine alte Version des Dokuments!
Bäume: Einführung
Bäume dienen als hierarchisches Strukturierungsmittel oder als Organsisationsprinzip - ein Beispiel ist der nebenstehende Stammbaum, in dem Johannes Gans versucht, fast alle europäischen Herrscherdynastien auf die Nachkommenschaft Rudolfs von Habsburg zurückzuverfolgen.1)
Du kennst sicher weitere Beispiele, bei denen Daten und ihre Beziehungen zueinander als Baum strukturiert werden können.
(A1)
Finde 3 weitere Beispiele für baumartig strukturierte Daten und Zusammenhänge. Skizziere die jeweiligen Bäume in deinem Heft.
Allgemeine Begriffe
Allgemein besteht ein Baum (in der Informatik) aus Knoten und Kanten. Die Koinoten sind teilweies durch Kanten verbunden. Damit wir von einem Baum sprechen, dürfen die Knoten allerdings nicht in beliebiger Weise untereinander verbunden sein, sondern es müssen bestimmte Regeln eingehalten werden:
- Jeder Knoten - außer dem Wurzelknoten - ist durch genau eine Kante mit seinem Elternknoten (Vaterknoten, Vorgänger)verbunden. Dieser Knoten wird häufig Kind oder Nachfolger des Elternknotens genannt.
- Der Knoten ohne Elternknoten ist der Wurzelknoten. Jeder (nicht leere) Baum hat genau einen Wurzelknoten.
- Ein Knoten der keine Kinderknoten hat heißt Blatt.
- Knoten mit Eltern- und Kinderknoten heißen innere Knoten des Baums
- Ein Pfad ist eine Abfolge von Knoten, die durch Kanten miteinander verbunden sind. Bei einem Baum gibt es zwischen dem Wurzelknoten und jedem anderen Knoten genau einen Pfad. (Bäume sind "zyklenfrei" und "zusammenhängend").
- Das Niveau eines Knotens ist die Länge des Pfads vom Wurzelknoten zum betrachteten Knoten.
- Die Höhe des Baums ist die Anzahl der Knoten im längsten Pfad des Baums (oder gleichbedeutend: Das größte Niveau eines Knotens im Baum +1)
Wenn vorgegeben ist, welche (Maximal-)Zahl von Kinderknoten eine Knoten eines Baums haben darf, spricht man von einem n-ären Baum. Wenn die Kinder eines Knotens in einer bestimmten Reihenfolge geordnet sein müssen ("zuerst das linke Kind, dann das rechte"), spricht man von einem geordneten Baum.
Binärbaum
Ein sehr wichtiges Sonderfall, wen wir im weiteren betrachten werden ist der "2-äre" Baum, besser bezeichnet als binärer Baum oder Binärbaum.
- Bei einem Binärbaum hat jeder Knoten höchstens 2 Kindsknoten
- Es ist unterscheidbar, welches der linke und welches der rechte Kindsknoten ist.