Traversierung
Es gibt Fälle, in denen man alle Elemente eines Baumes ausgeben oder in eine lineare Liste überführen möchte. Dabei kommt es darauf an, in welcher Reihenfolge die Elemente im Baum ausgegeben oder in die lineare Liste eingefügt werden sollen. Die unterschiedlichen Reihenfolgen führen zu verschiedenen Arten der Traversierung.
Schau dir das folgende Video an und beantworte die nachstehenden Fragen:
Aufgaben
- Gib vier Arten der Traversierung von Binärbäumen an.
Level-Order, Pre-Order, Post-Order und In-Order
- Gib an wofür die Abkürzungen bei den Traversierungsstrategien Pre-, In- und Post-Order stehen.
Die Abkürzungen W, L und R stehen für die Reihenfolge des Durchlaufs. Zum Beispiel wird bei der Post-Order-Traversierung zuerst der linke (L) und dann der rechte (R) Teilbaum durchlaufen. Zum Schluss wird die Wurzel (W) betrachtet.
- Erkläre wie man die drei Traversierungsstrategien Pre-, In- und Post-Order zeichnerisch nachvollziehen kann.
Man zeichnet den Binärbaum. Danach zeichnet man eine Kurve um den Binärbaum, welche an allen Knoten vorbeigeht, aber nicht die Kanten kreuzt.
Anschließend zeichnet man von jedem Knoten einen Strich nach links, rechts und unten, sodass diese Striche die Kurve berühren.
Nun geht man die Kurve entlang und gibt die Knoten aus, die zur Traversierungsstrategie passen.
- Pre-Order: linker Strich
- In-Order: unterer Strich
- Post-Order: rechter Strich
- Traversiere den folgenden Binärbaum mit den drei Traversierungsarten (Pre-, In- und Post-Order).
flowchart TD
A(("G")) --> B(("D"))
A --> C(("X"))
B --> D((J))
B --> E(("C"))
C --> F(("L"))
C --> G(("W"))
G --> H(("B"))
G --> I(("M"))
- Pre: GDJCXLWBM
- Post: JCDLBWXG
- In: JDCGLXBWM
- Ein Baum wurde Post-Order traversiert. Das Ergebnis lautet
G D V Z H K L Q W E R. Gib einen Ursprungbaum an, der dieses Ergebnis liefert. Analysiere, ob du einen weiteren Ursprungbaum finden kannst oder ob dieser eindeutig ist.
Für die Ausgabe gibt es mehrere Möglichkeiten, wie der Ausgangsbaum ausgesehen haben kann.
In Anlehnung an https://ddi.uni-wuppertal.de/archiv/madin/material/materialsammlung/oberstufe/datenstrukturen/baeume/ab_03_traversierung.pdf (CC-BY-NC-SA).