8
1 Botanique
Fig. 1.4 Un exemple d’arbre
infini : le peigne
exemple, le peigne de la figure 1.4 est un arbre pour la première définition ; c’est
l’ensemble (infini) des mots {1 n , n ≥ 0} ∪ {1 n 2, n ≥ 0}. Par bonheur, l’ensemble
des arbres finis selon la première définition est isomorphe à l’ensemble des arbres
de la définition récursive ; c’est pour cela que nous avons employé la même notation
P dans les deux définitions pour désigner l’ensemble des arbres planaires, bien
qu’ils ne désignent pas le même ensemble. . . Il en va de même pour d’autres classes
d’arbres que nous verrons par la suite. C’est pourquoi nous travaillerons, selon
les analyses et les méthodes qu’elles requièrent, avec l’une ou l’autre des deux
définitions des arbres, sans avoir besoin de le préciser.
1.1.2 Arbres binaires et arbres binaires complets
Comme dans la section précédente, deux points de vue et deux définitions sont
possibles, l’une comme ensemble de mots sur l’alphabet {0, 1}, qui produit des
arbres finis ou infinis, l’autre comme classe combinatoire, qui conduit à des arbres
finis.
A. Représentation canonique des arbres binaires et des arbres binaires complets Dans les définitions qui suivent, les nœuds de l’arbre sont des mots sur
l’alphabet à deux lettres 3 {0, 1}, c’est-à-dire des éléments de
U = {0, 1}
∗
= {ε} ∪
n≥1
{0, 1}
n .
Comme plus haut, ε désigne le mot vide. Le fils gauche du mot u est u0 et le fils
droit est u1.
3 Nous avons choisi l’alphabet à deux lettres {0, 1}, qui est usuel, mais pour retrouver des arbres au
sens de la définition 1.1, il faudrait utiliser l’alphabet {1, 2}.