Fils gauche, frère droit : ce que la conversion préserve et ce qu'elle déforme

La règle du cours : le fils gauche du binaire est le premier fils du général ; le fils droit est le frère suivant.

Les mesures.

La taille est conservée, et c'est immédiat : la conversion crée exactement un nœud binaire par nœud général, sans en perdre ni en ajouter. La preuve se fait par induction sur l'arbre général, avec le lemme correspondant sur les listes de frères.

La hauteur ne l'est pas, et elle ne peut qu'augmenter. Ici elle passe de $2$ à $3$. La raison se lit sur le dessin : les frères $B$, $C$, $D$, qui étaient au même niveau, sont devenus une chaîne descendante. Une fratrie de $k$ frères devient un peigne droit de hauteur $k-1$, ce qui est exactement le cas dégénéré du chapitre.

Le pire cas est donc frappant : un arbre général de hauteur $1$ à $k$ fils — une « étoile » — devient un binaire de hauteur $k-1$. La conversion transforme la structure la plus plate en la plus profonde.

Ce qu'on gagne quand même, et pourquoi le programme la demande. Un seul type de données, donc un seul jeu d'algorithmes : les parcours, la sérialisation, la comparaison s'écrivent une fois pour les arbres binaires et servent pour tous les arbres. Et le codage est sans perte : la conversion est bijective, on retrouve l'arbre général à partir du binaire.

Ce qu'on perd, et il faut le savoir avant de l'utiliser. Toute borne exprimée en fonction de la hauteur — et elles le sont toutes dans ce chapitre — se dégrade. Un algorithme en $O(h)$ sur le binaire n'est pas en $O(h)$ sur le général. La conversion est un outil de programmation, pas un outil d'analyse de complexité.