Sérialiser à la main, et compter les jetons

1. On applique la définition : un nœud donne son étiquette, puis son fils gauche, puis son fils droit ; un sous-arbre vide donne #.

5 3 1 # # # 8 # #

Détail de la lecture : 5, puis le sous-arbre gauche 3 1 # # # — c'est-à-dire $3$, son fils gauche 1 # #, et son fils droit # —, puis le sous-arbre droit 8 # #. Mesuré par aller-retour : la désérialisation de cette chaîne redonne l'arbre de départ.

2. Un arbre à $n$ nœuds a exactement $2n+1$ jetons : $n$ étiquettes et $n+1$ marqueurs #. Ici : $n=4$, et l'on compte bien $9$ jetons.

Démonstration, par induction structurelle. Pour $\text{Vide}$ : $n=0$ et un seul jeton, $2\cdot 0+1=1$. Pour $\text{Nœud}(g,e,d)$ de tailles $n_g$ et $n_d$ : par hypothèse d'induction les deux sous-arbres donnent $2n_g+1$ et $2n_d+1$ jetons, auxquels s'ajoute l'étiquette, soit

$$1+(2n_g+1)+(2n_d+1)=2(1+n_g+n_d)+1=2n+1.$$

Vérifié par programme sur $2000$ arbres tirés au hasard.

Une autre lecture du même comptage : un arbre binaire à $n$ nœuds a exactement $n+1$ « places vides » — c'est le nombre de sous-arbres vides —, résultat déjà vrai au chapitre chap:arbres et qu'on retrouve ici comme un sous-produit du format.

3. Oui, les deux sont indispensables, et pour deux raisons différentes.

• Le # du fils droit de $3$ distingue « $1$ est le fils gauche de $3$ » de « $1$ est son fils droit ». Mesuré : sans marqueurs, l'arbre $8$ avec $3$ à gauche et l'arbre $8$ avec $3$ à droite donnent tous deux la même écriture 8 3. Avec marqueurs : 8 3 # # # contre 8 # 3 # #.
• Les # des feuilles marquent la fin de la descente ; sans eux, rien ne dirait quand un sous-arbre se termine, et la lecture ne pourrait pas savoir à qui rattacher le jeton suivant.

Le # n'est pas un remplissage : c'est le seul endroit du format où la forme de l'arbre est écrite. Les étiquettes, elles, ne portent que le contenu.