______________________________________________________________

Hauptprogramm Aufgaben 9.1
___________
Quelltext:

MODULE Main;

IMPORT IO,BinaryTree;

VAR x : INTEGER;
VAR element, tree : BinaryTree.RefT;
VAR Wahl : CHAR;

(*********************************************************************)
(* Hauptprogramm zu Aufgabe 9,                                       *)
(* Fuegt Elemente in einen bin. Baunm ein, oder entfernt diese.      *)
(* Sucht Elemente, gibt Minima/Maxima aus, gibt Baum zurueck.        *)
(* Aufruf ueber Menuesteuerung.                                      *)
(*  Aufrufe:                                                         *)
(* -> insert                                                         *)
(* -> delete                                                         *)
(* -> search                                                         *)
(* -> minimum                                                        *)
(* -> maximum                                                        *)
(* -> put                                                            *)
(*********************************************************************)

BEGIN

  LOOP
    IF Wahl= '7' THEN EXIT; END; (* Beenden bei Benutzerwahl *)

    IO.Put("\n[1] Einfuegen\n");
    IO.Put("[2] Loeschen\n");
    IO.Put("[3] Suche\n");
    IO.Put("[4] Minimum\n");
    IO.Put("[5] Maximum\n");
    IO.Put("[6] Ausgabe\n");
    IO.Put("[7] Beenden des Programms\n");

    Wahl:= IO.GetChar();
    EVAL IO.GetLine();
    (**Ereignisbehandlung**)
    (* Wenn '1', dann Wert einlesen und Element hinzufuegen.    *)
    (* Wenn '2', dann Wert einlesen, suchen, Element entfernen. *)
    (* Wenn '3', dann Wert einlesen, suchen, Element ausgeben.  *)
    (* Wenn '4', dann Minimum suchen, Element ausgeben.         *)
    (* Wenn '5', dann Maximum suchen, Element ausgeben.         *)
    (* Wenn '6', dann Baum nach Groesse geordnet ausgeben.      *)
    CASE Wahl OF
    | '1' =>

      (* Wiederhole bis Erfolg: neues Element einlesen *)
      LOOP
        IO.Put("\nBitte geben sie das neue Element ein: ");
        TRY
          x:= IO.GetInt();
          EVAL IO.GetLine();
          EXIT
        EXCEPT
          | IO.Error => IO.Put("Ungueltiger Wert.\n");
            EVAL IO.GetLine();
        END;
      END;

      (* Versuche Element in Baum einzufuegen, abbrechen bei Fehler *)
      TRY
        BinaryTree.insert(tree, x);IO.Put("\n");
      EXCEPT
          | BinaryTree.WrongData => IO.Put("Wert bereits vorhanden.\n");
      END;
      
    | '2' =>

      (* Wiederhole bis Erfolg: zu loeschendes Element einlesen *)
      LOOP
        IO.Put("\nBitte geben sie das zu loeschende Element ein: ");
        TRY
          x:= IO.GetInt();
          EVAL IO.GetLine();
          EXIT
        EXCEPT
          | IO.Error => IO.Put("Ungueltiger Wert.\n");
            EVAL IO.GetLine();
        END;
      END;

      (* Suche Element und versuche Element zu entfernen, *)
      (* abbrechen bei Fehler.                            *)
      TRY
        BinaryTree.delete(tree, BinaryTree.search(tree, x));
      EXCEPT
          | BinaryTree.Empty => IO.Put("Baum leer.\n");
          | BinaryTree.WrongData => IO.Put("Wert nicht vorhanden.\n");
      END;

    | '3' =>

      (* Wiederhole bis Erfolg: zu suchendes Element einlesen *)
      LOOP
        IO.Put("\nBitte geben sie das zu suchende Element ein: ");
        TRY
          x:= IO.GetInt();
          EVAL IO.GetLine();
          EXIT
        EXCEPT
          | IO.Error => IO.Put("Ungueltiger Wert.\n");
            EVAL IO.GetLine();
        END;
      END;
      
      (* Suche Element im Baum, abbrechen bei Fehler. *)
      TRY
        element:= BinaryTree.search(tree, x);
        IO.Put("\nElement gefunden: ");IO.PutInt(element^.key);IO.Put("\n");
      EXCEPT
          | BinaryTree.Empty => IO.Put("Baum leer.\n");
          | BinaryTree.WrongData => IO.Put("Wert nicht vorhanden.\n");
      END;
      
    | '4' =>

      (* Suche Maxmimum im Baum und gib es aus, abbrechen bei Fehler. *)
      TRY
        element:= BinaryTree.minimum(tree);
        IO.Put("\nElement gefunden: ");IO.PutInt(element^.key);IO.Put("\n");
      EXCEPT
          | BinaryTree.Empty => IO.Put("Baum leer.\n");
      END;

    | '5' =>

      (* Suche Minimum im Baum und gib es aus, abbrechen bei Fehler. *)
      TRY
        element:= BinaryTree.maximum(tree);
        IO.Put("\nElement gefunden: ");IO.PutInt(element^.key);IO.Put("\n");
      EXCEPT
          | BinaryTree.Empty => IO.Put("Baum leer.\n");
      END;

    | '6' =>

      (* Versuche Baum auszugeben, abbrechen bei Fehler. *)
      TRY
        BinaryTree.put(tree);
      EXCEPT
          | BinaryTree.Empty => IO.Put("Baum leer.\n");
      END;

    ELSE
    END; (*CASE*)
  END;   (*LOOP*)

