Doppelstunde 8: Baumtraversierungen [nur LF]

Als nächstes werden die unterschiedlichen Traversierungsmethoden für Binärbäume behandelt. Die Präsentation 10_baeume_2.odp zeigt im ersten Teil zunächst, wie Algorithmen grundsätzlich strukturiert sind, die alle Knoten eines Binärbaums durchlaufen. Sinnvollerweise werden diese rekursiv formuliert, weil sich diese Lösung am einfachsten formulieren lassen. Die Schülerinnen und Schüler sollen erkennen, dass die prinzipielle Struktur beim Zählen der Knoten oder Aufsummieren der Knotenwerte eigentlich gleich ist.

Im Anschluss daran werden im dem Aufgabenblatt 10_baumalgorithmen.odt drei einfache Baumalgorithmen implementiert, um die Anzahl und die Tiefe eines Baums zu bestimmen und einen Wert im Baum suchen zu lassen. Wenn Higher-Order-Funktionen ausführlich behandelt wurden, kann man hier auch versuchen, eine Implementation von Anzahl- und Tiefenbestimmung mit dieser Technik umzusetzen.

Danach wird die Präsentation fortgesetzt. Dort werden die Unterschiede zwischen Preorder-, Postorder- und Inorder-Traversierung erklärt und jeweils Anwendungsbeispiele beschrieben. Zur Festigung dieser Prinzipien wird danach das Aufgabenblatt 10_traversierungen.odt bearbeitet. Darin werden die Traversierungsstrategien zunächst auf Papier durchgeführt und für Anwendungsfälle bestimmt, welche Traversierung jeweils erforderlich ist. Hier ist ausdrücklich keine Implementierung sondern eine Beschreibung in Pseudocode verlangt.

Als Differenzierung kann allerdings in Aufgabe 4 eine Implementation durchgeführt werden. Das Programmgerüst, das bereitgestellt wird, enthält zum einen eine GUI und zum anderen bereits die Funktionalität, um aus einem eingegebenen Term eine Baumdarstellung zu erzeugen (und den Term dabei auch auf syntaktische Korrektheit zu überprüfen). Hier soll einerseits der Zahlwert eines Rechenbaums bestimmt werden (eine Postorder-Traversierung) und andererseits eine lineare String-Darstellung ausgegeben werden (eine Inorder-Traversierung). Bei letzterer Aufgabe kann man aber nicht einfach den oben eingegebenen String wiederverwenden: Sinn der Aufgabe ist auch, dass unnötige Klammern entfernt werden. Hierbei ist den Schülerinnen und Schülern selbst überlassen, einen Algorithmus bzw. eine Entscheidungsregel zu entwickeln, wann Klammern zu setzen sind und wann nicht.

Unterrichtsverlauf: Herunterladen [odt][187 KB]

Weiter zu DS 9: Rekursive Algorithmen