Zehn Übungen zu den drei Traversierungen — bis zum Rekonstruieren eines Baums.
Dein Fortschritt:
0 / 0 Aufgaben
1
Übungsaufgaben
Zehn Übungen zum Klicken, Zuordnen, Rechnen und Knobeln — von AFB I bis AFB III. Jede Übung gibt sofort Rückmeldung; wenn du nicht weiterkommst, helfen die gestuften Tipps.
A1
Preorder von Hand
AFB I
Wende die Preorder-Traversierung auf den Baum t an und gib die Folge der Knoten an (ohne Kommas oder mit Kommas).
Binärbaum t
Trage deine Antwort ein — Enter prüft direkt.
Preorder: R L P Q Z T K N. Nach der Wurzel R geht es erst ganz durch den linken Teilbaum (L, P, Q, Z), bevor T an der Reihe ist.
Ansatz: Schreib zuerst die Wurzel, dann den ganzen linken Teilbaum, dann den rechten.
Weiter: Im linken Teilbaum gilt dieselbe Regel: L, dann P, dann der Teilbaum ab Q.
A2
Drei Reihenfolgen
AFB I
Ordne jede Karte der Traversierung zu, zu der sie gehört.
Ziehe jede Karte in den passenden Korb — oder wähle sie mit Enter aus und drücke dann die Ziffer des Korbs (0 legt sie zurück).
1Preorder
2Inorder
3Postorder
Die Silbe verrät die Stelle der Wurzel: pre = vor, in = zwischen, post = nach den Teilbäumen.
Ansatz: Achte darauf, wo die Wurzel W steht.
Weiter: Bei der Umrundung gegen den Uhrzeigersinn: links = zuerst, unten = zwischen, rechts = zuletzt.
A3
Stimmt's? — Traversierungen
AFB I
Gib bei jeder Aussage an, ob sie stimmt. Sie beziehen sich auf den Baum t aus A1 oder auf Binärbäume allgemein.
5 Aussagen nacheinander. Eine falsche Einschätzung reicht — dann startest du die Serie mit „Neue Runde“ neu.
Aussage 1 von 5
Die Wurzel steht in der Preorder vorn, in der Postorder hinten — in der Inorder irgendwo dazwischen.
Ansatz: Schreib die Preorder von t als Hilfe auf.
Weiter: Suche den Knoten, der am weitesten links liegt.
A4
Positionen bestimmen
AFB II
Ermittle für den Baum t aus A1 die gesuchten Knoten und Positionen.
Arbeite die Kette Schritt für Schritt ab: Erst wenn ein Schritt stimmt, wird der nächste freigeschaltet. Enter prüft.
3. Knoten der Inorder
letzter Knoten der Preorder
erster Knoten der Postorder
Position von R in der Inorder
Inorder: P L Q Z R T N K — R steht an Position 5, weil der linke Teilbaum vier Knoten hat. Preorder endet mit N, Postorder beginnt mit P.
Ansatz: Schreib alle drei Folgen vollständig auf, bevor du antwortest.
Weiter: In der Inorder stehen vor der Wurzel genau die Knoten ihres linken Teilbaums.
A5
Rechenbaum in Postorder
AFB II
Der Rechenbaum stellt den Term (8 − 2) × 3 + 4 dar. Stelle ihn in Postorder dar, indem du die Karten ordnest.
Rechenbaum
Ziehe die Karten in die richtige Reihenfolge — mit der Tastatur: ↑/↓ verschiebt, Shift+↑/↓ wechselt nur den Fokus.
18
22
3−
43
5×
64
7+
Postorder: 8 2 − 3 × 4 +. Jeder Operator steht direkt hinter seinen beiden Operanden — Klammern braucht diese Schreibweise nicht.
Ansatz: Links vor rechts, die Wurzel (der Operator) zum Schluss.
Weiter: Beginne ganz links unten mit 8 — der Operator + ist die Wurzel und steht am Ende.
A6
Postorder mit dem Stapel auswerten
AFB II
Die Folge 8 2 − 3 × 4 + wird mit einem Stapel ausgewertet: Zahlen mit push, bei einem Operator zweimal pop, rechnen, Ergebnis mit push. Berechne den Ablauf Schritt für Schritt.
Spiele den Ablauf Schritt für Schritt durch: Was passiert als Nächstes? Nur die richtige Karte bringt dich weiter.
Genau so rechnen Taschenrechner mit UPN: Die Postorder eines Rechenbaums lässt sich mit einem einzigen Stapel auswerten — höchstens zwei Werte liegen hier gleichzeitig darauf.
Ansatz: Beim Operator: das obere Element ist der rechte Operand.
Weiter: Nach jedem Operator liegt ein Wert weniger auf dem Stapel als vorher.
A7
Inorder mit Fehlern
AFB II
Die Methode soll die Inorder-Folge ausgeben. Überprüfe sie und markiere die fehlerhaften Zeilen.
In diesem Code stecken Fehler. Klicke genau die falschen Zeilen an — die richtigen musst du stehen lassen.
Der Abbruch prüft den leeren Baum, nicht das Blatt. Für Inorder steht die Ausgabe zwischen den Aufrufen für links und rechts.
Ansatz: Welcher Fall beendet die Rekursion — Blatt oder leerer Baum?
Weiter: Wo muss die Ausgabe bei L – W – R stehen?
A8
Den Baum rekonstruieren
AFB III
Von einem Baum kennt man die Preorder A B D E C F und die Inorder D B E A F C. Leite daraus die Postorder her.
Trage deine Antwort ein — Enter prüft direkt.
Die Preorder nennt die Wurzel A. In der Inorder stehen links von A die Knoten D B E (linker Teilbaum), rechts F C. Wiederholt man das für die Teilbäume, erhält man B mit Kindern D und E sowie C mit linkem Kind F. Postorder: D E B F C A.
Ansatz: Das erste Element der Preorder ist die Wurzel. Suche es in der Inorder.
Weiter: Was in der Inorder links von A steht, bildet den linken Teilbaum — für den gilt dasselbe Verfahren.
A9
Eindeutig oder nicht?
AFB III
Ein Baum hat die Preorder X Y und die Postorder Y X. Beurteile, ob diese Angaben den Baum eindeutig festlegen: Wie viele verschiedene Binärbäume passen dazu?
Rechne selbst und trage das Ergebnis ein — Enter prüft direkt.
Zwei: Y kann linkes oder rechtes Kind von X sein — beide Bäume haben die Preorder X Y und die Postorder Y X. Pre- und Postorder allein legen einen Binärbaum nicht fest; mit der Inorder dazu schon.
Ansatz: Zeichne alle Bäume mit zwei Knoten und der Wurzel X.
Weiter: Wo kann Y hängen — und ändert das die beiden Folgen?
A10
Wie viele Aufrufe?
AFB III
Bewerte die Aussagen zum Aufwand der rekursiven Traversierung und markiere alle zutreffenden.
Mehrere Antworten sind richtig. Markiere alle zutreffenden und klicke dann auf „Auswahl prüfen“.
Es gibt immer n Aufrufe für Knoten und n + 1 für leere Bäume: 2n + 1 — unabhängig von Form, Reihenfolge und Inhalt.
Ansatz: Zähle an einem kleinen Baum mit 2 Knoten alle Aufrufe.
Weiter: Ein Baum mit n Knoten hat immer n + 1 leere Teilbäume.
