[ALGO 2 Homepage] Algorithmen und Datenstrukturen 2 WS 1999/2000

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"?


Last modified: Hörmanseder 2000-01-17