restricted:alg-1:tp3.5 [WiKi informatique]

Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur.

====== TP 3.5 ======

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


===== Structure =====

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 : 

{{restricted:alg-1:tp3.5:arbre.png}}

===== Codage par parent =====

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$.


===== Chemins =====

==== A la racine ====

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

==== Entre deux noeuds quelconques ====

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$.