Benutzer-Werkzeuge

Webseiten-Werkzeuge


arithmetische_terme
Aufgabentext

GK Informatik - NRW 2007

Arithmetische Ausdrücke werden häufig in sogenannten Termbäumen dargestellt. Ein solcher Termbaum veranschaulicht den Ablauf der Berechnung des Terms.

Als Rechenoperationen sind bei dieser Aufgabe nur Addition ( + ), Subtraktion (–), Multiplikation (×) und Division ( / ) zugelassen. Als Operanden werden nur ganze Zahlen betrachtet.

Beispiel: Der oben abgedruckte Termbaum stellt den Term 3 + 7 dar.

Um den einfachen Term 3 + 7 als Teil eines komplexeren Terms zu verwenden, kann man den entsprechenden Termbaum anstelle eines Blattes in einen weiteren (komplexeren) Termbaum einhängen.

Beispiel: Der rechts abgedruckte Termbaum stellt den Term (3 + 7) × (17 − (8 + 7)) dar.

Aufgaben

a) Beschreiben Sie den Aufbau eines Binärbaums im Allgemeinen und erläutern Sie in diesem Zusammenhang die Begriffe „Wurzel“, „Blatt“ und „innerer Knoten“. Analysieren Sie den Aufbau eines wie im einführenden Text beschriebenen Termbaums. Gehen Sie dabei insbesondere auf spezielle Eigenschaften des Termbaums sowie auf seine Struktur (im Vergleich zum allgemeinen Binärbaum) ein.

b) Überführen Sie den Term ((11− 2) / 3) × (6 + 4) in den entsprechenden Termbaum. Beachten Sie dabei, dass die Struktur des Termbaums durch die Klammern im Term eindeutig festgelegt ist.

c) Entwerfen Sie ein Klassendiagramm für die Klasse Item zur Verwaltung der Inhalte eines beliebigen Baumknotens. Auf dieser Klasse sollen sowohl die Inhalte der inneren Knoten als auch die Inhalte der Blätter des Termbaums basieren.

Erläutern Sie, wie man für die von Ihnen entworfene Klasse feststellen kann, ob es sich bei einem gerade betrachteten Knoten um einen inneren Knoten oder um ein Blatt handelt.

d) Wenn man den Termbaum in Preorder-Form (Wurzel, linker Teilbaum, rechter Teilbaum – WLR) durchläuft, erhält man die sogenannte Prefix-Notation des Terms.

Geben Sie die Prefix-Notation für den Term (3 + 7) × (17 − (8 + 7)) an, der durch den oben abgedruckten Termbaum repräsentiert wird.

Übertragen Sie die Prefix-Notation − × 2 + 2 3 + 6 1 eines Terms in einen diesem Term entsprechenden Termbaum.

Die Methode mit der Signatur public String preorder(BinTree pTree) liefert den durch den Termbaum pTree gegebenen Term in der Prefix-Notation in Form eines Strings. Implementieren Sie diese Operation.

e) Gegeben sei der im Folgenden abgedruckte Auszug eines Java-Programms zur Bearbeitung von Termbäumen.

public int was(BinTree pTree){
  int lLeft, lRight, lWas;
  if (pTree.isEmpty()) 
    lWas = 0;
  else {
    lLeft  = this.was(pTree.getLeftTree());
    lRight = this.was(pTree.getRightTree());
    if (lLeft>lRight) 
      lWas = lLeft + 1;
    else 
      lWas = lRight + 1;
  }
  return lWas;
}

Analysieren Sie die Anfrage was bezüglich ihrer Wirkungsweise und ermitteln Sie, welcher Wert von ihr berechnet wird.

Anlagen

Die Klasse BinTree

In einem Objekt der Klasse BinTree werden beliebige Objekte nach dem Binärbaumprinzip verwaltet. Ein Binärbaum ist entweder leer oder besteht aus einem Knoten, dem ein Element und zwei binäre Teilbäume, die sogenannten linken und rechten Teilbäume, zugeordnet sind.

