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.
- Gib an wofür die Abkürzungen bei den Traversierungsstrategien Pre-, In- und Post-Order stehen.
- Erkläre wie man die drei Traversierungsstrategien Pre-, In- und Post-Order zeichnerisch nachvollziehen kann.
- Traversiere den folgenden Binärbaum mit den drei Traversierungsarten (Pre-, In- und Post-Order).
- 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.
In Anlehnung an https://ddi.uni-wuppertal.de/archiv/madin/material/materialsammlung/oberstufe/datenstrukturen/baeume/ab_03_traversierung.pdf (CC-BY-NC-SA).