====== 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) [[.groesserals|Hier beispielhafte Implementierungen der Methode ''größerAls''.]] Ein binärer Suchbaum mit ''int''-Werten könnte folgenden Aufbau haben: {{ :binsuchbaum:pasted:20241018-075651.png?800 }} ===== 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)'') [[.aufgabe1:loesung|Hier geht's zur Lösung!]] ===== 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 ==== {{ :binsuchbaum:pasted:20241018-075750.png }} ^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()'' [[.aufgabe2a:loesung|Hier geht's zur Lösung!]] ===== Höhe des Binärbaums ===== {{ :binsuchbaum:definition_ebenen.svg}} 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. \\ \\ [[.hoehe:loesung|Hier geht's zur Lösung!]] **Aufgabe 4:** \\ \\ {{ :binsuchbaum:pasted:20241018-075825.png?500}} Gib die Traversierung des rechts dargestellten Baumes * InOrder * PreOrder * PostOrder an. \\ \\ [[.traversierung1:loesung|Hier geht's zur Lösung!]] **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 \\ \\ [[.traversierung2:loesung|Hier geht's zur Lösung!]] **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. \\ \\ [[.traversierung3:loesung|Hier geht's zur Lösung!]] **Aufgabe 7:** \\ Erstelle eine Methode ''public int hoehe()'', die die Höhe des binären Suchbaums zurückgibt. \\ \\ [[.aufgabehoehe:start|Hier geht's zur Lösung!]]