engl.: tree

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.

• Üblicherweise sagt man, die Kinder sind von links nach rechts geordnet.