L'arbre complet dans un tableau

1 et 2. Les fils de l'indice $i$ sont $2i+1$ et $2i+2$, son père $\lfloor (i-1)/2\rfloor$. Table calculée :

La hauteur mesurée vaut $3$. C'est le cas général : un arbre complet à $n$ nœuds a pour hauteur $\lfloor {\log }_{2}n\rfloor$, ce qu'on a vérifié pour $n=1,2,3,4,7,8,15,16,100,1000$ — hauteurs $0,1,1,2,2,3,3,4,6,9$.

3. Le parcours en largeur. Mesure : le parcours en largeur de cet arbre donne $8,3,9,1,6,7,5,4$, c'est-à-dire exactement l'ordre du tableau. Ce n'est pas une coïncidence : la représentation par tableau est le parcours en largeur, écrit une fois pour toutes.

Pourquoi. Le parcours en largeur visite le niveau $0$, puis le niveau $1$ de gauche à droite, etc. La représentation par tableau range le niveau $k$ aux indices $2^k-1$ à $2^{k+1}-2$, dans le même ordre. Les deux énumérations coïncident donc terme à terme.

Le parcours infixe, lui, donne $4,1,3,6,8,7,9,5$ : il n'a aucun rapport avec l'ordre du tableau.

Ce que cette représentation coûte et rapporte. Elle supprime les pointeurs — deux mots de $8$ octets par nœud sur une machine $64$ bits, contre zéro ici — et rend la mémoire contiguë, donc lue plus vite. Le prix est qu'elle n'est correcte que pour un arbre complet : sur l'arbre de l'exercice 10.1, où le niveau $2$ n'est pas plein, il faudrait laisser des trous, et un peigne de $h$ nœuds occuperait $2^{h+1}-1$ cases. C'est un cas où la structure de données impose une contrainte sur la forme, et le chapitre chap:tas montrera qu'un tas est précisément conçu pour la respecter.