Benutzer-Werkzeuge

Webseiten-Werkzeuge


glossar:baum

Baum

engl.: tree

Bedeutung

In einem endlich verzweigten Baum hat jeder Knoten endlich viele Kinder.

  • Einen Knoten ohne Kinder nennt man ein Blatt.
  • Einen Knoten mit Kindern einen innerer Knoten oder Zweig.
  • Den Knoten ohne Elter nennt man Wurzel.

Ein Baum heißt markiert, wenn jeder Knoten $k$ eine Markierung $m(k)$ besitzt.

In einem Binärbaum hat jeder Knoten maximal zwei Kinder.

Zu jedem Knoten $k$ gehört ein Unterbaum, nämlich der Baum der $k$ als Wurzel hat.

Der leerer Baum ist ein Baum ohne Knoten.

Die Tiefe eines Knotens in einem Baum ist sein Abstand zur Wurzel.

  • Der Wurzelknoten hat die Tiefe $0$. Für alle anderen Knoten $k$ gilt: $\mbox{tiefe}(k) = \mbox{tiefe}(\mbox{elternknoten}(k)) + 1$
  • Die Knoten gleicher Tiefe $t$ nennt man das Niveau $t$. Die Höhe des leeren Baumes ist $0$. Die Höhe eines nicht-leeren Baumes b ist die maximale Knotentiefe plus 1: $\mbox{höhe}(b) = \max \{\mbox{tiefe}(k) \mid k\;\mbox{Knoten von}\; b\} + 1$.

Die Größe eines Baums ist die Anzahl seiner Knoten.

Bemerkungen

  • Üblicherweise sagt man, die Kinder sind von links nach rechts geordnet.
glossar/baum.txt · Zuletzt geändert: 2015/10/05 16:55 (Externe Bearbeitung)