CHAPITRE 3

LES ARBRES

3.1 Introduction
L’arbre est une structure de données fondamentale en informatique. On rencontre
cette structure dans tout les domaines de l’informatique :
— Algorithmique (exp : méthodes de tri) ;
— Compilation (arbres syntaxiques) ;
— Intelligence artificielle (arbres de décisions, de résolution, ) ...

Exemple 1 (Représentation d’une expression arithmétique)

✏
A (B + C ⇤ (D E)) ⇤ F

✏(((hhh
✏
✏(((hhh
✏
A ⇤

✏(((hhh
✏
+ F

✏(((hhh
✏
B ⇤

✏(((hhh
✏
C
D E

33
3.2 Terminologie de base

Exemple 2 (Représentation d’une table de matière d’un livre)

Livre
Chap I
S1.1
S1.2
Chap II
S2.1
SS2.1.1
SS2.1.2
S2.2
S2.3
ChapIII

LIVRE
((hhhh
(((
( h
h
Chap I Chap II Chap III
HH h
XhXX
hX
H hhhh
SS1.1 SS1.2 SS2.1 SS2.2 SS2.3
HH
SS2.1.1 SS2.1.2

Exemple 3 (représentation d’un arbre généalogique,. . .)

3.2 Terminologie de base

Défintion (Arbre, Sous-arbre, Nœud)

Un arbre est une collection d’éléments homogènes organisée en niveaux. Chaque élé-
ment, appelé « nœud », d’un niveau donné peut être relié à plusieurs éléments du niveau
inferieur, par des branches ne formant pas de boucles (sinon on affaire à un graphe).
Un arbre peut, aussi être défini, comme étant un graphe orienté acyclique.
Comme on peut définir simplement un arbre de façon récursive de la façon suivante :
un arbre d’éléments de type T est
— soit vide,

34
 Chapitre 3. LES ARBRES

— soit formé d’une donnée de type T appelée « racine »et d’un ensemble fini de taille
variable d’arbre de type T appelés sous-arbres.
Un nœud comme tout élément d’une liste, peut être de n’importe quel type et les nœuds
sont liés par une relation dite de « parenté ». On appelle feuille la racine d’un arbre n’ayant
pas lui même de sous-arbres. La racine et les feuilles sont des nœuds particuliers. Un sous-
arbre d’un arbre et appelé son « fils », et inversement celui-ci sera appelé « père »de celui
là.
Deux sous-arbres du même arbre sont des « frères ».

Exemple 4 ()
✏
a
✏⇢
⇢✏Z
⇢Z ✏ Arbre A
Z
b c d
✏ @
@✏
e f

a : racine de A
b, e, f, d :feuilles de A ;
c est le père de e et de f
d fils de a.

Définition (Chemin)

Soit n1 , . . . , nk une suite de nœuds d’un arbre telle que ni est le parent de ni+1 pour
1  i < k.
Cette suite est appelée « chemin entre le nœud n1 et le nœud nk . La longueur d’un
chemin est égale au nombre d’arcs (le nombre de nœuds qu’il contient -1).

Exemple 5 ()
Dans l’arbre A de l’exemple 3.2 (voir page 35), le chemin a c f est de longueur 2.

Définition (Descendant, Ascendant)

S’il existe un chemin entre 2 nœuds x et y, on dit que x est un « ascendant »ou un
« ancêtre »de y et réciproquement que y est un « descendant »de x.

35
3.2 Terminologie de base

Exemple 6 ()
Dans l’arbre A,de l’exemple 3.2 (voir page 35), les ascendants de c sont lui même et
a et ses descendants sont lui même, e et f .

Remarque

Tout nœud est à la fois l’un de ses propres descenants et l’un de ses propres ascendants.

Définition (Profondeur)

La « profondeur »d’un nœud est la longueur du chemin entre la racine et ce nœud.

Exemple 7 ()
La profondeur du nœud d de l’arbre A, de l’exemple 3.2 (voir page 35), est égale à 1.

3.2.1 Ordre sur les nœuds d’un arbre

Les fils d’un nœud sont habituellement ordonnés de gauche vers la droite.

Exemple 8 ()

✏ ✏
Les deux arbres ordonnés suivants sont différents :
a a
✏ @
@✏ ✏ @
@✏
b c c b

Si l’on désir ignorer explicitement l’ordre des fils, on dit que l’on travaille sur un arbre
non ordonné.
L’ordre « gauche-droite »permettant la comparaison d’enfants d’un même père peut
être étendu pour comparer 2 nœuds qui ne sont pas liés par la relation ascendant-
descendant. Si a et b sont 2 frères et si a est à gauche de b, alors tout descendant
de a est à gauche de tout descendant de b.

Exemple 9 ()
D’après la figure 3.1 (voir la page 37), le nœud 8 est :
— à gauche des nœuds 9,6,10,4,7 ;

36
 Chapitre 3. LES ARBRES

Figure 3.1 – Arbre ordonné

— à droite du nœud 2 ;
— Il n’est ni à droite ni à gauche de ses ascendants 1, 3, 5.

Une règle simple pour trouver tous le nœuds situés à droite ou à gauche d’un nœud
n est de tracer le chemin reliant la racine à ce dernier. Toute les branches de l’arbre
partant sur la gauche de ce chemin aboutissent aux nœuds situés à gauche de n. Tout
les nœuds issus de branches sur la droite du chemin sont droite de n.

3.2.2 Parcours d’arbres

Il existe plusieurs manières de parcourir les nœuds d’un arbre. Les trois parcours les
plus imporants sont les parcours préfixé (ou préordre), postfixé (ou postordre) et infixé
(ou ordre). Un parcours d’un arbre est tout algorithme permettant d’accéder une et une
seule fois à tout les nœuds de l’arbre. Soit A un arbre de racine n et A1 , . . ., Ak k
sous-arbres de A (voir la figure 3.2 de la page 37 ).

Figure 3.2 – Arbre k-aire

1. Pour effectuer le parcours préfixé des nœuds de A, on commence par la racine n

puis on parcourt en préfixé les nœuds de A1 , puis ceux de A2 . . .ainsi de suite
jusqu’à les nœuds de Ak .

37
3.2 Terminologie de base

Figure 3.3 – L’arbre T

Exemple 10 (Parcours préfixé)

Parcours préfixé de T de la figure 3.6 : 2, 5, 1, 7, 4, 8, 10, 12.

2. Pour effectuer le parcours postfixé des nœuds de A, on effectue le parcours postfixé

des nœuds de A1 , puis ceux de A2 , . . ., Ak et l’on termine par la racine n.

Exemple 11 (Parcours postfixé)

Reprenons l’arbre de la figure 3.6 (voir page 41). Le parcours postfixé de T
donne : 7, 1, 4, 5, 12, 10, 8, 2.

3. Pour effectuer le parcours infixé des nœuds de A, on commence par le parcours

infixé des nœuds de A1 , puis on passe par la racine n, puis on effectue le parours
infixé des nœuds de A2 , . . ., Ak .

Exemple 12 (Parcours Infixé)

Reprenons l’arbre de la figure 3.6 (voir page 41). Le parcours infixé de T
donne : 1, 7, 5, 4, 2, 8, 12, 10.

Les principes des procédures récursives PREFIXE (resp. INFIXE) permettant le parcours
préfixé (resp. infixé) des nœuds d’un arbre sont les suivants :

Procédure PREFIXE (n : nœud)

début
lister(n)
pour chaque fils f de n, s’il y en a, depuis le plus à gauche
jusqu’au le plus à droite faire

38
 Chapitre 3. LES ARBRES

PREFIXE(f )
finpour
fin

Procédure INFIXE (n : nœud)

début
si n est une feuille
alors lister(n)
sinon INFIXE(le fils le plus à gauche de n)
lister (n)
pour chaque fils f de n, à l’exception du plus à gauche,
depuis la gauche jusqu’au la droite faire
INFIXE(f )
finpour
finsi
fin

La procédure effectuant le parcours postfixé peut être facilement déduite à partir de

la procédure PREFIXE().

Application 1 ()
Appliquer les procédures PREFIXE(), POSTFIXE() et INFIXE() sur l’arbre de la figure
3.1 (voir la page 37) et donnez le résultat obtenu avec chacune des 3 procédures. On
suppose que les nœuds 10 et 7 sont des fils gauches.

3.3 Les arbres binaires

Définition (Arbre Binaire)

Un arbre binaire 1 est un arbre dans lequel chaque nœud possède 0, 1 ou 2 fils (fils
gauche et fils droite).
1. noté dans la suite également « AB »

39
3.4 Représentation des AB par des pointeurs

Un AB peut être vide.

Chaque nœud stocke une donnée appelée valeur du nœud.
La définition récursive d’un AB se réduit à :
Un AB est :
— soit vide ;
— soit formé d’une racine et deux sous-arbres : le sous-arbre gauche et le sous-arbre
droit qui sont eux-même des AB.

Définition (Arbre Binaire Complet)

Un sous-arbre est dit complet si tout nœud interne possède exactement 2 fils (voir
figure 3.5).

Figure 3.4 – Arbre binaire complet

Définition (Niveau d’un nœud)

Le niveau d’un nœud n d’un AB peut être défini comme suit :

— 1 si n est la racine ;
— x si le niveau du père de n est x-1.

Définition (Hauteur d’un arbre)

La hauteur d’un AB est le max des niveaux des nœuds.

3.4 Représentation des AB par des pointeurs

On utilise une représentation où chaque nœud de l’arbre contient l’information propre
au nœud et deux pointeurs sur les sous-arbres gauche et droite. On définit alors le type
NŒUD comme suit :

Type NŒUD = enregistrement

40
 Chapitre 3. LES ARBRES

Figure 3.5 – Niveaux des nœuds dans un arbre

val : T ypeElement
fg, fd : ˆNŒUD
finenregistrement

Figure 3.6 – Représentation d’un arbre par des pointeurs

On peut définir le type ARBRE comme un poiteur sur un nœud particulier d’un
arbre, à savoir, sa racine.
Type ARBRE = ˆNŒUD

41
3.4 Représentation des AB par des pointeurs

Application 2 ()
Le but de cette application est d’arriver à afficher les valeurs d’un arbre binaire
suivant les deux approches en largeur et en profondeur.

A. Parcours en profondeur

Il va s’agir d’afficher tous les chemins issus de la racine et aboutissant sur des
feuilles d’un arbre binaire d’entiers de type AB dans l’ordre depuis le chemin le plus
à gauche jusqu’au chemin le plus à droite.
Le parcour en profondeur de l’arbre à la figure 3.7 (voir page 43) affichera

Les chemins issus de la racine sont :

1 - 2 - 4;
1 - 2 - 5 - 6;
1 - 3.

L’idée est de passer par une pile pour y enregistrer les valeurs stockées dans les
nœuds. À chaque fois on passe par un neud, on empile sa valeur dans cette pile puis
on la dépile une fois on a terminé avec ce nœud. Une fois on se trouve sur une feuille,
il faut afficher le chemin.
1. Définir le type PILE dont il s’agit.
2. Écrire une procédure qui affiche les valeurs dans une pile de type PILE depuis
la base jusqu’au sommet.
3. Écrire la procédure qui affiche les chemins issus de la racine d’un arbre de type
AB de la gauche vers la droite.

B. Parcours en largeur

Il va s’agir d’afficher les valeurs stockées dans les nœuds niveau par niveau.
Pour chaque niveau, on affiche les valeurs de la gauche vers la droite. Le parcour en
largeur de l’arbre à la figure3.7 (voir page 43) affichera les valeurs dans l’ordre :

1, 2, 3, 4, 5, 6.

Pour ce faire, nous passons par une file pour y mémoriser les nœuds qu’on a
considéré mais qu’on n’a pas pas considéré leurs fils encore.

42
 Chapitre 3. LES ARBRES

4. Définir le type FILE dont’il s’agit.

5. Écrire la procédure qui permet d’afficher les valeurs stockées dans un arbre de
type AB en suivant le parcous en largeur.

Figure 3.7 – Arbre à parcourir en largeur et en profondeur

3.5 Exercices
Exercice 1 (- pts)
Lister les nœuds de l’arbre ci-dessous suivant les parcours préfixé, postfixé et infixé.
✏
✏ ✏
A

✏ ✏ ✏ ✏ ✏
B C

✏ ✏ ✏ ✏
D E F G H

✏ ✏
I J K L
M N

Exercice 2 (- pts)
Soit A un arbre binaire représenté par pointeurs (utiliser les types NŒUD et ARBRE
définis en cours).
a. Écrire des programmes récursifs permettant les parcours préfixé, postfixé et infixé.
b. Écrire la version itérative du parcours préfixé.

Exercice 3 (- pts)

43
3.5 Exercices

1. Écrire une fonction qui teste si deux arbres binaires sont égaux ou non.
2. Écrire une procédure qui transforme un arbre binaire en son symétrique par rap-
port à la racine.
3. Écrire une procédure qui construit une copie d’un arbre binaire.
4. Soit un arbre binaire d’entiers. Écrire une fonction qui calcule la somme des valeurs
dans un tel arbre.

Exercice 4 (- pts)
Soient A un arbre quelconque non vide et n un nœud de A. On définie le degré de n dans
A comme étant le nombre de ses fils. Notons par N n2 le nombre de nœuds de degré 2 et
par N f le nombre de feuilles dans A. En supposant que A est un arbre binaire, on vous
demande de :
1. Déterminer le nombre maximum de nœuds de l’arbre A s’il est de hauteur h.
2. Montrer, en vous inspirant de la question précédente, que N f = N n2 + 1.
3. Écrire une fonction pour calculer la hauteur h de l’arbre A.

44