Elemente der Datenstruktur Baum

Bäume sind wichtige Datenstrukturen in der Informatik. Bäume sind Graphen mit speziellen Eigenschaften. Wie Graphen bestehen sie aus Knoten und Kanten. Kanten verbinden Knoten. Anders als Graphen sind Bäume immer gerichtet und enthalten niemals Kreise d.h es gibt genau einen Weg von der Wurzel zum Knoten. Bäume bilden eine Hierarchie ab.
Die hier am Beispiel eines binären Baumes erläuterten Begriffe gelten für alle Bäume.

Die Elemente

Binärbaum Beispiel
Binär Baum

Ein Baum
ist eine Datenstruktur mit genau einem Knoten (Wurzel) ohne Eltern und sonstigen Knoten mit genau einem Elternknoten.
Eine Kante
verbindet zwei Knoten in hierarchischer Beziehung.
Eltern Kind Knoten
sind Knoten in direkter (hierarchischer) Folge.
Innere Knoten
sind alle Knoten mit mindestens einem Nachfolger (Kind).
Ein Blatt
ist ein Knoten ohne Nachfolger (Kind).
Der Grad
eines Baumes entspricht der höchsten Kinderzahl (Verzweigungsgrad) eines Elternknotens.
Ein Binärbaum
hat den Grad 2.
Die Ebenen
eines Baumes werden 0 basiert von der Wurzel aus gezählt. Knoten direkter Folge haben eine Ebenendifferenz von 1.
Die Höhe
eines Baumes ist seine tiefste Ebene.
Die Weglänge
ist die Zahl der Kanten von der Wurzel bis zum entsprechenden Knoten. Sie entspricht seiner Ebene.
Im ausgeglichenem Baum
ist die max. Differenz der Weglängen aller Blätter ± 1.

Bäume können in unterschiedlicher Weise implementiert werden. Zum Beispiel als mit Verweisen verkettete Knotenobjekte oder als Array in dem der Feldindex zur 'Verkettung' genutzt wird.

Kommentar(e)

Kommentarformular ein-/ausblenden