END Main.

Aufgabe 9.1
___________
Quelltext:

MODULE BinaryTree;
IMPORT IO;

VAR newElement : REF ELEMENT;

(*-------------------------------------------------------------------*)
(* Prozedur insert, liest Argumente: Baum in den eingefuegt wird,    *)
(* (tree) einzufuegendes Element (elem), keine Rueckgabewerte.       *)
(* Fuegt Element (elem) in den Baum ein.                             *)
(*-------------------------------------------------------------------*)

PROCEDURE insert(VAR tree : RefT; elem : INTEGER)
RAISES {WrongData} =

BEGIN

  (* sucht (rekursiv) passende Position und fuegt, wenn gefunden *)
  (* als neues Element in den Baum ein                           *)
  IF tree= NIL THEN  (*Baum leer, dann direkt einfuegen*)
    newElement:= NEW(RefT);
    newElement^.key := elem;
    tree:= newElement;
  (*wenn bereits vorhanden, Fehler*)
  ELSIF tree^.key = elem THEN RAISE WrongData
  
  (*Suche passende Stelle*)
  ELSIF tree^.left#NIL AND tree^.key>elem THEN
    insert(tree^.left, elem);
  ELSIF tree^.right#NIL AND tree^.key<elem THEN
    insert(tree^.right, elem);
  
  (*Untergeordnete Elemente anhaengen und neues Element*)
  (*an uebergeordnetes Element anhaengen               *)
  ELSIF tree^.left=NIL AND tree^.key>elem THEN
    newElement:= NEW(RefT);
    newElement^.parent := tree;
    newElement^.key := elem;
    tree^.left:= newElement;
  ELSIF tree^.right=NIL AND tree^.key<elem THEN
    newElement:= NEW(RefT);
    newElement^.parent := tree;
    newElement^.key := elem;
    tree^.right:= newElement;
 
  ELSE
    RAISE WrongData;
  END;

END insert;

(*-------------------------------------------------------------------*)
(* Prozedur delete, liest Argumente: Baum aus dem entfernt wird,     *)
(* (tree) Zeiger auf zu entfernendes Element (node), keine           *)
(* Rueckgabewerte. Entfernt Element aus Baum .                       *)
(*  Aufrufe:                                                         *)
(* delete -> empty                                                   *)
(* delete -> minimum                                                 *)
(*-------------------------------------------------------------------*)

PROCEDURE delete(VAR tree : RefT; node : RefT)
RAISES {Empty} =

BEGIN

  IF empty(tree) THEN (* Fehler, wenn leer. *)
    RAISE Empty;
  END;

  (* Haengt linken Ast am Minium des rechten Asts an *)
  IF node^.right#NIL AND node^.left#NIL THEN
    newElement := minimum(node^.right);
    newElement^.left := node^.left;
  ELSIF node^.right=NIL AND node^.left#NIL THEN
    node^.right := node^.left;
  ELSE
  END;

  (* Haengt Rest an uebergeordnetem Element an *)
  (* (zu loeschendes Element wird entfernt)    *)
  IF node^.parent=NIL THEN
    node^.right^.parent:= NIL;
    tree:= node^.right;
  ELSIF node^.parent^.right= node THEN
    IF node^.right#NIL THEN
      node^.right^.parent := node^.parent;
      node^.parent^.right:= node^.right;
    ELSE node^.parent^.right:= NIL;
    END;
  ELSE
    IF node^.right#NIL THEN
      node^.right^.parent := node^.parent;
      node^.parent^.left:= node^.right;
     ELSE node^.parent^.left:= NIL;
     END;
  END;

