Materialien im GK/LK Informatik der Stufe 12:

Suchbaum als spezieller Binärbaum
Implementation als Klassen

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:

Weitere Materialien:


© 2008 Ziemke .:. Letzte Aktualisierung am 22. Januar 2008 durch den WebMaster.