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 eine Markierung besitzt.

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

Zu jedem Knoten gehört ein Unterbaum, nämlich der Baum der 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 . Für alle anderen Knoten gilt:
  • Die Knoten gleicher Tiefe nennt man das Niveau . Die Höhe des leeren Baumes ist . Die Höhe eines nicht-leeren Baumes b ist die maximale Knotentiefe plus 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: 24.09.2014 16:41 (Externe Bearbeitung)
 
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki