Traversierungen

Wenn man die Summe der in den Knoten gespeicherten Werte bestimmen möchte oder einfach die Zahl der Knoten eines Baums bestimmen will, ist die Reihenfolge, in der der jeweilige Knoten und seine Kinder abgearbeitet werden, irrelevant. Das ist aber nicht immer so, es gibt Situationen, in denen man sicherstellen möchte, dass die Knoten eines Baums in einer gewissen "Reihenfolge" durchlaufen werden. Da ein Baum jedoch nicht "geordnet" ist, wie z.B. die ganzen Zahlen, muss man hierzu Regeln festlegen, wie die Knoten durchlaufen und verarbeitet werden wollen.

Es gibt drei Traversierungsarten, die man rekursiv umsetzen kann:

• Preorder-Traversierung
• Inorder-Traversierung
• Postorder-Traversierung

• Bildet (mindestens) 3-er-Gruppen
• Sendet je (mindestens) eine Person in die Expertengruppen für Preorder-, Inorder, Postorder-Traversierung. Jede Expertengruppe recherchiert zu ihrer Spezialtraversierung und erstellt eine Mini-Präsentation (1-2 Folien, mit grafischer Veranschaulichun an einem Beispiel, Beschreibung und Pseudocode für eine rekursive Implementierung) ihrer Traversierungsart.
• Anschließend gehen die Experten zurück in ihre Stammgruppen und erklären den anderen Gruppenmitgliedern ihre Traversierungsart. Am Ende sollte jede Schülerin über einen Heftaufschrieb zu jeder Traversierungsart - und dem entsprechenden Wissen - verfügen.

Erläuterungen

Jeder bearbeitet diese Aufgabe wieder für sich alleine! Nenne jeweils die Reihenfolge, in der die Knoten besucht werden, für alle drei Traversierungen:

• Preorder-Traversierung
• Inorder-Traversierung
• Postorder-Traversierung