Ein gewurzelter Baum ist in der Graphentheorie ein spezieller Graph. Man unterscheidet gewurzelte Bäume in

• In-Trees und
• Out-Trees.

Definition

Gewurzelte Bäume sind gerichtete Graphen mit einem ausgezeichneten Knoten, der so genannten Wurzel, für die gilt, dass im Falle von Out-Trees jeder Knoten durch genau einen gerichteten Pfad von diesem aus erreichbar ist oder dass im Falle von In-Trees dieser von jedem Knoten aus durch genau einengerichteten Pfad erreichbar ist.

Weitere Begriffe

Im Falle von Out-Trees wird der maximale Ausgangsgrad als Ordnung des Baumes bezeichnet und alle Knoten mit Ausgangsgrad 0 bezeichnet man als Blätter. Als Tiefe einen Knotens bezeichnet man die Länge des Pfades von der Wurzel zu ihm und als Höhe des Baumes die Länge eines längsten Pfades. Im Falle von In-Trees bezeichnet man den maximalen Eingangsgrad des Baumes als seine Ordnung und alle Knoten mit Eingangsgrad 0 werden als Blätter bezeichnet. Als Höhe des Baumes die Länge eines längsten Pfades.

Wie bei ungerichteten Bäumen bezeichnt man auch in gewurzelten Bäumen alle Knoten die kein Blatt sind als innere Knoten. Manchmal schließt man die Wurzel dabei aber aus.

Für Out-Trees gibt es noch eine ganze Reihe weiterer Begriffe. Für einen von der Wurzel verschiedenen Knoten v bezeichnet man den Knoten, durch den er mit einer eingehenden Kante verbunden ist als Vater, Vaterknoten, Elternknoten oder Vorgänger von v. Als Vorfahren von v bezeichnet man alle Knoten, die entweder Vater von v oder Vorgänger des Vaters sind.

Umgekehrt bezeichnet man alle Knoten, die von einem beliebigen Knoten v aus durch eine ausgehende Kante verbunden sind als Kinder, Kinderknoten, Sohn oder Nachfolger von v. Als Nachfahren von v bezeichnet man Kinder von v oder deren Nachfahren. Als Geschwister oder Geschwisterknoten werden in einem Out-Tree Knoten bezeichnet, die den gleichen Vater besitzen.

Alternative Definition

Gewurzelte Bäume lassen sich auch rekursiv definieren. Sie bestehen aus einem Knoten w, der die Wurzel des Baumes darstellt, welcher ausschließlich mit den Wurzeln knotendisjunkter Bäume T₁, T₂, ..., T_n verbunden ist, bei Out-Trees in Richtung der Wurzeln von T₁, T₂, ..., T_n, wobei diese selbst Out-Trees sind und bei In-Trees in Richtung von w, wobei T₁, T₂, ..., T_n selbst In-Trees sind.