Algorithmen und |
10. Übung - abzugeben (voraussichtlich) am 18. 1. 2000 in Ihrer Übungsgruppe
Schreiben Sie ein Programm zur Verwaltung von binären Suchbäumen gemäß folgendem Implementierungsvorschlag:
DEFINITION OF MODULE BinTree; TYPE ElemT*=INTEGER; BinTreeT*=POINTER TO TreeNodeT; TreeNodeT=RECORD key:ElemT; left,right:BinTreeT; ....... END; (*record*) PROCEDURE Init*(VAR t:BinTreeT); (* Initialisierung des Baums vor der ersten Verwendung *) PROCEDURE CleanUp*(VAR t:BinTreeT); (* Aufräumungsarbeiten nach der letzten Verwendung eines Baumes *) PROCEDURE InOrder*(t:BinTreeT); (* Baumdurchlauf mit Ausgabe der Knotenwerte *) PROCEDURE Insert*(VAR t:BinTreeT; k:ElemT); (* Einfügen Element k in den Suchbaum, keine Balanzierung *) PROCEDURE Search*(t:BinTreeT; k:ElemT):BOOLEAN; (* Suchen Element k im Suchbaum *) PROCEDURE NoOfNodes*(t:BinTreeT):INTEGER; (* Liefert die Anzahl der Knoten im Baum *) PROCEDURE Height*(t:BinTreeT):INTEGER; (* Liefert die Höhe des Baums *) ... END BinTree.Ein einfachster Testtreiber ist verfügbar. Auch ein kleiner Ausschnitt aus dem Modul BinTree steht Ihnen als Arbeitsgrundlage zur Verfügung. Dokumentieren Sie das Modul BinTree. Adaptieren/korrigieren Sie soweit notwendig bzw. entsprechend Ihren Vorstellungen.
Bauen Sie einen Baum aus folgenden Zahlen (in der angegebenen) Reihenfolge auf und testen Sie Ihr Programm damit:
10, 5, 15, 3, 7, 12, 11, 8, 9, 6.
In welcher Reihenfolge werden die Knoten dieses Baumes bei Durchlauf Inorder / Preorder / Postorder "besucht"?