6
1 Botanique
Fig. 1.1 Arbre planaire
τ = {ε, 1, 2, 3, 31, 32}. Pour
cet arbre M ε = 3, M 3 = 2 et
M 1 = M 2 = M 31 = M 32 = 0.
Le numérotage canonique est
représenté pour chaque nœud
de τ
Fig. 1.2 Un arbre préfixe.
Les enfants de la racine sont
numérotés 1 et 3 ; il n’y a pas
d’enfant numéroté 2
Définition 1.3 Dans un arbre τ , la racine ou ancêtre est le nœud correspondant
à ε. L’arité d’un nœud est le nombre de ses enfants. Le niveau ou profondeur
d’un nœud est la longueur du mot qui lui est associé. C’est aussi la distance à la
racine. La hauteur d’un arbre fini est le maximum des profondeurs de ses nœuds
(l’arbre réduit à sa racine est de hauteur 0).
La taille d’un arbre est (sauf indication explicite du contraire) le nombre de ses
nœuds.
Les nœuds internes d’un arbre sont ceux qui ont au moins un enfant ; les
feuilles, ou nœuds externes sont les nœuds qui n’ont pas d’enfant. Les nœuds
internes terminaux sont les nœuds internes n’ayant que des feuilles pour enfants.
L’ensemble des feuilles d’un arbre τ est noté ∂τ . L’ensemble des nœuds internes de
τ est τ \ ∂τ .
Les descendants d’un nœud u sont les éléments de l’arbre ayant u pour préfixe.
L’ensemble des descendants du nœud u, renumérotés en supprimant le préfixe u, est
le sous-arbre issu de u, noté généralement τ u .
Ainsi l’ensemble des nœuds de l’arbre est la réunion disjointe des nœuds internes et
des feuilles : τ = (τ \ ∂τ ) ∪ ∂τ .
Remarque 1.4 Dans ce livre, nous utilisons les conventions suivantes pour un arbre
non marqué : ◦ sert à désigner un nœud lorsque nous ne précisons pas s’il s’agit
d’un nœud interne ou d’une feuille ; dans le cas contraire • désigne un nœud interne
et une feuille.
Il peut arriver que nous soyons conduits à restreindre les arités possibles pour un
nœud.
Définition 1.5 Soit E un sous-ensemble de N ; nous notons P E l’ensemble des
arbres planaires dont les nœuds sont à arité dans E.
Lorsque E = N, on retrouve évidemment l’ensemble P ; si E ne contient pas 0, les
arbres sont infinis.
1 Botanique
Fig. 1.1 Arbre planaire
τ = {ε, 1, 2, 3, 31, 32}. Pour
cet arbre M ε = 3, M 3 = 2 et
M 1 = M 2 = M 31 = M 32 = 0.
Le numérotage canonique est
représenté pour chaque nœud
de τ
Fig. 1.2 Un arbre préfixe.
Les enfants de la racine sont
numérotés 1 et 3 ; il n’y a pas
d’enfant numéroté 2
Définition 1.3 Dans un arbre τ , la racine ou ancêtre est le nœud correspondant
à ε. L’arité d’un nœud est le nombre de ses enfants. Le niveau ou profondeur
d’un nœud est la longueur du mot qui lui est associé. C’est aussi la distance à la
racine. La hauteur d’un arbre fini est le maximum des profondeurs de ses nœuds
(l’arbre réduit à sa racine est de hauteur 0).
La taille d’un arbre est (sauf indication explicite du contraire) le nombre de ses
nœuds.
Les nœuds internes d’un arbre sont ceux qui ont au moins un enfant ; les
feuilles, ou nœuds externes sont les nœuds qui n’ont pas d’enfant. Les nœuds
internes terminaux sont les nœuds internes n’ayant que des feuilles pour enfants.
L’ensemble des feuilles d’un arbre τ est noté ∂τ . L’ensemble des nœuds internes de
τ est τ \ ∂τ .
Les descendants d’un nœud u sont les éléments de l’arbre ayant u pour préfixe.
L’ensemble des descendants du nœud u, renumérotés en supprimant le préfixe u, est
le sous-arbre issu de u, noté généralement τ u .
Ainsi l’ensemble des nœuds de l’arbre est la réunion disjointe des nœuds internes et
des feuilles : τ = (τ \ ∂τ ) ∪ ∂τ .
Remarque 1.4 Dans ce livre, nous utilisons les conventions suivantes pour un arbre
non marqué : ◦ sert à désigner un nœud lorsque nous ne précisons pas s’il s’agit
d’un nœud interne ou d’une feuille ; dans le cas contraire • désigne un nœud interne
et une feuille.
Il peut arriver que nous soyons conduits à restreindre les arités possibles pour un
nœud.
Définition 1.5 Soit E un sous-ensemble de N ; nous notons P E l’ensemble des
arbres planaires dont les nœuds sont à arité dans E.
Lorsque E = N, on retrouve évidemment l’ensemble P ; si E ne contient pas 0, les
arbres sont infinis.