Anleitung
Einen Zipper für einen Binärbaum erstellen.
Zipper sind eine rein funktionale Art, innerhalb einer Datenstruktur zu navigieren und sie zu verändern.
Sie bestehen im Wesentlichen aus einer Datenstruktur und einem Zeiger in diese Datenstruktur (der Fokus genannt wird).
Ein Zipper könnte zum Beispiel für einen Rose Tree (bei dem jeder Knoten einen Wert und eine Liste von Kindknoten enthält) die folgenden Operationen unterstützen:
-
from_tree (erzeugt einen Zipper aus einem Rose Tree, der Fokus liegt auf dem Wurzelknoten)
-
to_tree (erzeugt den Rose Tree aus dem Zipper)
-
value (gibt den Wert des Fokusknotens zurück)
-
prev (verschiebt den Fokus zum vorherigen Kindknoten desselben Elternknotens,
gibt einen neuen Zipper zurück)
-
next (verschiebt den Fokus zum nächsten Kindknoten desselben Elternknotens, gibt
einen neuen Zipper zurück)
-
up (verschiebt den Fokus zum Elternknoten, gibt einen neuen Zipper zurück)
-
set_value (setzt den Wert des Fokusknotens, gibt einen neuen Zipper zurück)
-
insert_before (fügt einen neuen Unterbaum vor dem Fokusknoten ein, er wird zum
prev des Fokusknotens, gibt einen neuen Zipper zurück)
-
insert_after (fügt einen neuen Unterbaum nach dem Fokusknoten ein, er wird zum
next des Fokusknotens, gibt einen neuen Zipper zurück)
-
delete (entfernt den Fokusknoten und alle Unterbäume, der Fokus wandert zum
next-Knoten, wenn möglich, ansonsten zum prev-Knoten, wenn möglich,
ansonsten zum Elternknoten, gibt einen neuen Zipper zurück)
Umfang
Die Klasse Tree ist bereits für dich implementiert.
Deine Aufgabe ist es, die Klasse Zipper zu schreiben.