Die Klasse BinTree stellt Methoden in folgender Syntax zur Verfügung:

 public BinTree()
 public BinTree (Object pObject)
 public BinTree (Object pObject, BinTree pLeftTree, BinTree pRightTree)
 public boolean isEmpty()
 public void clear()
 public void setRootItem (Object pObject)
 public Object getRootItem()
 public void addTreeLeft (BinTree pTree)
 public void addTreeRight (BinTree pTree)
 public BinTree getLeftTree()
 public BinTree getRightTree()

Dokumentation der Methoden der Klasse BinTree

 Konstruktor BinTree()
 nachher Ein leerer Baum existiert.

 Konstruktor BinTree (Object pObject)
 nachher Der Binärbaum existiert und hat einen Wurzelknoten mit dem Inhalt
         pObject und zwei leeren Teilbäumen.

 Konstruktor BinTree (Object pObject, BinTree pLeftTree, BinTree pRighttree)
 nachher Der Binärbaum existiert, hat einen Wurzelknoten mit dem Inhalt pObject 
         sowie dem linken Teilbaum pLeftTree und dem rechten Teilbaum pRightTree.

 Anfrage isEmpty(): boolean
 nachher Diese Anfrage liefert den Wahrheitswert true, wenn der Binärbaum leer ist, 
         sonst liefert sie den Wert false.

 Auftrag clear()
 nachher Der Binärbaum ist leer.

 Auftrag setRootItem (Object pObject)
 nachher Die Wurzel hat – unabhängig davon, ob der Binärbaum leer ist oder schon 
         eine Wurzel hat – pObject als Inhalt. Eventuell vorhandene Teilbäume werden 
         nicht geändert.

 Anfrage getRootItem(): Object
 vorher  Der Binärbaum ist nicht leer.
 nachher Diese Anfrage liefert den Inhalt des Wurzelknotens des Binärbaums.

 Auftrag addTreeLeft (BinTree pTree)
 vorher  Der Binärbaum ist nicht leer.
 nachher Die Wurzel hat den übergebenen Baum als linken Teilbaum.

 Auftrag addTreeRight (BinTree pTree)
 vorher  Der Binärbaum ist nicht leer.
 nachher Die Wurzel hat den übergebenen Baum als rechten Teilbaum.

 Anfrage getLeftTree(): BinTree
 vorher  Der Binärbaum ist nicht leer.
 nachher Diese Anfrage liefert den linken Teilbaum der Wurzel des Binärbaums. 
         Der Binärbaum ist unverändert.

 Anfrage getRightTree(): BinTree
 vorher  Der Binärbaum ist nicht leer.
 nachher Diese Anfrage liefert den rechten Teilbaum der Wurzel des Binärbaums. 
         Der Binärbaum ist unverändert.

Lösungen

Modelllösung a)

Ein Binärbaum ist eine hierarchische Struktur, bestehend aus Knoten, die über Kanten miteinander verbunden sind.

Alle Knoten, außer dem sogenannten Wurzelknoten, der den Ursprung des Binärbaums bildet und daher keinen Vorgänger hat, haben einen direkten Vorgänger und bis zu zwei Nachfolger.

Ein Knoten, der keinen Nachfolger besitzt, heißt Blatt. Knoten, die kein Blatt sind, heißen innere Knoten. Ein leerer Binärbaum ist ein Binärbaum, der keine Knoten besitzt.

Alternativ ist eine rekursive Beschreibung möglich, wenn jeder Knoten seinerseits als Wurzel eines Binärbaums aufgefasst wird: Ein Binärbaum heißt leer, wenn er keinen Knoten besitzt. Ein nicht leerer Binärbaum ist eine hierarchische Struktur, bestehend aus einem Wurzelknoten, der über jeweils eine Kante mit genau zwei Teilbäumen verbunden ist. Jeder Teilbaum eines Binärbaums ist selbst ein (möglicherweise leerer) Binärbaum. Der Wurzelknoten eines Binärbaums, welcher zwei leere Teilbäume besitzt, heißt Blatt. Die übrigen Wurzelknoten des Binärbaums heißen innere Knoten.

Besondere Eigenschaften und Struktur des Termbaums: Jeder innere Knoten eines Termbaums enthält einen Operator (Rechenzeichen), jedes Blatt enthält einen Operanden (Zahl). In einem Termbaum ist jeder Knoten entweder ein Blatt (d. h., er hat keinen Nachfolger) oder er hat zwei nicht leere Teilbäume (d. h., er hat genau zwei Nachfolger).

