Dr. Andreas Borchert Abteilung Angewandte Informationsverarbeitung 15. Juli 2004
Michael Wiedemann Blatt 10






Allgemeine Informatik II (SS 2004)


Abgabetermin: 22. Juli 2004

10 Sortierte binäre Bäume - 10 Punkte

Im Skript findet sich ein ausführliches Beispiel zu sortierten binären Bäumen. Dieses Beispielmodul wollen wir für unser Programm benutzen. Es findet sich in den Beispielen zu diesem Blatt.
Ausgehend davon sollt Ihr zwei Module schreiben, für spezielle sortierte binäre Bäume:

• ein Modul namens NumericalTrees, das ganze Zahlen in einem sortierten binären Baum verwaltet. Im einzelnen soll das Modul einzelne Integerzahlen einfügen, bestehende Einträge (auszuwählen durch die Angabe einer Zahl) löschen, den ganzen Baum ausgeben und die Summe aller Einträge ausgeben können.
• ein Modul Namens LetterTrees, das einzelne Buchstaben verwaltet. Anstatt die Summe sollen in diesem Modul alle vorkommenden Großbuchstaben ausgeben können. Ansonsten sollten die Funktionen analog zum Modul NumericalTrees sein.

Das Modul SortedBinaryTrees soll unangetastet bleiben, Ihr könnt also nur die öffentlichen Prozeduren verwenden. Dazu solltet Ihr selbstverständlich die Funktionsweise dieses Moduls durchschaut haben. Als Hinweis, wie Eurer Module aussehen könnten, ist eine mögliche Definition zu dem Modul NumericalTrees ebenfalls in den Beispielen zu finden.

Natürlich brauchen wir weiterhin ein Hauptmodul, das die zwei Module gegebenenfalls testen kann. Dabei darf gerne mit Argumentverarbeitung gearbeitet werden, zum Beispiel zur Auswahl, welche Art von Baum verwendet werden soll (mittels Flags). Des weiteren ist eine Art Menu in das Programm einzubauen, das nach dem ersten Einlesen den Benutzer fragt, was nun zu tun sei:

Dies könnte beispielsweise so aussehen (bei Zahlen):

Auswahl angeben: d(elete), p(rint), q(uit), i(nsert), v(alue)
p
2 3 4 6 7 8 9
Auswahl angeben:
d
Zu loeschendes Element angeben: 5
Element 5 nicht gefunden!
Auswahl angeben:
d
Zu loeschendes Element angeben: 4
Element 4 erfolgreich geloescht
Auswahl angeben:
v
Summe alle Elemente im Baum: 35
Auswahl angeben:
i
Einzufuegendes Element angeben: 5
Element 5 erfolgreich eingefuegt
Auswahl angeben:
p
2 3 5 6 7 8 9
Auswahl angeben:
und so weiter ...

Viel Erfolg!