MINT üben

Pre-, In- und Postorder

Zwei Abituraufgaben zu Traversierungen — vom Taschenrechner bis zur Rate-App.

Dein Fortschritt:
0 / 0 Aufgaben
1

Rechenbaum im Taschenrechner

AFB I–II

Ein Taschenrechner-Programm zerlegt einen eingegebenen Term in einen Rechenbaum vom Typ BinTree<String>. Die Blätter enthalten Zahlen, die inneren Knoten die Operatoren +, -, * und / (ganzzahlige Division). Der Operator eines Knotens verknüpft das Ergebnis seines linken mit dem seines rechten Teilbaums. Eingegeben wird der Term \((12-4)/2+3\cdot 5\).

  1. Stellen Sie den Term als Rechenbaum dar. 3 BE
  2. Geben Sie die Preorder-, Inorder- und Postorder-Folge Ihres Rechenbaums an. 3 BE
  3. Erklären Sie, warum sich aus der Inorder-Folge allein der eingegebene Term nicht eindeutig zurückgewinnen lässt, aus der Postorder-Folge aber schon. 3 BE
  4. Implementieren Sie die Methode static int auswerten(BinTree<String> b), die den Wert eines nicht leeren Rechenbaums liefert. Zahlen können mit Integer.parseInt umgewandelt werden. 5 BE

Insgesamt 14 BE

Hinweise

Hinweis zu Aufgabe a)
Der zuletzt auszuführende Operator bildet die Wurzel.
Hinweis zu Aufgabe b)
Links vor rechts; nur die Stelle der Wurzel ändert sich.
Hinweis zu Aufgabe c)
Setzen Sie in die Inorder-Folge an verschiedenen Stellen Klammern — ändert sich der Wert?
Hinweis zu Aufgabe d)
Ein Blatt liefert seine Zahl. Sonst: erst beide Teilbäume auswerten, dann den Operator der Wurzel anwenden — das ist Postorder.