END delete;

(*-------------------------------------------------------------------*)
(* Prozedur search, liest Argumente: Baum in dem gesucht wird,       *)
(* (tree) zu suchendes Element (key), gibt Zeiger auf gefundenes     *)
(* Element zurueck.                                                  *)
(*  Aufrufe:                                                         *)
(* search -> empty                                                   *)
(*-------------------------------------------------------------------*)

PROCEDURE search(tree : RefT; key : INTEGER) : RefT
RAISES {Empty, WrongData} =

BEGIN

  IF empty(tree) THEN (* Fehler, wenn leer. *)
   RAISE Empty;
  END;

  (* Verzweigung: gefunden, gib Zeiger zurueck, rechter < , dann *)
  (* setze fort mit rechtem Teil, linker > , dann setze fort mit *)
  (* linkem Teil, sonst Fehler.                                  *)
  WHILE tree#NIL DO
    IF tree^.key=key THEN RETURN tree
    ELSIF tree^.right#NIL AND tree^.key<key THEN
      tree:= tree^.right;
    ELSIF tree^.left#NIL AND tree^.key>key THEN
      tree:= tree^.left;
    ELSE
      RAISE WrongData;
    END;
  END;

  RAISE WrongData;

END search;

(*-------------------------------------------------------------------*)
(* Prozedur minimum, liest Argumente: Baum in dem gesucht wird,      *)
(* gibt Zeiger auf gefundes Element zureck. Geht so weit nach links *)
(* wie moeglich, gibt Zeiger auf dieses Element zurueck.             *)
(*  Aufrufe:                                                         *)
(* minimum -> empty                                                  *)
(*-------------------------------------------------------------------*)

PROCEDURE minimum(tree : RefT) : RefT
RAISES {Empty} =

BEGIN

  IF empty(tree) THEN (* Fehler, wenn leer. *)
    RAISE Empty;
  END;
  
  (*Rufe solange mit lower part auf bis kl. Element*)
  IF tree^.left#NIL THEN
    tree:= minimum(tree^.left)
  END;

  RETURN tree

END minimum;

(*-------------------------------------------------------------------*)
(* Prozedur maximum, liest Argumente: Baum in dem gesucht wird,      *)
(* gibt Zeiger auf gefundes Element zureck. Geht so weit nach rechts*)
(* wie moeglich, gibt Zeiger auf dieses Element zurueck.             *)
(*  Aufrufe:                                                         *)
(* maximum -> empty                                                  *)
(*-------------------------------------------------------------------*)

PROCEDURE maximum(tree : RefT) : RefT
RAISES {Empty} =

BEGIN

  IF empty(tree) THEN (* Fehler, wenn leer. *)
    RAISE Empty;
  END;

  (*Rufe solange mit upper part auf bis gr. Element*)
  IF tree^.right#NIL THEN
    tree:= maximum(tree^.right)
  END;

  RETURN tree

END maximum;

(*-------------------------------------------------------------------*)
(* Prozedur put, liest Argumente: Baum der ausgegeben wird,          *)
(* keine Rueckgabewerte. Gibt von links unten ausgehend nach rechts  *)
(* unten alle Elemente des Baums entlang der Aeste aus.              *)
(*  Aufrufe:                                                         *)
(* put -> empty                                                      *)
(*-------------------------------------------------------------------*)

PROCEDURE put(tree : RefT)
RAISES {Empty}  =

BEGIN

  IF empty(tree) THEN (* Fehler, wenn leer. *)
   RAISE Empty;
  END;

  IF tree^.left#NIL THEN  (* Lower Branch ausgeben *)
    put(tree^.left);
    IO.PutInt(tree^.key);
    IO.Put("\t");
  END;

  IF tree=minimum(tree) THEN
    IO.PutInt(tree^.key);
    IO.Put("\t");
  END;


  IF tree^.right#NIL THEN  (* Upper Branch ausgeben *)
    put(tree^.right);
  END;

