(Binäre) Bäume

Was haben Bäume mit der Informatik zu tun?? – werden Sie Sich wahrscheinlich gefragt haben, als Sie zum ersten Mal erfahren haben, dass Bäume auch in der digitalen Welt existieren.

Sie werden sehen, dass Bäume in der Informatik einige Gemeinsamkeiten mit den natürlichen Bäumen haben. Zum Beispiel besitzen beide Blätter und Wurzel. Und genau so, wie es in der Natur etliche Arten von Bäumen gibt, existieren auch in der Informatik verschiedene Arten. Jede Art ist spezialisiert und für eine bestimmte Anwendung optimiert. Es gibt jedoch auch Unterschiede zwischen Bäumen der Informatik und natürlichen Bäumen: Sie „wachsen“ nicht in die gleiche Richtung. Bäume in der Informatik wachsen nach unten und haben dementsprechend die Wurzel oben wie ein natürlicher Baum, den Sie um 180 Grad drehen.

Ein Baum (tree) besteht aus verschiedenen Komponenten. Die wohl wichtigste ist der Knoten

Ein Knoten (node) dient zur Speicherung von Daten. Knoten sind untereinander mit Kanten (edges) verbunden.

Besitzt ein Baum keine Knoten, so ist dieser Baum leer. Besitzt er hingegen Knoten, so können diese vom Typ Wurzel (root), innerer Knoten oder Blatt (leaf) sein.
Jeder nicht leere Baum besitzt genau eine Wurzel (root), welche normalerweise oben gezeichnet wird. Da die Wurzel ganz oben ist, wächst der Baum nach unten.

Ist ein Knoten nach unten mit anderen Knoten durch Kanten verbunden, so sind diese unteren Knoten seine Kinder (child). Der obere Knoten wird als Vater (father) dieser Kinder bezeichnet.

Ein innerer Knoten (inner node) ist ein Knoten mit mindestens einem Kind. Ist ein Knoten kinderlos, so spricht man von einem Blatt (leaf).

Es gibt verschiedene Messgrößen, welche benutzt werden, um Eigenschaften eines Baumes zu beschreiben.

Die Ordnung (order) gibt an, wie viele Kinder ein innerer Knoten höchstens haben darf. Hat ein Baum zum Beispiel die Ordnung 2, so dürfen seine Knoten maximal 2 Kinder haben. Ist jedoch nur die grafische Darstellung eines Baumes vorgegeben, so lässt sich seine Ordnung nicht ablesen. An Hand einer Grafik kann nur die Ordnung bestimmt werden, welche der Baum mindestens hat.

Der Grad (degree) eines Knotens sagt aus, wie viele Kinder ein Knoten effektiv hat. Dabei gilt, dass der Grad jedes Knotens kleiner oder gleich der Ordnung des Baumes sein muss. In der folgenden Abbildung haben zum Beispiel die Knoten a und b den Grad 2 und der Knoten e hat den Grad 5.

Der Pfad (path) von Knoten v nach Knoten w gib an, welche Kanten und Knoten besucht werden, wenn man von v nach w wandert.

Die Tiefe (depth) eines Knotens v gibt an, wie lange der Pfad zur Wurzel ist.

Dabei werden alle Knoten gezählt, welche auf dem direkten Pfad von der Wurzel zum Knoten v liegen - inklusive der Wurzel und dem Knoten v selbst.

Knoten, die die gleiche Tiefe haben, werden zu Niveaus (level) zusammengefasst.

Die Höhe (height) eines Baumes entspricht der Tiefe des Knotens, welcher am weitesten von der Wurzel entfernt ist.
Somit entspricht die Höhe des Baumes dem größten Niveau aller Knoten des Baumes.

Ein Baum heißt ausgefüllt, wenn alle inneren Knoten die maximale Anzahl Kinder haben. Somit ist der Grad jedes Knotens entweder gleich der Ordnung des Baumes (innerer Knoten) oder 0 (Blatt).

Ein Baum heißt vollständig, wenn jedes Niveau die maximale Anzahl an Knoten hat. Jeder vollständige Baum ist auch ausgefüllt.

Knoten, welche den gleichen Vater haben, werden auch Brüder oder Geschwister (sibling) genannt.

⇒ Nun kennst du alle relevanten Begriffe der Bäume, welche für die anstehende Programmierung ein notwendige Grundlage sind.

Bestimmen den Typ (Wurzel, innerer Knoten, Blatt, Vater, Kind) aller Knoten in folgender Abbildung. Beachte, dass einzelne Knoten auch von mehreren Typen sein können.

Bestimmen Sie für die folgenden zwei Bäume :

• a) die Höhe,
• b) die Ordnung,
• c) die Niveaus,
• d) ob der Baum ausgefüllt ist,
• e) den Grad aller Knoten
• f) und die Tiefe jedes Knotens

Bestimmen Sie im folgenden Baum die Typen der Knoten. Füllen Sie dazu die vorgegebene Tabelle aus.

Bestimmen Sie für jeden Knoten des Baumes der Aufgabe 3 die Tiefe und den Grad.

Zeichnen Sie im Baum der Aufgabe 3 die Niveaus und die Höhe ein. Überlegen Sie sich, welche Ordnung dieser Baum haben könnte, und begründen Sie ihre Entscheidung.

Gegeben sind die drei folgenden Bäume der Ordnung 2. Entscheiden Sie, welche Bäume vollständig und welche ausgefüllt sind, und begründen Sie Ihre Antwort