Anleitung
Hänge einen Baum an einem ausgewählten Knoten um.
Ein Baum ist eine besondere Art von Graph, in dem alle Knoten miteinander verbunden sind, es aber keine Zyklen gibt.
Das heißt, für jedes beliebige Knotenpaar gibt es genau einen Pfad von einem Knoten zum anderen.
In dieser Übung geht es darum, einen Baum neu auszurichten, um die Dinge aus einem anderen Blickwinkel zu sehen.
Stammbäume werden zum Beispiel normalerweise aus der Perspektive des Vorfahren dargestellt:
+------0------+
| | |
+-1-+ +-2-+ +-3-+
| | | | | |
4 5 6 7 8 9
Aber ein Baum hat keine inhärente Richtung.
Dieselbe Information lässt sich aus der Perspektive jedes anderen Knotens im Baum darstellen, indem man ihn zur Wurzel hochzieht und seine Beziehungen mitzieht.
Derselbe Baum aus der Perspektive von 6 sähe also so aus:
6
|
+-----2-----+
| |
7 +-----0-----+
| |
+-1-+ +-3-+
| | | |
4 5 8 9
So können wir die Pfade zwischen zwei Knoten einfacher beschreiben.
Der Pfad von 6 nach 9 zum Beispiel (der im ersten Baum bis zur Wurzel hinauf- und dann zu einem anderen Blattknoten hinunterführt) folgt erkennbar dem Pfad 6-2-0-3-9.
Bei dieser Übung nimmst du einen Eingabebaum und richtest ihn aus der Sicht eines der Knoten neu aus.
Hinweise zur Implementierung
Das Testprogramm erstellt Bäume, indem es die variadische New-Funktion wiederholt anwendet.
Zum Beispiel erzeugt die Anweisung
tree := New("a",New("b"),New("c",New("d")))
den folgenden Baum:
"a"
|
-------
| |
"b" "c"
|
"d"
Du kannst davon ausgehen, dass es in den Testbäumen keine doppelten Werte gibt.
Die Methoden Value und Children werden vom Testprogramm verwendet, um Bäume zu zerlegen.
Der grundlegende Aufbau und die Zerlegung von Bäumen müssen funktionieren, bevor du mit dem interessanten Teil der Übung beginnst, deshalb werden sie in den ersten drei Tests separat getestet.
Die Methoden FromPov und PathTo sind der interessante Teil der Übung.
Die Methode FromPov nimmt ein String-Argument from, das einen Knoten im Baum über seinen Wert angibt.
Sie sollte einen Baum zurückgeben, dessen Wurzel den Wert from hat.
Du kannst den ursprünglichen Baum verändern und ihn zurückgeben oder einen neuen Baum erstellen und diesen zurückgeben.
Wenn du einen neuen Baum zurückgibst, darfst du den ursprünglichen Baum verbrauchen oder zerstören.
Natürlich ist es schön, ihn unverändert zu lassen.
Die Methode PathTo nimmt zwei String-Argumente from und to, die zwei Knoten im Baum über ihre Werte angeben.
Sie sollte den kürzesten Pfad im Baum vom ersten zum zweiten Knoten zurückgeben.
