Einführung:
Verschiedene Suchbaumarten
sollen hierarchisiert aus einer Basisklasse BinBaum abgeleitet werden.
Da viele der benötigten Methoden unabhängig vom Inhalt
sind, soll von BinBaum zuerst eine Klasse SuchBaum und von dieser
die Klassen IntSuchbaum, StringSuchbaum, PointSuchbaum und AdressSuchbaum
abgeleitet werden. Die Hierarchie verdeutlicht dieses Klassendiagramm:
(Weitere Diagramm-Ansichten: [ UML1.3 ] (mit ArgoUML 0.16.1)
[ UML1.3 ] [ PHP5 ] ] (mit ArgoUML 0.18.1)
Aufgabe:
a) Erzeugen Sie dieses
Klassendiagramm mittels ArgoUML
selbst. Ergänzen Sie die Klassen PointSuchbaum und AdressSuchbaum,
markieren Sie abstrakte Methoden farbig. Welche Attribute und Methoden
sollten private, welche protected gekapselt werden?
Wechseln Sie auch in die Ansicht PHP5. Vergleichen Sie mit
den Lösungsdiagrammen.
b) Die Implementation soll in Delphi erfolgen. Ergänzen Sie hierzu die Unit binbaum.pas, die Sie hier als Datei binbaum_rumpf.txt erhalten.
c) Ergänzen Sie auch die Methoden DeleteIt und Insert in der Unit suchbaum.pas, die Sie hier als Datei suchbaum_rumpf.txt erhalten. Bei Bedarf orientieren Sie sich an den Kommentaren dort, die den Grobalgorithmus repräsentieren.
d) Die übrigen Units des Delphi-Projektes
BaumTester finden Sie hier.
Analysieren Sie die Units genau. Kompilieren Sie das Projekt zuerst
mit den von Ihnen ergänzten Units Binbaum und Suchbaum,
beseitigen Sie die Fehler. Beachten Sie auch die Informationen (Auszüge
aus der Delphi-Hilfe):
[Sichtbarkeit von Klassenelementen] [Virtuelle und abstrakte Methoden] [Schnittstellenoperator As]
e) Kontrollieren Sie nun die komplette Funktionalität Ihres Projektes. Vergleichen Sie mit dem fertigen Programm BaumTester, das Sie hier laden können.
f) Implementieren Sie im Projekt zusätzlich die noch fehlenden Funktionalitäten (Import aus Datei, Export in Datei nach Pre-, In-, PostOrder-Traversierung, Höhen- und Gewichtsbalance jedes Knotens, mittlere Weglänge ab der Wurzel, Anzahl der Knoten im Baum).
g) Das Knotenlöschen (Option Bearbeiten / Knoten / Löschen ; kurz [F3]) könnte komfortabler werden: Alle verfügbaren Knoten werden sortiert in einem Auswahlfenster angeboten (keine Mehrfachauswahl!). Implementieren Sie dies, nachdem Sie einen Grobalgorithmus hierzu formulierten.
Lösung (aber
zuerst selbst bearbeiten!)
[ zu a ]
Literatur:
Wichtiger Hinweis: Falls Inhalte von Verweisen (Links) nicht angezeigt werden, könnte das an einer falschen Konfigurierung des Zielservers liegen. Versuchen Sie dann mit Rechtsklick und Öffnen im neuen Fenster bzw. Register dort in der Adresszeile zu Beginn das angegebene Protokoll (https://) in die unsichere Variante (http://) zu ändern und den Link so aufzurufen.
Weitere Materialien:
- UML-Diagramm-Editor ArgoUML v0.18.1
- Skripte zu ArgoUML und UML
- Quelldatei des Klassendiagrammes zu a) für ArgoUML 0.18
- Kompletter Quellcode zur Ergänzung der Aufgaben f) und g):
[binbaum] [suchbaum] [suchbaumarten] [baumanzeige] [baumformular] - Demo-Versionen: [Sortierter Binärbaum] [AVL-Baum]