3
LES ARBRES BINAIRES
3.1 Introduction
Définition 8
Un arbre est une structure de données hiérarchique constituée d’un ensemble de nœuds reliés entre eux par des
liens (arêtes).
Chaque noeud peut avoir plusieurs enfants, sauf la racine qui n’a pas de parent.
4 8 12
3 7 1 9 14 11
3 20
Les arbres permettent de :
✁ représenter des relations hiérarchiques (fichiers, décisions, expressions arithmétiques) ;
✁ organiser les données pour une recherche et une manipulation e!caces.
✂ Exemples d’utilisation:
✁ Organisation hiérarchique des dossiers d’un ordinateur ;
✁ Arbres syntaxiques dans les compilateurs ;
✁ Arbres de décision en intelligence artificielle ;
✁ Arbres de recherche dans les bases de données.
✂ Structure d’un arbre:
Un arbre est formé de :
✁ Noeuds (ou sommets) : entités contenant une valeur ou une information.
Mr ESSADDOUKI Mostafa 27
3.2 Définitions et terminologie de base
✁ Arêtes (ou branches) : liens reliant un nœud à ses enfants.
✁ Sous-arbres : arbres constitués à partir d’un nœud et de ses descendants.
✃ Exemple(s) 3.1.1:
4 8
3 7 9 14
Figure 3.1
Dans cet exemple,
✄ 6 est la racine,
✄ 4, 8 sont ses enfants,
✄ 3, 7 sont des descendants de 4.
3.2 Définitions et terminologie de base
Définition 9: Racine
C’est le premier nœud de l’arbre, celui qui n’a aucun parent. Tous les autres nœuds en dérivent directement ou
indirectement.
→ Dans la figure 3.1, 6 est la racine.
Définition 10: Noeuds internes
Les noeuds internes sont les noeuds ayant au moins un enfant. Ils servent de points de branchement vers d’autres
nœuds.
→ Dans la figure 3.1, les noeuds internes sont 6, 4, et 8.
Définition 11: Feuilles
Les feuilles sont les noeuds sans enfants, c’est-à-dire dont les sous-arbres gauche et droit sont vides.
→ Dans la figure 3.1, Les feuilles sont 3, 7, 9, et 14.
Définition 12: Chemin
Un chemin est une suite d’arêtes reliant deux noeuds. Chaque arête relie un parent à un enfant.
→ Dans la figure 3.1, le chemin de la racine 6 vers la feuille 14 est 6 → 8 → 14.
Définition 13: Profondeur d’un noeud
La profondeur d’un noeud est le nombre d’arêtes reliant ce noeud à la racine.
→ Dans la figure 3.1,
Mr ESSADDOUKI Mostafa 28
3.3 Les arbres binaires
Noeud Profondeur
6 0
4, 8 1
3, 7, 9, 14 2
Remarque
La racine a toujours une profondeur égale à 0.
Définition 14: Hauteur de l’arbre
La hauteur d’un arbre est la longueur du plus long chemin de la racine jusqu’à une feuille.
→ Dans la figure 3.1, la hauteur de l’arbre est 2.
Définition 15: Degré d’un noeud
Le degré d’un noeud est le nombre de ses enfants directs.
→ Dans la figure 3.1,
Noeud Enfants degré
6 4, 8 2
4 3, 7 2
8 9, 14 2
3, 7, 9, 14 - 0
3.3 Les arbres binaires
Définition 16
Un arbre binaire est un arbre dont chaque noeud a au plus deux sous-arbres :
✁ un sous-arbre gauche
✁ un sous-arbre droit
✂ Représentation récursive adoptée:
Dans ce cours, nous représentons un arbre binaire sous la forme d’une liste imbriquée :
arbre =[ valeur , sous - arbre gauche , sous - arbre droit ]
Chaque sous-arbre est lui-même une structure de la même forme, ou bien une liste vide [] s’il est absent.
Mr ESSADDOUKI Mostafa 29
3.3 Les arbres binaires
✃ Exemple(s) 3.3.1:
✄ Arbre vide :
A = []
✄ Arbre réduit à un seul noeud :
A = [6 , [] , []]
✄ Arbre complet :
4 8
3 7 9 14
A = [6 , [4 , [3 , [] , []] , [7 , [] , []]] , [8 , [9 , [] , []] , [14 , [] , []]]]
3.3.1 Types d’arbres binaires
Selon la manière dont les noeuds sont disposés, on distingue plusieurs formes caractéristiques d’arbres binaires.
Ces formes influencent directement :
✁ la hauteur de l’arbre,
✁ les performances de recherche ou d’insertion,
✁ et la mémoire utilisée.
a) Arbre binaire complet
Définition 17
Un arbre binaire complet est un arbre dans lequel :
✁ tous les niveaux, sauf éventuellement le dernier, sont entièrement remplis,
✁ et le dernier niveau est rempli de gauche à droite, sans trou.
Mr ESSADDOUKI Mostafa 30
3.3 Les arbres binaires
✃ Exemple(s) 3.3.2:
6 13
4 8 7 12
3 7 9 14 2 5
(a) (b)
b) Arbre binaire parfait
Définition 18
Un arbre binaire parfait est un arbre complet dans lequel tous les niveaux sont pleins, y compris le dernier.
Autrement dit, toutes les feuilles sont au même niveau.
✃ Exemple(s) 3.3.3:
4 8
3 7 9 14
c) Arbre binaire dégénéré
Définition 19
Un arbre binaire dégénéré (ou arbre filiforme) est un arbre dans lequel chaque nœud n’a qu’un seul enfant.
Il se comporte comme une liste chaînée.
Mr ESSADDOUKI Mostafa 31
3.3 Les arbres binaires
✃ Exemple(s) 3.3.4:
13
Figure 3.3
d) Arbre binaire équilibré
Définition 20
Un arbre binaire équilibré est un arbre dans lequel la hauteur des deux sous-arbres de chaque nœud di"ère d’au
plus 1.
✃ Exemple(s) 3.3.5:
6 13
4 8 7 12
3 7 9 14 2 5
(a) (b)
e) Arbre binaire plein
Définition 21
Un arbre binaire plein (ou propre) est un arbre dans lequel chaque nœud a soit 0, soit 2 enfants — jamais un
seul.
Mr ESSADDOUKI Mostafa 32
3.3 Les arbres binaires
✃ Exemple(s) 3.3.6:
6 13
4 8 7 12
3 7 9 14 3 5 2
(a) plein (b) pas plein
3.3.2 Propriétés fondamentales
Proposition 3.1
Dans tout arbre (quel que soit son type), le nombre d’arêtes ( A ) et le nombre de nœuds ( N ) sont liés par la
relation :
A = N ↑1
Démonstration Un arbre connexe sans cycle reliant N noeuds nécessite exactement N ↑ 1 liens pour connecter
tous les nœuds sans créer de cycle.
Propriétés 3.1
Si un arbre binaire contient :
✁ T noeuds internes (ayant au moins un enfant)
✁ L feuilles (noeuds sans enfants)
alors :
N = T +L
et le nombre d’arêtes est :
A = N ↑ 1 = (T + L) ↑ 1
Proposition 3.2
Le nombre maximum de noeuds dans un arbre binaire de hauteur h est :
N = 2h+1 ↑ 1
Mr ESSADDOUKI Mostafa 33
3.3 Les arbres binaires
Démonstration À chaque niveau i, le nombre maximum de nœuds possibles dans un arbre binaire complet est :
2i
Ainsi, le nombre total de nœuds jusqu’au niveau ( h ) est :
N = 1 + 2 + 4 + 8 + · · · + 2h
C’est une somme géométrique de raison 2.
2h + 1 ↑ 1
h
!
N= 2i = = 2h + 1 ↑ 1
2↑1
i=0
Proposition 3.3
Le nombre maximum de noeuds au niveau l d’un arbre binaire est :
N = 2l
où le niveau de la racine est l = 0.
Démonstration Par récurrence sur l
☎ Initialisation ::
Pour l = 0, le niveau 0 contient uniquement la racine.
N0 = 1 = 20
La propriété est vraie pour l = 0.
☎ Hypothèse de récurrence:
On suppose que, pour un certain l = k, le niveau k contient au plus 2k noeuds.
☎ Étape de récurrence:
Chaque noeud du niveau ( k ) peut avoir **au plus deux enfants** (gauche et droite).
Donc, au niveau ( k + 1 ), le nombre maximum de nœuds est :
Nk + 1 ↓ 2 ↔ Nk
D’après l’hypothèse de récurrence :
N k ↓ 2k
alors
Nk+1 ↓ 2 ↔ 2k = 2k +1
La propriété est vraie pour l = k + 1.
Par récurrence, elle est donc vraie pour tout l ↗ 0 :
N l = 2l
Mr ESSADDOUKI Mostafa 34
3.3 Les arbres binaires
Proposition 3.4
Dans un arbre binaire complet, le nombre de feuilles est toujours :
L = T +1
avec,
✁ L = nombre de feuilles
✁ T = nombre de noeuds internes
Démonstration D’après la proposition 1.1, A = N ↑ 1.
Or, dans un arbre binaire complet : chaque nœud interne a 2 enfants, donc 2 arêtes sortantes ; les feuilles n’ont
aucun enfant, donc 0 arête sortante.
Ainsi, le nombre total d’arêtes est :
arêtes = 2T
Mais d’après la propriété générale :
arêtes = (T + L) ↑ 1
puisque le nombre total de nœuds est
T +L
.
En égalant les deux :
2T = (T + L) ↑ 1
On simplifie :
2T = T + L ↑ 1
↘ T = L↑1
Proposition 3.5
La hauteur minimale possible (ou le nombre minimum de niveaux) d’un arbre binaire contenant ( N ) noeuds
est :
H = ≃log2 (N + 1) ↑ 1⇐
Mr ESSADDOUKI Mostafa 35
3.3 Les arbres binaires
Démonstration
☎ Borne supérieure du nombre de nœuds à hauteur fixée.:
Un arbre binaire de hauteur (h) contient au plus
Nmax (h) = 1 + 2 + 4 + · · · + 2h = 2h+1 ↑ 1
noeuds (arbre parfait).
☎ Condition nécessaire pour loger (N) nœuds à hauteur (h).:
Il faut
N ↓ 2h+1 ↑ 1 ⇒↘ N + 1 ↓ 2h + 1 ⇒↘ log2 (N + 1) ↓ h + 1.
☎ Hauteur minimale.:
Toute hauteur admissible doit vérifier h ↗ log2 (N + 1) ↑ 1.
La plus petite hauteur entière qui satisfait cela est donc
Hmin = ≃log2 (N + 1) ↑ 1⇐ = ≃log2 (N + 1)⇐ ↑ 1.
D’où aussi Lmin = Hmin + 1 = ≃log2 (N + 1)⇐.
Proposition 3.6
Le nombre minimal de niveaux dans un arbre binaire comportant L feuilles est :
Nniveaux,min = ≃log2 L⇐ + 1
et la hauteur minimale correspondante est :
Hmin = ≃log2 L⇐
Démonstration Dans un arbre binaire complet, chaque nœud interne a exactement deux enfants.
Ainsi, au dernier niveau, on peut avoir au maximum 2h feuilles, si la hauteur est h.
Donc, pour contenir L feuilles, il faut que :
2h ↗ L
On obtient alors :
h ↗ log2 L
Comme la hauteur est un entier :
Hmin = ≃log2 L⇐
Et puisque le **nombre de niveaux = hauteur + 1 :
Nniveaux,min = Hmin + 1 = ≃log2 L⇐ + 1
Théorème 3.1: Poignée de main
Dans tout graphe simple non orienté — en particulier dans un arbre — la somme des degrés de tous les nœuds
est le double du nombre d’arêtes :
n
!
deg (i) = 2|A|
i→1
Mr ESSADDOUKI Mostafa 36
3.4 Parcours d’un arbre binaire
où n est le nombre de nœuds et |A| le nombre d’arêtes.
Démonstration Considérons une arête u, v.
✁ Elle contribue +1 au degré de u
✁ et +1 au degré de v.
Donc chaque arête est comptée exactement deux fois dans la somme
n
!
deg(i)
i=1
.
En additionnant sur toutes les arêtes, on obtient :
n
!
deg(i) = 2, |A|.
i=1
3.4 Parcours d’un arbre binaire
Le parcours d’un arbre binaire consiste à visiter tous ses nœuds selon un certain ordre.
Deux grandes familles existent :
✁ Parcours en profondeur
✁ Parcours en largeur
3.4.1 Parcours en profondeur
Ces parcours explorent l’arbre en allant le plus loin possible dans chaque branche avant de remonter. Ils sont naturellement
implémentés de manière récursive.
À partir d’un nœud, on visite récursivement son sous-arbre gauche, puis son sous-arbre droit.
Trois variantes principales existent selon le moment où la racine est visitée :
✁ Préfixe : Racine → Gauche → Droite
✁ Infixe : Gauche → Racine → Droite
✁ Postfixe : Gauche → Droite → Racine
4 8
3 7 9 14
Figure 3.6
Mr ESSADDOUKI Mostafa 37
3.4 Parcours d’un arbre binaire
✂ Parcours Préfixe:
1. Traiter la racine (N).
2. Parcourir récursivement le sous-arbre gauche (G).
3. Parcourir récursivement le sous-arbre droit (D).
def prefixe ( arbre ) :
if arbre != []:
print ( arbre [0])
prefixe ( arbre [1])
prefixe ( arbre [2])
✃ Exemple(s) 3.4.1:
→ pour l’arbre de la figure 3.6 : 6, 4, 3, 7, 8, 9, 14
✂ Parcours Infixe:
1. Parcourir récursivement le sous-arbre gauche (G).
2. Traiter la racine (N).
3. Parcourir récursivement le sous-arbre droit (D).
def infixe ( arbre ) :
if arbre != []:
infixe ( arbre [1])
print ( arbre [0])
infixe ( arbre [2])
✃ Exemple(s) 3.4.2:
→ pour l’arbre de la figure 3.6 : 3, 4, 7, 6, 9, 8, 14
✂ Parcours Postfixe:
1. Parcourir récursivement le sous-arbre gauche (G).
2. Parcourir récursivement le sous-arbre droit (D).
3. Traiter la racine (N).
def postfixe ( arbre ) :
if arbre != []:
postfixe ( arbre [1])
postfixe ( arbre [2])
print ( arbre [0])
✃ Exemple(s) 3.4.3:
→ pour l’arbre de la figure 3.6 : 3, 7, 4, 9, 14, 8, 6
3.4.2 Parcours en largeur
Le parcours en largeur explore l’arbre niveau par niveau (ou par profondeur croissante), de la gauche vers la droite à
chaque niveau. C’est comme balayer l’arbre horizontalement.
Autrement dit, on explore d’abord tous les nœuds du niveau 0, puis tous ceux du niveau 1, puis tous ceux du niveau 2,
etc.
Mr ESSADDOUKI Mostafa 38
3.4 Parcours d’un arbre binaire
✃ Exemple(s) 3.4.4:
→ pour l’arbre de la figure 3.6 : 6, 4, 8, 3, 7, 9, 14
Le parcours en largeur est un algorithme itératif qui utilise une file pour mémoriser les noeuds à visiter. L’utilisation
d’une file garantit que les noeuds du niveau N sont traités avant ceux du niveau N + 1.
✂ Algorithme:
1. Initialiser une file vide.
2. Enfiler (ajouter) la racine de l’arbre dans la file.
3. Tant que la file n’est pas vide :
(a) Défiler (retirer) le noeud en tête de file (c’est le noeud courant).
(b) Traiter ce noeud (l’a!cher, par exemple).
(c) Si le noeud courant a un fils gauche, l’enfiler.
(d) Si le noeud courant a un fils droit, l’enfiler.
Étape Description Sortie File d’attente
Initialisation On commence par enfiler la racine. - [6]
On défile 6. Ses fils, 4 (gauche) et 8 (droit), sont
1 (Niveau 0) 6 [4,8]
enfilés.
2 (Niveau 1) On défile 4. Ses fils, 3 et 7, sont enfilés. 4 [8,3,7]
3 (Niveau 2) On défile 8. Ses fils, 9 et 14, sont enfilés. 8 [3,7,9,14]
4 (Niveau 3) On défile 3. Il n’a pas de fils. 3 [7,9,14]
5 (Niveau 4) On défile 7. Il n’a pas de fils. 7 [9,14]
6 (Niveau 5) On défile 9. Il n’a pas de fils. 9 [14]
7 (Niveau 6) On défile 14. Il n’a pas de fils. La file est vide. 14 []
Mr ESSADDOUKI Mostafa 39