Algorithmen und Programmierung III 

         WS 2002/2003                   Übung 7                          H. Schweppe
                                           (wegen Klausur am 10.12. verkürzt)

        Ausgabe: 28.11.2002
        Abgabe:   10.12.2002  15.00

 

Aufgabe 7.1 ( 11  P)  

Boolesche Ausdrücke, wie   true OR (true AND false) AND true werden intern oft mit  sogenannten Operatorbäumen repräsentiert. Der obige Ausdruck z.B. läßt sich darstellen als:

 

 

 

 

 

 

 

 

Hierbei stehen die booleschen Operatoren in den Knoten und die boolesche Werte in den Blättern des Baumes. Im Paket boolexp (siehe http://www.inf.fu-berlin.de/lehre/WS02/ALP3/uebungen/A7-2.zip) finden Sie Programmgerüste, mit deren Hilfe man solche Ausdrücke bearbeiten (ausgeben / auswerten) kann. Das Unterverzeichnis, in die Sie die Datei entpacken, sollte  boolexp heißen.
a) (2)  Geben Sie für die Klassen: BoolExpression, BoolOperator, BoolLiteral, And und Or das Vererbungsdiagramm an.
b) (4) Vervollständigen Sie die Klassen und testen es mit  folgendem Programm:

package boolexp;

public class Test {
 
public static void main(String argv[]) { 
   
BoolExpression boolexpr =//entspricht true OR (true AND false) AND true
     
new Or(new BoolLiteral(true),
      
      new And(new And(new BoolLiteral(true),
                  
       new BoolLiteral(false)),
            
         new BoolLiteral(true)));

  
// Die zu schreibende Klasse zum Durchlaufen (traversieren) der Baeume 

  
// CalculateTraverser c = new CalculateTraverser();
  
// boolexpr.accept(c);

 
// System.out.println(" = " + c.getResult());
 
}
}
c) (5)  Schreiben Sie eine Klasse namens boolexp.CalculateTraverser, die das Interface boolexp.Traverser implementiert. Diese Klasse  soll das Ergebnis eines booleschen Ausdrucks berechnen.

Aufgabe 7.2  ( 9  P)  
a) (3)Zeichen Sie einen Binärbaum T so dass: 
    - Jeder innere Knoten ein Zeichen enthält.
    - Der preorder-Durchlauf der Knoten von T die Zeichenkette "informatik" liefert.
    - Der inorder-Durchlauf der Knoten von T die Zeichenkette "ofrnmitaki" liefert.
b)(3) Schreiben Sie eine Haskell-Funktion, die die Knoten eines Binärbaums vom Typ
     data BT1 t  = Empty |   N (BT1 t) (BT1 t) t
  in postorder-Folge durchläuft.

c)(3) Zeigen Sie, dass Folgendes in jedem Binärbaum gilt: ist x  die Anzahl  der Knoten vom Grad 2 und b die Anzahl Blätter, so ist b= x+1 . Hinweis: durch Induktion . 


20 Punkte