Modelllösung b)

Termbaum zum Term ((11− 2) / 3) × (6 + 4):

Modelllösung c)

Bei der Lösung dieser Teilaufgabe sind verschiedene Varianten möglich, die gleichermaßen als richtig zu bewerten sind. Im Folgenden werden beispielhaft zwei Varianten ausgeführt.

Variante 1:

Entwurf einer Klasse Item:

Für ein Blatt belegt man im Rahmen des Konstruktors Item(int pZahl) das Attribut zBlatt mit dem Wert true. Entsprechend belegt man das Attribut zBlatt im Rahmen des Konstruktors Item(String pRechenzeichen) mit dem Wert false. Bei der Bearbeitung eines Termbaums kann man für den gerade betrachteten Knoten dann mit Hilfe der Anfrage istBlatt() überprüfen, ob es sich bei diesem Knoten um ein Blatt oder um einen inneren Knoten handelt.

Variante 2:

Entwurf einer Klasse Item:

Sowohl für innere Knoten als auch für Blätter wird ein String zugrunde gelegt. Zur Überprüfung, ob es sich bei dem betrachteten Knoten um ein Blatt handelt, analysiert man einen Teilbaum mit Hilfe der Methode getLeftTree() bzw. getRightTree() aus der Klasse BinTree. Wird ein leerer Binärbaum zurückgegeben, so ist der gerade betrachtete Knoten ein Blatt, sonst ein innerer Knoten.

(Möchte man z. B. den Wert des Terms bestimmen, so müssen die in den Blättern verwalteten Informationen in ganze Zahlen umgewandelt werden. Java stellt hierzu die Methode parseInt(String s) zur Verfügung. Sie liefert den ganzzahligen Wert des Strings s zurück, sofern der übergebene String eine ganze Zahl darstellt.)

Modelllösung d)

Prefix-Notation für den Term (3 + 7) × (17 − (8 + 7)) : × + 3 7 −17 + 8 7.

Termbaum zum Term mit der Prefix-Notation − × 2 + 2 3 + 6 1:

Implementation der Methode preorder(BinTree pTree): Variante 1 (entspricht Variante 1 aus Teilaufgabe c)):

public String preorder(BinTree pTree) {
  Item lItem;
  if (!pTree.isEmpty()) {
    lItem = (Item) pTree.getRootItem();
    if (! lItem.istBlatt() ) {
      return lItem.getRechenzeichen() + " " +
             this.preorder(pTree.getLeftTree())+ " " +
             this.preorder(pTree.getRightTree()); 
    } else {
      return String.valueOf(lItem.getZahl()) + " ";
    }
  }
  return "";
}

Variante 2 (entspricht Variante 2 aus Teilaufgabe c)):

public String preorder(BinTree pTree) {
  Item lItem;
  if (!pTree.isEmpty()) {
    lItem = (Item) pTree.getRootItem();
    return lItem.getContent()+ " " +
           this.preorder(pTree.getLeftTree())+
           this.preorder(pTree.getRightTree());
  }
  return "";
}

Modelllösung e)

Die Anfrage was ist eine rekursiv formulierte Anfrage.

Ist der betrachtete Termbaum leer, so ist die Abbruchbedingung für die Rekursion erfüllt und der Rückgabevariablen lWas wird der Wert 0 zugewiesen. Anderenfalls wird die Methode was jeweils für den linken und den rechten Teilbaum des betrachteten Termbaums rekursiv aufgerufen. Es handelt sich also um eine verzweigte Rekursion. Zum Maximum der beiden zurückgegebenen Werte wird schließlich der Wert 1 addiert.

Die Methode was liefert die Höhe des Termbaums. Für jeden nicht leeren Baum wird zunächst die Höhe seiner Teilbäume rekursiv bestimmt. (Die Höhe eines leeren Baums beträgt 0.) Anschließend wird zum Maximum der beiden zurückgegebenen Höhen der Wert 1 addiert.

arithmetische_terme.txt · Zuletzt geändert: 2014/09/01 14:25 von admin