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

Le programme de test crée des arbres par applications répétées de la fonction variadique New. Par exemple, l'instruction suivante :

tree := New("a",New("b"),New("c",New("d")))

construit l'arbre ci-dessous :

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

On peut supposer qu'il n'y aura pas de valeurs en double dans les arbres de test.

Les méthodes Value et Children seront utilisées par le programme de test pour déconstruire les arbres.

La construction et la déconstruction de base d'un arbre doivent fonctionner avant d'aborder la partie intéressante de l'exercice, c'est pourquoi elles sont testées séparément dans les trois premiers tests.

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

La méthode FromPov prend un argument 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 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 tel quel.

La méthode PathTo prend deux arguments string from et to qui désignent deux nœuds de l'arbre par leurs valeurs. Elle doit renvoyer le chemin le plus court dans l'arbre pour aller du premier nœud au second.

---

Source

Adaptation d'un exercice de 4clojure