POV

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.

---

Quelle

Adaption einer Übung von 4clojure