6.

LES ARBRES BINAIRES

Cours Algorithmique LMSD1 2024-2025 -77- Mr Khaled GHARDALLOU

 1. Introduction
Les arbres sont des structures de données fondamentales en
informatique très utilisés dans tous les domaines parce qu’ils sont bien
adaptés à la représentation naturelle d’informations homogènes
organisées et d’une grande commodité et rapidité de manipulation.

Leur usage est multiple car ils captent l’idée de hiérarchie :

Découpage d’un
livre en chapitres,
sections,
paragraphes

Expression
arithmétique
exemple :

A – (B + C * (D –E)) *
F

Cours Algorithmique LMSD1 2024-2025 -78- Mr Khaled GHARDALLOU

Arborescence des
répertoires et des
fichiers

2. Définition et terminologies
➢ Un arbre est une structure de données (souvent dynamique) représentant
un ensemble de valeurs organisées hiérarchiquement (non linéaire).
➢ Chaque valeur est stockée dans un nœud.
➢ Les nœuds sont connectés entre eux par des arêtes qui représentent la
relation parents/fils.

➢ Racine: c’est le nœud qui n’a pas de prédécesseur (parents) et possède 0

ou plusieurs fils. La racine constitue la caractéristique d’un arbre.
➢ Feuille: c’est un nœud qui n’a pas de successeurs (fils). Une feuille est
aussi appelée nœud externe.
➢ Nœud interne: tout nœud qui admet au moins un successeur (fils).

Cours Algorithmique LMSD1 2024-2025 -79- Mr Khaled GHARDALLOU

 ➢ Sous-arbre: est une portion de l’arbre. Dans l’exemple, le nœud G avec
ses deux fils J et K constituent un sous-arbre.
➢ Une branche: c’est une suite de nœuds connectées de père en fils (de la
racine à la feuille: A-B-E; A-C; A-D-F; A-D-G-J; …
➢ Descendants d’un Nœud: sont tous les nœuds du sous-arbre de racine ce
nœud. Dans l’exemple, les descendants de D sont F, G, H, I, J, K et L.
➢ Ascendants d’un nœud: sont tous les nœuds se trouvant sur la branche
de la racine vers ce nœud. Dans l’exemple, les ascendants de J sont G, D
et A.
➢ Taille de l’arbre: est le nombre de nœuds qu’il possède.
o Taille de l’arbre de l’exemple = 12
o Taille d’un arbre vide = 0
➢ Degré d’un nœud: est le nombre de ses fils. Dans l’exemple, le degré de
B est 1, le degré de D est 4.
➢ Degré d’un arbre: est le degré maximum de ses nœuds. Degré de l’arbre
de l’exemple est 4.
➢ Le niveau d’un nœud: est la distance qui le sépare de la racine.
o Niveau de la racine = 0
o Le niveau de chaque nœud est égal au niveau de son père plus 1
o Dans l’exemple le niveau du nœud contenant G est égal à 2.

Cours Algorithmique LMSD1 2024-2025 -80- Mr Khaled GHARDALLOU

 ➢ Hauteur de l’arbre: est le nombre de niveaux (dans notre exemple
hauteur = 4).

3. Typologie
➢ Arbre m-aire: est un arbre d’ordre m et le degré maximum d’un nœud
est égal à m.
➢ Arbre binaire: est un arbre où le degré maximum d’un nœud est 2.
➢ Arbre binaire de recherche: c’est un arbre binaire où la clé de chaque
nœud est supérieure à celle de ses descendants gauches et inférieure à celle
des ses descendants droite.

4. Arbres binaires et Fonctions de base

a) Définition
➢ Un arbre binaire est un arbre où chaque nœud est connecté à deux sous-
arbres (un sous-arbre gauche et un sous arbre droit)
➢ C’est un arbre de degré 2, c’est-à-dire que chaque nœud a au plus deux
fils.
➢ Le premier fils d’un nœud n est appelé Fils gauche (FG) et le deuxième
fils est appelé Fils droit (FD).

Cours Algorithmique LMSD1 2024-2025 -81- Mr Khaled GHARDALLOU

 ➢ Un arbre binaire est dit strictement binaire si chaque nœud interne a
exactement 2 fils différents de NULL.

➢ Un arbre binaire complet est un arbre strictement binaire où toutes les

feuilles sont au même niveau.

b) Déclaration
L’arbre est implémenté souvent de manière dynamique comme un
ensemble de nœuds chaînés entre eux. La structure d’un nœud de l’arbre
est la suivante :

t désigne un type quelconque

