Point de vue

Instructions

Réenracine un arbre sur un nœud choisi.

Un arbre est un type particulier de graphe dans lequel tous les nœuds sont connectés, mais où il n'y a pas de cycle. Autrement dit, il existe exactement un chemin pour aller d'un nœud à un autre, quelle que soit la paire de nœuds considérée.

Cet exercice consiste à réorienter un arbre pour voir les choses d'un autre point de vue. Par exemple, les arbres généalogiques sont généralement présentés du point de vue de l'ancêtre :

    +------0------+
    |      |      |
  +-1-+  +-2-+  +-3-+
  |   |  |   |  |   |
  4   5  6   7  8   9

Mais un arbre n'a pas de direction intrinsèque. Les mêmes informations peuvent être présentées du point de vue de n'importe quel autre nœud de l'arbre, en le faisant remonter à la racine et en entraînant ses relations avec lui. Ainsi, le même arbre vu depuis le nœud 6 ressemblerait à ceci :

        6
        |
  +-----2-----+
  |           |
  7     +-----0-----+
        |           |
      +-1-+       +-3-+
      |   |       |   |
      4   5       8   9

Cela permet de décrire plus simplement les chemins entre deux nœuds. Par exemple, le chemin de 6 à 9 (qui, dans le premier arbre, monte jusqu'à la racine puis redescend vers une autre feuille) suit le chemin 6-2-0-3-9.

Cet exercice consiste à prendre un arbre en entrée et à le réorienter du point de vue de l'un de ses nœuds.

Notes d'implémentation

L'objet Tree possède deux attributs :

• un label de type String
• des enfants de type List<Tree>

Le programme de test crée des arbres par applications successives de la fonction de construction Tree.of. Par exemple, l'instruction

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

construit l'arbre suivant :

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

Tu peux supposer qu'il n'y aura pas de valeurs dupliquées dans les arbres de test.

Les méthodes FromPov et PathTo sont la partie intéressante de l'exercice.

La méthode FromPov prend un argument de type string from, qui désigne un nœud de l'arbre par sa valeur. Elle doit renvoyer un arbre dont la racine porte la valeur from. Tu peux modifier l'arbre d'origine et le renvoyer, ou bien créer un nouvel arbre et renvoyer celui-ci. Si tu renvoies un nouvel arbre, tu es libre de consommer ou de détruire l'arbre d'origine. Bien sûr, il est préférable de le laisser intact.

La méthode PathTo prend deux arguments de type string, from et to, qui désignent deux nœuds de l'arbre par leur valeur. Elle doit renvoyer le plus court chemin dans l'arbre entre le premier et le second nœud.

Messages d'exception

Il est parfois nécessaire de lever une exception. Quand tu le fais, tu dois toujours inclure un message d'erreur explicite qui indique l'origine de l'erreur. Cela rend le code plus lisible et aide beaucoup au débogage.

Cet exercice en particulier exige que tu utilises le mot-clé throw pour « lever » plusieurs UnsupportedOperationException si l'on passe à la classe Tree() un arbre qui ne peut pas être réorienté, ou si aucun chemin ne peut être trouvé entre un start node et un end node. Les tests ne seront réussis que si tu throw l'exception en y joignant un message.

Pour lever une UnsupportedOperationException avec un message, écris le message comme argument du type d'exception :

// 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");

---

Source

Adaptation d'un exercice de 4clojure