engl.: tree
In einem endlich verzweigten Baum hat jeder Knoten endlich viele Kinder.
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.
Die Größe eines Baums ist die Anzahl seiner Knoten.