Type :
Nœud = enregistrement
val : t //valeur à stocker
FG : ^Nœud // Fils Gauche
FD : ^Nœud // Fils Droite
Cours Algorithmique LMSD1 2024-2025 -82- Mr Khaled GHARDALLOU
 Fin enregistrement

Arbre = ^Nœud
Var :
A : Arbre

c) Création d’un arbre vide

Cette primitive retourne un arbre vide. Il suffit de déclarer un pointeur
sur un arbre binaire et de l’initialiser à Null.

Fonction Créer_arbre_vide () : Arbre

Var :
A : Arbre
Début
A←Null
Retourner A
Fin

d) Création d’une feuille

Cette primitive permet de créer un nœud externe contenant une
valeur et retourne sa position en mémoire.

Fonction Créer_Feuille (e : t ) : Arbre

Var :
Feuille: Arbre
Début
Allouer (Feuille)
Feuille^.Val ← e
Feuille^.FG ← Null
Feuille^.FD ← Null
Retourner Feuille
Fin

Cours Algorithmique LMSD1 2024-2025 -83- Mr Khaled GHARDALLOU

 e) Création d’un arbre
Cette primitive permet de créer un arbre à partir d’un sous-arbre droit
et d’un sous-arbre gauche existants et d’un élément qui représente la
valeur de la racine.

Fonction Créer_arbre (e : t, SAG: arbre, SAD: Arbre ) : Arbre

Var :
père: Arbre
Début
Allouer (père)
père^.Val ← e
père^.FG ← SAG
père^.FD ← SAD
Retourner père
Fin

f) Tester si l’arbre est vide

Fonction est_arbre_vide (A: arbre) : booleen
Début
Retourner (A =Null)
Fin
g) Tester si un nœud est une feuille
Fonction est_Feuille (A: Arbre) : booleen
Début
Si (A = NULL) alors
Ecrire (« l’arbre est vide »)
Retourner Null
Sinon
Retourner (est_arbre_vide (A^.FG) et est_arbre_vide (A^.FD))
FinSi

Cours Algorithmique LMSD1 2024-2025 -84- Mr Khaled GHARDALLOU

 Fin

h) Racine de l’arbre
Fonction Racine (A: Arbre) : t
Début
Si (A = NULL) alors
Ecrire (« l’arbre est vide »)
Retourner Faux
Sinon
Retourner (A^.Val)
FinSi
Fin
i) Suppression d’un arbre
Cette primitive permet de détruire la totalité de l’arbre ou du sous-
arbre dont la position en mémoire est fournies en paramètre

Procédure DetruireArbre (A: Arbre)

Début
Si ( A <> NULL) alors
DetruireArbre (A^.FG)
DetruireArbre (A^.FD)
Liberer (A)
FinSi
Fin

5. Arbres binaires et Applications

a) Taille d’un arbre
Le calcul de la taille d’un arbre revient à calculer le nombre de nœuds
de cet arbre.
Fonction Taille (A: Arbre) : entier
Cours Algorithmique LMSD1 2024-2025 -85- Mr Khaled GHARDALLOU
 Début
Si (A = NULL) alors
Retourner 0
Sinon
Retourner ( 1 + Taille (A^.FG) + Taille (A^.FD))
FinSi
Fin

b) Nombre de feuilles d’un arbre

Le calcul de la taille d’un arbre revient à calculer le nombre de nœuds
de cet arbre.
Fonction Nombre_Feuille (A: Arbre) : entier
Début
Si (A = NULL) alors
Retourner 0
Sinon
Si (A^.FG = NULL) et (A^.FD = NULL) alors
Retourner 1
Sinon
Retourner ( Nombre_Feuille (A^.FG) +
Nombre_Feuille (A^.FD))
FinSi
FinSi
Fin
c) Recherche d’un élément dans un arbre
Fonction Existe (A: Arbre, x :t) : boolean
Début
Si (A = NULL) alors
Retourner Faux
Sinon
Si (A^.val = x) alors
Retourner Vrai
Cours Algorithmique LMSD1 2024-2025 -86- Mr Khaled GHARDALLOU
 Sinon
Retourner ( Existe (A^.FG, x) ou Existe (A^.FD, x))
FinSi
FinSi
Fin

Fonction Recherche (A: Arbre, x :t) : Arbre

//retourner le sous arbre contenant x
Var :
SousArbre : Arbre
Début
Si (A = NULL) alors
Retourner NULL
Sinon
Si (A^.val = x) alors
Retourner A
Sinon
SousArbre ← Recherche(A^.FG, x)
Si (SousArbre = NULL) alors
Retourner Recherche(A^.FD, x)
Sinon
Retourner SousArbre
FinSi
FinSi
FinSi
Fin

6. Parcours d’un arbre binaire

