Ready to put your newfound language skills into use? Get 40% off CodeCrafter's real-world proficiency projects!

Sichere dir deinen Rabatt

Tracks

Java

Übungen

POV

Schwer

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

Ein Baum-Objekt hat zwei Attribute:

String label
List<Tree> children

Das Testprogramm erzeugt Bäume durch wiederholtes Anwenden der Builder-Funktion Tree.of. Zum Beispiel konstruiert die Anweisung

Tree tree = Tree.of("a", List.of(Tree.of("b"), Tree.of("c", List.of(Tree.of("d")))));

den folgenden Baum:

      "a"
       |
    -------
    |     |
   "b"   "c"
          |
         "d"

Du kannst davon ausgehen, dass es in den Testbäumen keine doppelten Werte gibt.

Die Methoden FromPov und PathTo sind der interessante Teil der Übung.

Die Methode FromPov nimmt ein String-Argument from entgegen, das einen Knoten im Baum über seinen Wert angibt. Sie soll einen Baum zurückgeben, in dessen Wurzel der Wert from steht. Du kannst den ursprünglichen Baum verändern und ihn zurückgeben oder einen neuen Baum erzeugen 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 entgegen, die zwei Knoten im Baum über ihre Werte angeben. Sie soll den kürzesten Pfad im Baum vom ersten zum zweiten Knoten zurückgeben.

Exception-Meldungen

Manchmal ist es notwendig, eine Exception zu werfen. Wenn du das tust, solltest du immer eine aussagekräftige Fehlermeldung angeben, die zeigt, was die Fehlerursache ist. Das macht deinen Code lesbarer und hilft beim Debuggen erheblich.

Diese Übung erfordert, dass du das throw-Schlüsselwort verwendest, um mehrere UnsupportedOperationException zu „werfen“, wenn der Klasse Tree() ein Baum übergeben wird, der nicht neu ausgerichtet werden kann, oder wenn zwischen einem start node und einem end node kein Pfad gefunden werden kann. Die Tests bestehen nur, wenn du sowohl throw verwendest als auch eine Meldung für die exception angibst.

Um eine UnsupportedOperationException mit einer Meldung zu werfen, gibst du die Meldung als Argument für den exception-Typ an:

// when a tree cannot be oriented to a new node POV
throw new UnsupportedOperationException("Tree could not be reoriented");

// when a path cannot be found between a start and end node on the tree.
throw new UnsupportedOperationException("No path found");