12
1 Botanique
Fig. 1.9 Nous oublions les liens d’origine. . .
Fig. 1.10 . . . et nous redressons l’arbre ; la racine n’a jamais de fille droite et peut être oubliée !
– L’image par φ de l’arbre vide est l’arbre vide.
– Soit u un nœud de τ ; le nœud φ(u) dans φ(τ ) a pour enfant gauche l’image par
φ de la fille aînée de u et pour enfant droit l’image par φ de la sœur droite de u,
i.e., le nœud suivant u dans l’ordre des enfants de leur parent commun.
Par conséquent :
– si u est une feuille de τ qui est le dernier enfant de la fratrie, φ(u) est une feuille
de φ(τ ).
– un arbre planaire réduit à sa racine a pour image par φ un arbre binaire réduit à
sa racine.
Il n’est pas difficile de se convaincre que, pour tout n ≥ 0, φ est une bijection de
P n ∪ {ε}, ensemble des arbres planaires de taille n augmenté de l’arbre vide, vers
l’ensemble des arbres binaires de taille n tels que la racine soit toujours un nœud
sans fille droite. La racine de cet arbre binaire n’apporte donc aucune information,
et peut être supprimée. Nous obtenons alors, pour tout n > 0, une bijection de