1.1 Arbres non marqués
9
Fig. 1.5 Un arbre binaire et
un arbre binaire complet ; à
chaque nœud est indiqué le
mot associé
Définition 1.10 Un arbre binaire τ est soit l’arbre vide, soit un sous-ensemble de
U = {0, 1} ∗ tel que
∀u, v ∈ U, si uv ∈ τ alors u ∈ τ.
Un arbre binaire complet τ est un sous-ensemble de U = {0, 1} ∗ tel que
⎧
⎨
⎩
ε ∈ τ,
∀u, v ∈ U, si uv ∈ τ alors u ∈ τ,
∀u ∈ τ, u1 ∈ τ ⇔ u0 ∈ τ .
L’ensemble des arbres binaires est noté C ; l’ensemble des arbres binaires complets
est noté B.
Comme pour les arbres planaires, les éléments de τ sont les nœuds, la racine de τ
est ε, le nombre de lettres d’un nœud u est noté |u|, c’est le niveau ou profondeur de
u dans l’arbre et le niveau de la racine est |ε| = 0, l’arité d’un nœud est son nombre
d’enfants. Pour les arbres binaires, ce nombre peut valoir 0, 1 ou 2. Pour les arbres
binaires complets, il peut valoir 0 ou 2. Nous parlerons de feuille, de nœud simple, 4
ou de nœud double, pour un nœud d’arité 0, 1, ou 2 (figure 1.5).
B. Classes combinatoires Nous définissons ci-dessous les classes combinatoires
des arbres binaires et des arbres binaires complets. Nous utilisons les notions de
classe combinatoire neutre et de classe combinatoire atomique (cf. la section B.1).
Définition 1.11 (récursive)
Une classe combinatoire C est une classe d’arbres binaires lorsqu’il existe une
classe neutre notée E contenant un objet de taille 0, l’arbre vide, et une classe
4 Il existe en fait deux types de nœuds simples distincts dans les arbres binaires : ceux qui n’ont
que le fils gauche, et ceux qui n’ont que le fils droit ; il est parfois utile de les distinguer.