Pre-, In- und Postorder: Abituraufgaben – Informatik Leistungskurs

Dein Fortschritt:

0 / 0 Aufgaben

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\).

Stellen Sie den Term als Rechenbaum dar. 3 BE
Geben Sie die Preorder-, Inorder- und Postorder-Folge Ihres Rechenbaums an. 3 BE
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
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.

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)

Zuletzt wird addiert: + ist die Wurzel. Links steht (12 − 4) / 2, rechts 3 × 5.

Erwartungshorizont zu Aufgabe b)

Preorder: + / − 12 4 2 × 3 5
Inorder: 12 − 4 / 2 + 3 × 5
Postorder: 12 4 − 2 / 3 5 × +

Erwartungshorizont zu Aufgabe c)

Die Inorder-Folge 12 − 4 / 2 + 3 × 5 enthält keine Klammern. Nach Punkt-vor-Strich ergäbe sie 12 − 2 + 15 = 25 statt 19; welche Teilterme zusammengehören, geht verloren. In der Postorder-Folge steht jeder Operator direkt hinter seinen beiden Operanden — die Reihenfolge der Auswertung ist dadurch eindeutig festgelegt (umgekehrte polnische Notation), Klammern sind überflüssig.

Erwartungshorizont zu Aufgabe d)

static int auswerten(BinTree<String> b) {
    if (b.isLeaf()) {
        return Integer.parseInt(b.getItem());          // Blatt: Zahl
    }
    int links = auswerten(b.getLeft());                // erst die Teilbäume ...
    int rechts = auswerten(b.getRight());
    String op = b.getItem();                           // ... dann die Wurzel (Postorder)
    if (op.equals("+")) {
        return links + rechts;
    } else if (op.equals("-")) {
        return links - rechts;
    } else if (op.equals("*")) {
        return links * rechts;
    }
    return links / rechts;
}

Für den Baum aus a) liefert die Methode 19. Da jeder Operator genau zwei Operanden hat, sind die Teilbäume innerer Knoten nie leer.

Tiere raten

AFB II–III

In einer Rate-App denkt sich eine Person ein Tier. Die App stellt Ja-/Nein-Fragen und nennt dann ein Tier. Das Wissen der App ist ein BinTree<String>: Innere Knoten enthalten Fragen, Blätter Tiere. Bei „Ja“ geht es im linken, bei „Nein“ im rechten Teilbaum weiter.

Zum Speichern schreibt die App den Baum als Preorder-Folge in eine Datei; jeder leere Baum wird dabei als # notiert, die Einträge sind durch Kommas getrennt.

Material: Ratebaum der App (links = Ja, rechts = Nein)

F1: Kann es fliegen? · F2: Ist es ein Insekt? · F3: Lebt es im Wasser? · F4: Hat es Streifen?

Beschreiben Sie den Ablauf eines Spiels, bei dem sich die Person einen Hund denkt, und geben Sie die Zahl der gestellten Fragen an. 3 BE
Alle Tiere, die die App kennt, sollen von links nach rechts untereinander ausgegeben werden. Entwerfen dafür eine Methode static void tiereAusgeben(BinTree<String> b) in Java. 4 BE
Eine Datei enthält die Folge
Hat es Federn?, Kann es schwimmen?, Pinguin, #, #, Spatz, #, #, Hat es Flossen?, Hai, #, #, Maus, #, #
Ermitteln Sie den Baum, der zu dieser Folge gehört, und geben Sie an, wie viele # ein Baum mit n Knoten erzeugt. 4 BE
Ein Mitschüler schlägt vor, auf die #-Zeichen zu verzichten, weil sie die Datei „nur aufblähen“. Erörtern Sie diesen Vorschlag. 4 BE

Insgesamt 15 BE

Hinweise

Hinweis zu Aufgabe a)

Folgen Sie dem Pfad der Antworten „Nein“ und „Ja“.

Hinweis zu Aufgabe b)

Nur Blätter werden ausgegeben. Links vor rechts durchlaufen — Pre-, In- oder Postorder liefern hier dieselbe Reihenfolge der Blätter.

Hinweis zu Aufgabe c)

Der erste Eintrag ist die Wurzel. Danach folgt vollständig der linke Teilbaum; ein # beendet einen Ast.

Hinweis zu Aufgabe d)

Kriterien: Eindeutigkeit der Rekonstruktion, Dateigröße, Aufwand beim Einlesen.

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)

F1 „Kann es fliegen?“ — Nein → rechts zu F3 „Lebt es im Wasser?“ — Nein → rechts zu F4 „Hat es Streifen?“ — Nein → rechts zum Blatt „Hund“. Die App nennt den Hund nach drei Fragen (so viele innere Knoten liegen auf dem Pfad).

Erwartungshorizont zu Aufgabe b)

static void tiereAusgeben(BinTree<String> b) {
    if (b.isEmpty()) {
        return;
    }
    if (b.isLeaf()) {
        System.out.println(b.getItem());       // Blatt = Tier
    } else {
        tiereAusgeben(b.getLeft());             // Fragen nicht ausgeben
        tiereAusgeben(b.getRight());
    }
}

Ausgabe für den abgebildeten Baum: Biene, Adler, Hai, Zebra, Hund.

Erwartungshorizont zu Aufgabe c)

Wurzel „Hat es Federn?“; linker Teilbaum „Kann es schwimmen?“ mit den Blättern Pinguin (links) und Spatz (rechts); rechter Teilbaum „Hat es Flossen?“ mit Hai (links) und Maus (rechts).

Jeder Knoten hat zwei Plätze für Teilbäume, n − 1 davon belegen Knoten: Es entstehen \(n+1\) Zeichen # — hier 8 bei 7 Knoten.

Erwartungshorizont zu Aufgabe d)

Pro: Die Datei wird kürzer (bei n Knoten fallen n + 1 Einträge weg). Contra: Ohne # ist nicht mehr erkennbar, wo ein Teilbaum endet. Die Preorder „Frage, Tier, Tier“ passt z. B. zu mehreren Bäumen; man wüsste nicht, ob ein Eintrag Kind der Frage oder eines anderen Knotens ist. Erst mit einer zweiten Folge (z. B. der Inorder) wäre der Baum eindeutig — dann wäre die Datei aber länger als mit #. Alternative Idee: Blätter und Fragen unterscheiden (z. B. am Fragezeichen), dann lassen sich volle Binärbäume auch ohne # rekonstruieren. Fazit: Ohne Zusatzinformation ist der Vorschlag abzulehnen; die # machen die Rekonstruktion eindeutig und einfach.