TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 317

Aus VoWi
Zur Navigation springen Zur Suche springen

Zum Abarbeiten der Knoten eines Binärbaumes verwendet man gerne rekursive Algorithmen, die in wohldefinierter Reihenfolge die folgenden Schritte ausführen:
(1) Bearbeite den aktuellen Knoten,
(2) Gehe zur Wurzel des linken Nachfolgebaums des aktuellen Knotens,
(3) Gehe zur Wurzel des rechten Nachfolgebaums des aktuellen Knotens.
Am Beginn steht man bei der Wurzel des Gesamtbaumes. Führt man die genannten Schritte (1) bis (3) rekursiv in der angegebenen Reihenfolge aus, so spricht man von Präordertraversierung. Beim untenstehenden Baum werden die Knoten also in folgender Reihenfolge bearbeitet: A;B;D;E;H; I;C; F;G. Wie ändert sich diese Reihenfolge, wenn man im Algorithmus jeweils die Abfolge (2)(1)(3) nimmt (Inordertraversierung), wie wenn man die Abfolge (2)(3)(1) wählt (Postordertraversierung)?

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:
{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}


Lösungsvorschlag[Bearbeiten | Quelltext bearbeiten]

Inordertraversierung[Bearbeiten | Quelltext bearbeiten]

Abarbeitung:

1 Gehe zur Wurzel des linken Nachfolgebaums des aktuellen Knotens,
2 Bearbeite den aktuellen Knoten,
3 Gehe zur Wurzel des rechten Nachfolgebaums des aktuellen Knotens.

graphische Abarbeitung:


Reihenfolge:
D,B,H,E,I,A,F,C,G

Postordertraversierung[Bearbeiten | Quelltext bearbeiten]

Abarbeitung:

1 Gehe zur Wurzel des linken Nachfolgebaums des aktuellen Knotens,
2 Gehe zur Wurzel des rechten Nachfolgebaums des aktuellen Knotens,
3 Bearbeite den aktuellen Knoten.

graphische Abarbeitung:


Reihenfolge:
D,H,I,E,B,F,G,C,A

Links[Bearbeiten | Quelltext bearbeiten]