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.

---

Source

Adaptation d'un exercice de 4clojure