Inhaltsverzeichnis
Binäre Suchbäume
Binäre Suchbäume (auch: sortierte Binärbäume oder geordnete Binärbäume) sind Binärbäume, die zusätzlich sortiert (bzgl. eines bestimmten Merkmals, z.B. Größe) sind:
Die Inhalte der linken Nachfolger eines Knotens sind dabei immer (bzgl. der gewählten Ordnung) kleiner und die Inhalte der rechten Nachfolger sind immer größer als der Inhalt des aktuellen Knotens.
Dazu ist in der Inhaltsklasse zusätzlich eine Methode größerAls notwendig, die den Rückgabewert true, besitzt, falls das aktuelle Objekt größer als das übergebene Objekt ist und ansonsten false:
public boolean größerAls(Inhalt i)
Hier beispielhafte Implementierungen der Methode ''größerAls''.
Ein binärer Suchbaum mit int-Werten könnte folgenden Aufbau haben:
Implementierung
Aufgabe 1
Ergänze den binären Suchbaum um folgende Methoden:
- Anzahl der enthaltenen Elemente (Methode
int anzahl()) - Prüfung, ob ein bestimmtes Element enthalten ist (Methode
boolean istEnthalten(int n))
Traversierung (Durchlaufen) des Baumes
Zum Durchlaufen (Traversierung) eines binären Suchbaums sind verschiedene Varianten üblich. An dieser Stelle werden beispielhaft drei bedeutende Varianten genannt:
InOrder
Es wird rekursiv zuerst der linke Teilbaum durchlaufen, dann der aktuelle Knoten besucht und anschließend der rechte Teilbaum.
PreOrder
Es wird zuerst der aktuelle Knoten besucht, dann werden rekursiv der linke und der rechte Teilbaum durchlaufen.
PostOrder
Es wird zuerst rekursiv der linke Teilbaum, dann der rechte Teilbaum durchlaufen und dann der aktuelle Knoten besucht.
Beispiel
| InOrder | PreOrder | PostOrder |
|---|---|---|
| Archäologie | Informatik | Archäologie |
| Biologie | Biologie | Chinesisch |
| Chemie | Archäologie | Chemie |
| Chinesisch | Chemie | Biologie |
| Informatik | Chinesisch | Latein |
| Latein | Mathematik | Sport |
| Mathematik | Latein | Spanisch |
| Spanisch | Spanisch | Mathematik |
| Sport | Sport | Informatik |
Aufgabe 2
Ergänze den binären Suchbaum um die Methoden
void traversePreOrder()void traversePostOrder()
Höhe des Binärbaums
Als Höhe des Binärbaumes bezeichnet man die Anzahl der enthaltenen "Ebenen", d.h. die maximale Anzahl der Ebenen von der Wurzel bis zu einem Abschluss. Ein vollständig gefüllter Binärbaum der Höhe $n$ hat $2^n - 1$ Elemente.
Ein Binärbaum mit möglichst wenigen Ebenen heißt balancierter Binärbaum.
Der Baum rechts hat die Höhe 3.
Aufgabe 3:
Ermittle, wie viele Ebenen ein balancierter binärer Suchbaum mit
- 12
- 1500
- 10 000 000 000
Elementen besitzt.
Hier geht's zur Lösung!
Aufgabe 4:
Gib die Traversierung des rechts dargestellten Baumes
- InOrder
- PreOrder
- PostOrder
Aufgabe 5:
Gib einen binären Suchbaum an (als Text oder als Grafik, z.B. mit UMLet), der folgende Ausgabereihenfolge erzeugt:
- preOrder: 39, 20, 18, 10, 51, 93, 64, 77, 97
- postOrder: 10, 18, 20, 77, 64, 97, 93, 51, 39
Aufgabe 6:
In einen (leeren) binären Suchbaum sollen folgende Einträge eingefügt werden:
15, 46, 1, 28, 100, 99, 3
Gib jeweils eine Einfügereihenfolge an, bei der der binäre Suchbaum maximale (d.h. 7) bzw. minimale (d.h. 3) Höhe hat. Finde eine allgemeine Strategie für die minimale Höhe.
Hier geht's zur Lösung!
Aufgabe 7:
Erstelle eine Methode public int hoehe(), die die Höhe des binären Suchbaums zurückgibt.
Hier geht's zur Lösung!