Die Erarbeitung des Themas "Binärer Suchbaum" in einem Leistungskurs Informatik kann mit nachfolgendem Material gut unterstützt werden. Im Sinne eines advance organizers setzen Sie das Program GuiBinBaum ein, das die Durchführung aller relevanten Grundoperationen ermöglicht, den aktuellen Zustand des binären Suchbaums in einer Grafik darstellt und somit das Thema zugänglich macht. Es setzt eine Java-Version ab 8.40 voraus.

Das Klassendiagramm des Programms besteht aus vier Klassen:

Die beiden Klassen BinBaum und Knoten bilden das Fachkonzept. Ein binärer Suchbaum besteht aus einer Aggregation von Knoten und ein Knoten kann Nachfolgeknoten haben. Die Klasse BinBaumCanvas ist eine Unterklasse der JavaFX-Klasse Canvas. Sie stellt einen binären Suchbaum grafisch dar und so dass man eine einfache visuelle Kontrolle hat. Mit der JavaFX-Applikation GuiBinBaum lassen sich die Operationen auf einem binären Suchbaum aufrufen.

Diese vier Klassen werden den Schülerinnen und Schülern zur Verfügung gestellt, wobei in der Klasse BinBaum nur wenige Methoden implementiert aber viele Methodenrümpfe vorhanden sind. Anhand von ergänzendem Unterrichtsmaterial und auf Basis von Erarbeitungsphasen implementieren die Schülerinnen und Schüler die Operationen auf einem binären Suchbaum.

Ein Suchbaum kann durch sukzessives Einfügen von Knoten erzeugt werden. Zum Einfügen eines Knotens benötigt man eine Schleife, mit der die Einfügestelle gesucht wird. Ein rekursiver Algorithmus ist nicht nötig, da nur ein Pfad im binären Suchbaum abgelaufen wird. Das Ablaufen kann durch einen Cursor-Knoten realisiert werden. Die Implementierung kann erarbeitet oder eine gegebene analysiert werden. Zur Übung kann eine zweite Variante, die keine Doubletten zulässt, implementiert werden.

Funktioniert das Einfügen, können viele weitere Operationen implementiert werden. Zum Beispiel eine Inorder-Ausgabe des Baumes, wozu ein rekursiver Algorithmus nötig ist, weil der ganze Baum traversiert werden muss.

Das Löschen eines Knotens ist eine sehr schwierige Operation. Daher schaltet das Programm GuiBinBaum in eine zwei-Fenster-Ansicht um, bei der man den Baum vor und nach dem Löschen sehen und vergleichen kann. Die verschiedenen Fälle, die beim Löschen zu berücksichtigen sind, werden durch passende Methodenrümpfe (z. B. löscheKnotenMitEinemTeilbaum) vorstrukturiert.

Lässt man sich das Raster anzeigen, so wird deutlich, wie die grafische Ausgabe eines binären Suchbaums funktioniert. Für jeden Knoten wird eine Spalte reserviert und die Tiefe eines Knoten bestimmt seine Reihe. Zum Zeichnen einer Kante benötigt man die Nummern der beteiligten Knoten, aus denen sich die erforderlichen Koordinaten berechnen lassen.

Download des Quellcodes für die Schülerinnen und Schüler. Die heruntergeladene jar-Datei wird per Drag&Drop in den Java-Editor gezogen, wodurch dann die enthaltenen Dateien entpackt und geöffnet werden.

Gerhard Röhner
August 2019