➢ Le parcours d’un arbre consiste à passer par tous ses nœuds.
➢ Les parcours permettent d’effectuer tout un ensemble de
traitement sur les arbres.
➢ On distingue deux types de parcours :
o Des parcours en largeur explorent l’arbre niveau par niveau.

Cours Algorithmique LMSD1 2024-2025 -87- Mr Khaled GHARDALLOU

 o Des parcours en profondeur explorent l’arbre branche par
branche où on descend le plus profondément possible
dans l’arbre puis une fois qu’une feuille a été atteinte, on
remonte pour explorer les autres branches en commençant
par la branche ‘’la plus basse’’ parmi celles non encore
parcourues. Le parcours en profondeur peut se faire en:
▪ le Préordre(Préfixe): où on affiche (R, FG, FD)
▪ L’Inordre(Infixe): où on affiche (FG, R, FD)
▪ Le Postordre(Postfixe): où on affiche (FG, FD, R)

a) Le parcours en profondeur préordre (Préfixe)

Le parcours préordre (Préfixe) consiste à visiter le nœud racine (R)
ensuite parcourir récursivement en préordre la sous arbre gauche (FG)
puis la sous arbre droit (FD) ce qui donne : (R, FG, FD)

Cours Algorithmique LMSD1 2024-2025 -88- Mr Khaled GHARDALLOU

 Parcours Préfixé :
A,B,D,H,I,E,C,F,G

Procédure Préfixe (A: Arbre)

Début
Si ( A <> NULL) alors
Ecrire (A^.val)
Préfixe (A^.FG)
Préfixe (A^.FD)
FinSi
Fin
b) Le parcours en profondeur inordre (Infixe)
Le parcours inordre consiste à parcourir récursivement en inordre la
sous arbres gauche (FG) puis visiter le nœud racine (R) ensuite parcourir
récursivement en inordre la sous arbre droit (FD) ce qui donne : (FG,R,FD).

Parcours Infixe : H,D,I,B,E,A,F,C,G

Procédure Infixe (A: Arbre)

Début
Si ( A <> NULL) alors

Cours Algorithmique LMSD1 2024-2025 -89- Mr Khaled GHARDALLOU

 Infixe (A^.FG)
Ecrire (A^.val)
Infixe (A^.FD)
FinSi
Fin
c) Le parcours en profondeur Postordre (Postfixe)
Le parcours Postordre consiste à parcourir récursivement en
Postordre la sous arbres gauche (FG) puis parcourir récursivement en
Postordre la sous arbre droit (FD) ensuite visiter le nœud racine (R) ce qui
donne : (FG,FD,R).

Parcours Postfixe:
H,I,D,E,B,F,G,C,A

Procédure Postfixe (A: Arbre)

Début
Si ( A <> NULL) alors
Postfixe (A^.FG)
Postfixe (A^.FD)
Ecrire (A^.val)
FinSi
Fin

Cours Algorithmique LMSD1 2024-2025 -90- Mr Khaled GHARDALLOU

 d) Le parcours en Largeur (par niveau)
Dans le parcours par niveau, tous les nœuds d’un même niveau sont
traités avant de descendre au niveau suivant. On explore les nœuds de
l’arbre niveau après niveau, l’exploration se fait dans l’ordre suivant : le
nœud racine, les nœuds du niveau 1, les nœuds du niveau 2, …etc.

Parcours en Largeur:
A,B,C,D,E,F,G,H,I

Pour ce type de parcours on ne peut pas appliquer la récursivité, car

l’arbre n’obéit plus à une définition récursive, mais il est considéré comme
étant formés de niveaux, chaque niveau contenant un certain nombre de
nœuds. Pour cela il faut utiliser une autre structure de données, les Files.

Fonction Parcours_Largeur (A: arbre) : liste

Var :
L: liste; //L liste sortie qui contient le parcours en largeur
F: file; //File qui contient les noueds de l’arbre
X: arbre ; //X variable sous arbre intermédiaire
Début
L← créer_Listevide ()
F← créer_filevide ()
Enfiler (F, A)
TantQue (F <> Null ) faire //F n’est pas vide
X ← Sommet(F) //ou F^.val : Récupérer le 1er élément
Défiler (F) //Enlever le 1er élement de la file
Cours Algorithmique LMSD1 2024-2025 -91- Mr Khaled GHARDALLOU
 Si (X <> Null) alors
InsertionFinListe (L , X^.val )
//Ajouter la racine de X dans la liste de sortie
Si (X^.FG <> Null) alors
Enfiler (F, X^.FG)
//Ajouter la sous arbre gauche dans la file
FinSi
Si (X^.FD <> Null) alors
Enfiler (F, X^.FD)
//Ajouter la sous arbre droite dans la file
FinSi
FinSi
FinTantQue
Retourner L
Fin
On va exécuter ce algorithme pour notre exemple :

