Représentation de l'arbre de parcours
Il est possible de représenter un arbre dont les fils ne sont pas triés
(on ne s'intéresse pas à la notion de fils le plus à gauche) en partant
des feuilles pour remonter vers la racine. Il suffit d'associer à chaque
noeud de l'arbre le noeud de son père. Il est ainsi très facile de retrouver
le chemin qui va de la racine vers une feuille donnée (ici, la station
d'arrivée).
Dans notre cas, il suffira donc d'un tableau d'entiers qui, pour chaque
noeud, indique soit une valeur négative si le noeud n'est pas dans l'arbre,
soit sa propre valeur s'il est la racine de l'arbre, soit le numéro de son
père dans l'arbre. Notez qu'il faudra aussi stocker quelque part à quelle
ligne de métro correspond cette arête.
Retour au sujet