Ein Baum ist eine nicht-leere Menge von Knoten und Kanten, die gewisse Bedingungen erfüllen.
Ein Knoten ist ein Objekt, das einen Namen haben und weitere Informationen beinhalten kann.
Eine Kante ist eine Verbindung zwischen zwei Knoten.
Ein Pfad ist eine Folge von unterschiedlichen Knoten, die durch Kanten im Baum miteinander verbunden sind.
Die Wurzel eines Baums ist ein besonderer Knoten, der den Ursprung des Baums kennzeichnet. Es gilt immer, dass es zwischen der Wurzel und jedem beliebigen anderen Knoten eines Baums genau einen Pfad gibt.
Jeder Knoten (außer der Wurzel) hat genau einen Vorgänger, der sich direkt über ihm befindet und als sein direkter Vorgänger (parent) bezeichnet wird. Knoten, die sich direkt unter einem Knoten befinden, werden als seine direkten Nachfolger (children) bezeichnet.
Entsprechend eines Familienstammbaums spricht man auch von einem Großelterknoten oder von Geschwisterknoten.
Blätter, Endknoten und äußere Knoten sind Knoten ohne Nachfolger.
Innere Knoten sind Knoten mit mindestens einem Nachfolger.
Jeder Knoten ist die Wurzel eines Unterbaums, der aus ihm und den Knoten unter ihm besteht.
Die Ebene eines Knotens ist die Anzahl der Knoten auf dem Pfad von diesem Knoten zur Wurzel, wobei der Knoten selbst nicht mitgezählt wird und die Höhe eines Baums ist seine höchste Ebenennummer. Die Pfadlänge eines Baums ist die Summe der Ebenen aller Knoten.
Ein Wald ist ein Menge von Bäumen.
Geordnete Bäume sind Bäume, bei denen die Reihenfolge der direkten Nachfolger bei jedem Knoten festgelegt ist. Ist diese Reihenfolge nicht fest vorgeschrieben, spricht man von ungeordneten Bäumen.
Falls jeder Knoten nur eine bestimmte Anzahl n von direkten Nachfolgern haben darf, die in einer bestimmten Reihenfolge vorliegen müssen, spricht man von einem n-ären Baum.