Variables X (sous- F (File) L (Liste de sortie)

arbre)
[Arbre(A)] []
Tantque Arbre(A) [Arbre(A)] [A]
1 [Arbre(B), Arbre(C)]
Tantque Arbre(B) [Arbre(B), Arbre(C)] [A,B]
2 [Arbre(C), Arbre(D),
Arbre(E)]

Cours Algorithmique LMSD1 2024-2025 -92- Mr Khaled GHARDALLOU

Tantque Arbre(C) [Arbre(C), Arbre(D), [A,B,C]
3 Arbre(E)]
[Arbre(D), Arbre(E),
Arbre(F), Arbre(G)]
Tantque Arbre(D) [Arbre(D), Arbre(E), [A,B,C,D]
4 Arbre(F), Arbre(G)]
[Arbre(E), Arbre(F),
Arbre(G), Arbre(H),
Arbre(I)]
Tantque Arbre(E) [Arbre(E), Arbre(F), [A,B,C,D,E]
5 Arbre(G), Arbre(H),
Arbre(I)]
Tantque Arbre(F) [Arbre(F), Arbre(G), [A,B,C,D,E,F]
6 Arbre(H), Arbre(I)]
Tantque Arbre(G) [Arbre(G), Arbre(H), [A,B,C,D,E,F,G]
7 Arbre(I)]
Tantque Arbre(H) [Arbre(H), Arbre(I)] [A,B,C,D,E,F,G,H]
8
Tantque Arbre(I) [Arbre(I)] [A,B,C,D,E,F,G,H,I]
9

Cours Algorithmique LMSD1 2024-2025 -93- Mr Khaled GHARDALLOU

 7. Arbres binaires de recherche (ABR)
Un arbre binaire de recherche (ABR) est un arbre binaire ordonné
pour tout nœud n:

➢ Toutes les valeurs du sous arbre gauche de n sont inférieures ou

égales à la valeur de n
➢ Toutes les valeurs du sous arbre droit de n sont supérieures ou
égales à la valeur de n

a) Recherche d’un élément dans un ABR (version itérative)

Dans un ABR, on sait de façon précise s’il faut continuer la recherche
à gauche ou à droite pour chaque nœud exploré. Vela rend la recherche
beaucoup plus efficace que pour les arbres binaires quelconques.
Fonction Existe_ABR (A: Arbre, x :t) : boolean
Début
Si (A = NULL) alors
Retourner faux
Sinon
Si (A^.val = x) alors
Retourner vrai
Sinon
Si (A^.val < x) alors
Retourner Existe_ABR (A^.FG, x)
Sinon
Retourner Existe_ABR (A^.FD, x)
Cours Algorithmique LMSD1 2024-2025 -94- Mr Khaled GHARDALLOU
 FinSi
FinSi
FinSi
Fin

Fonction Recherche_ABR (A: Arbre, x :t) : Arbre

//retourner le sous arbre contenant x
Début
Si (A = NULL) alors
Retourner NULL
Sinon
Si (A^.val = x) alors
Retourner A
Sinon
Si (A^.val < x) alors
Retourner Recherche_ABR (A^.FG, x)
Sinon
Retourner Recherche_ABR (A^.FD, x)
FinSi
FinSi
FinSi
Fin
La complexité de la recherche dans un ABR est de O(hauteur(Arbre))

b) Insertion d’un élément dans un ABR

Pour insérer un nouvel élément dans un ABR il faut d’abord repérer sa
place dans l’arbre, il faut donc le comparer aux éléments déjà existants
dans l’ABR. Enfin l’insérer comme fils du dernier nœud visité.

Cours Algorithmique LMSD1 2024-2025 -95- Mr Khaled GHARDALLOU

Dans cet exemple on va insérer l’élément 25
dans cette ABR :
25 > Nœud 20 => comparaison FD : (59)
25 < Nœud 59 => comparaison FG : (27)
25 < Nœud 27 => comparaison FG : (Null)
Insertion FD Noued 27
Procedure Insertion_ABR (Ref A: Arbre, x :entier)
Var :
P : Arbre
Début
Si (A = NULL) alors
Allouer (A)
A^.Val ← x
A^.FG ← Null
A^.FD ← Null
Sinon
Si (A^.val < x) alors
Insertion_ABR (A^.FG, x)
Sinon
Insertion_ABR (A^.FD, x)
FinSi
FinSi
Fin

Cours Algorithmique LMSD1 2024-2025 -96- Mr Khaled GHARDALLOU