Allgemeine Informatik II SoSe 2001
Prof. Dr. H. Neumann $\bullet$ Dr. K. Murmann $\bullet$ S. Geschwentner $\bullet$ Dr. F. Schwenker

6. Aufgabenblatt (bis zum 28.06.2001)

13. Aufgabe:
In dieser Aufgabe sollen eindimensionale Muster wie in der Abbildung als Binärbäume dargestellt und manipuliert werden.

Ein Muster besteht aus 16 ``Pixeln'', die jeweils schwarz oder weiss sein können. Die Wurzel des Baumes stellt das ganze Muster dar, das linke und rechte Kind jeweils die linke und rechte Hälfte des Musters. Der Baum wird solange weiter aufgeteilt, bis die Pixel, die ein Knoten darstellt, alle die gleiche Farbe haben.

  CONST PATTERNLENGTH = 16;
  TYPE 
    COLOR = (WHITE, BLACK);
    PATTERN = ARRAY [0..PATTERNLENGTH-1] OF COLOR;
    TREE = POINTER TO NODE;
    NODE = ...

Komplettieren Sie die Definition des Datentyps NODE, und implementieren Sie die folgenden Prozeduren und Funktionsprozeduren :

1. PROCEDURE ReadPattern(VAR pat : PATTERN) : BOOLEAN;
   Liesst ein Muster pat ein und gibt zurück, ob das Lesen erfolgreich war.

2. PROCEDURE BuildTree(pat : PATTERN) : TREE;
   Konstruiert den Binärbaum zum Muster pat, und gibt den Zeiger auf die Wurzel des Baumes zurück.

3. PROCEDURE GenPattern(t : TREE; VAR pat : PATTERN);
   Generiert das vom Binärbaum t repräsentierte Muster durch Auffüllen des Muster-arrays pat.

4. PROCEDURE Reflect(VAR t : TREE);
   Realisiert die Baumoperation, die der Spiegelung des Musters entspricht. (D.h. nach dieser Operation sollte der Baum das Spiegelbild des Ausgangsmusters darstellen.)

5. PROCEDURE WritePattern(pat : PATTERN);
   Gibt ein Muster aus.

Verwenden Sie hier zu 2 Module. In dem einen befinden sich die obigen Prozeduren und Typen, in dem anderen werden sie getestet. Testen Sie indem für jedes der folgenden Muster (1) der zugehörigen Baum t konstruiert wird, (2) das von t repräsentierte Muster generiert wird, (3) der gespiegelte Baum zu t generiert wird, (4) das vom gespiegelten Baum repräsentierte Muster generiert wird (0 : schwarz, 1 : weiss) :

$$0000-0000-0000-0000, \makebox[0.5cm]{} 0000-1000-0001-1000, \makebox[0.5cm]{} 0101-0100-1011-1010$$

Geben Sie für jedes Muster das regenerierte und das gespiegelte Muster aus.