END put;

(*-------------------------------------------------------------------*)
(* Prozedur empty, liest Argumente: Baum der geprueft wird,          *)
(* gibt wahr zurueck falls Baum leer, falsch falls Baum nicht leer   *)
(* ist.                                                              *)
(*-------------------------------------------------------------------*)

PROCEDURE empty(tree : RefT) : BOOLEAN =

BEGIN

  IF tree= NIL THEN RETURN TRUE
  ELSE RETURN FALSE
  END;

END empty;

BEGIN

END BinaryTree.

Testlauf:

[1] Einfuegen
[2] Loeschen
[3] Suche
[4] Minimum
[5] Maximum
[6] Ausgabe
[7] Beenden des Programms
6
Baum leer.

[1] Einfuegen
[2] Loeschen
[3] Suche
[4] Minimum
[5] Maximum
[6] Ausgabe
[7] Beenden des Programms
1

Bitte geben sie das neue Element ein: 5


[1] Einfuegen
[2] Loeschen
[3] Suche
[4] Minimum
[5] Maximum
[6] Ausgabe
[7] Beenden des Programms
1

Bitte geben sie das neue Element ein: 4

[1] Einfuegen
[2] Loeschen
[3] Suche
[4] Minimum
[5] Maximum
[6] Ausgabe
[7] Beenden des Programms
1

Bitte geben sie das neue Element ein: 3


[1] Einfuegen
[2] Loeschen
[3] Suche
[4] Minimum
[5] Maximum
[6] Ausgabe
[7] Beenden des Programms
1

Bitte geben sie das neue Element ein: 2


[1] Einfuegen
[2] Loeschen
[3] Suche
[4] Minimum
[5] Maximum
[6] Ausgabe
[7] Beenden des Programms
1

Bitte geben sie das neue Element ein: 8


[1] Einfuegen
[2] Loeschen
[3] Suche
[4] Minimum
[5] Maximum
[6] Ausgabe
[7] Beenden des Programms
1

Bitte geben sie das neue Element ein: 7


[1] Einfuegen
[2] Loeschen
[3] Suche
[4] Minimum
[5] Maximum
[6] Ausgabe
[7] Beenden des Programms
1

Bitte geben sie das neue Element ein: 9


[1] Einfuegen
[2] Loeschen
[3] Suche
[4] Minimum
[5] Maximum
[6] Ausgabe
[7] Beenden des Programms
1

Bitte geben sie das neue Element ein: 6


[1] Einfuegen
[2] Loeschen
[3] Suche
[4] Minimum
[5] Maximum
[6] Ausgabe
[7] Beenden des Programms
6
2       3       4       5       6       7       8       9
[1] Einfuegen
[2] Loeschen
[3] Suche
[4] Minimum
[5] Maximum
[6] Ausgabe
[7] Beenden des Programms
2

Bitte geben sie das zu loeschende Element ein: 7

[1] Einfuegen
[2] Loeschen
[3] Suche
[4] Minimum
[5] Maximum
[6] Ausgabe
[7] Beenden des Programms
6
2       3       4       5       6       8       9
[1] Einfuegen
[2] Loeschen
[3] Suche
[4] Minimum
[5] Maximum
[6] Ausgabe
[7] Beenden des Programms
4

Element gefunden: 2

[1] Einfuegen
[2] Loeschen
[3] Suche
[4] Minimum
[5] Maximum
[6] Ausgabe
[7] Beenden des Programms
5

Element gefunden: 9

[1] Einfuegen
[2] Loeschen
[3] Suche
[4] Minimum
[5] Maximum
[6] Ausgabe
[7] Beenden des Programms
2

Bitte geben sie das zu loeschende Element ein: 5

[1] Einfuegen
[2] Loeschen
[3] Suche
[4] Minimum
[5] Maximum
[6] Ausgabe
[7] Beenden des Programms
6
2       3       4       6       8       9
[1] Einfuegen
[2] Loeschen
[3] Suche
[4] Minimum
[5] Maximum
[6] Ausgabe
[7] Beenden des Programms
7

Testlaufende.