Baum
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