Benutzer-Werkzeuge

Webseiten-Werkzeuge


glossar:baum

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen gezeigt.

Link zu dieser Vergleichsansicht

glossar:baum [2014/09/24 16:43] (aktuell)
Zeile 1: Zeile 1:
 +====== 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: 2014/09/24 16:43 (Externe Bearbeitung)