TP 3.5

Pour aller plus loin que le tp3. En est la suite directe et concerne les arbres.

Utilisez la structure vue dans le tp3 pour encoder un arbre (la racine sera de numéro 0).

Comment reconnaître la racine en ne connaissant que la structure ?

Encodez l'arbre de la figure suivante :

Le codage par parent d'un arbre est une façon compacte de décrire un arbre de N noeuds. On suppose pour cela que :

• tous les sommets on un numéro unique entre 0 et N-1,
• la racine a un numéro de 0.

Le code consiste en un tableau de longueur N où la case d'indice $i$ contient l'indice du parent du noeud $i$.

Déduire du codage par parent une façon de trouver le chemin allant d'un noeud à la racine en $\mathcal{O}(N)$

Etant donné le chemin entre $i$ et la racine et le chemin entre $j$ et la racine, montrez que ces deux chemins sont identiques à partir d'un élément $k$ (cet élément pouvant être la racine).

En déduire un moyen en $\mathcal{O}(N)$ de trouver le chemin entre $i$ et $j$.