Algorithmiques, structures

de données et complexité
Responsable : Naim TERBEH
[email protected]

1.ISI et 1.SI *** S2 A.U: 2023-2024

Chapitre 4: Les arbres
 Introduction
Qu’est ce qu’un arbre ?

Un arbre est une structure de données non linéaire sert à mémoriser des données d’une manière
hiérarchique, c’est un graphe sans cycles où chaque nœud a au plus un prédécesseur.
D’une manière plus simple, un graphe est constitué d’éléments appelés souvent des nœuds (node) ou
sommet/racine (root) tels que:
 Le premier nœud est la racine et ne possède pas de prédécesseur (père),
 Un nœud peut avoir 0, 1 ou plusieurs sous-nœuds (fils),
 Un fils n’a qu’un seul père,
 Les feuilles sont les nœuds qui sont au bout des branches et qui n’ont pas de fils,
 Les frères sont des nœuds qui ont le même père.
Chapitre 4: Les arbres
 Introduction
Qu’est ce qu’un arbre ?

Exemple:

 Le prédécesseur, s’il existe, il s’appelle père. Père(C)=A, Père(L)=H

 Le successeur, s’il existe, il s’appelle fils. Fils(A)={B, C, D}, Fils(H)={L, M}
 Le nœud qui n’a pas de prédécesseur s’appelle racine. Racine=A
 Le nœud qui n’a pas de successeur s’appelle feuille {E, F, G, L, M, J, K}
 Descendants de C = {G, H, I, L, M}, Descendants de B={E,F}
 Ascendants de L={H, C, A}, Ascendants de E={B, A}
Chapitre 4: Les arbres
 Introduction
Caractéristiques d’un arbre

 Taille d’un arbre = nombre de nœuds (Taille=13 pour notre exemple; un arbre vide a une taille 0).
 Niveau d’un nœud: niveau de la racine=0. Le niveau d’un nœud est égal au niveau de son père+1.
 La hauteur ou la profondeur d’un arbre est égale au niveau maximum de ses nœuds.
 Le degré d’un nœud est égal au nombre de ses fils.
 Le degré d’un arbre est égal au degré maximal de ses nœuds.
Chapitre 4: Les arbres
 Introduction
Utilisation des arbres

 SGBD,
 Expression arithmétiques,
 IA,
 Arbres généalogiques,
 Plan d’un rapport, découpage d’un livre.
Chapitre 4: Les arbres

Déclaration d’un arbre binaire

Type Nœud= Enregistrement (structure)

Donnée : Entier (ou autre type)
FilsG: *Noeud
FilsD: *Nœud
Fin Nœud
Arbre : *Nœud
Variable
A : Arbre
Chapitre 4: Les arbres

Opérations sur les arbres binaires

Pour manipuler les arbres binaires, on utilise les fonctions ayant les objectifs suivants:
 Créer un arbre,
 Vérifier si l’arbre est vide,
 Retourner le fils gauche ou droite d’un arbre,
 Tester si le nœud est feuilee ou non,
 …
Chapitre 4: Les arbres

Opérations sur les arbres binaires

Pour manipuler les arbres binaires, on utilise les fonctions ayant les objectifs suivants:
 Créer un arbre,
 Vérifier si l’arbre est vide,
 Retourner le fils gauche ou droite d’un arbre,
 Tester si le nœud est feuille ou non,
 … Procédure Créer_Arbre (A: Arbre)

Début
A  Null
Fin
Chapitre 4: Les arbres

Opérations sur les arbres binaires

Pour manipuler les arbres binaires, on utilise les fonctions ayant les objectifs suivants:
 Créer un arbre,
 Vérifier si l’arbre est vide,
 Retourner le fils gauche ou droite d’un arbre,
 Tester si le nœud est feuille ou non,
 … Fonction Vide_Arbre (A: Arbre): Booléen

Début
Return(A=Null)
Fin
Chapitre 4: Les arbres

Opérations sur les arbres binaires

Pour manipuler les arbres binaires, on utilise les fonctions ayant les objectifs suivants:
 Créer un arbre,
 Vérifier si l’arbre est vide,
 Retourner le fils gauche ou droite d’un arbre,
 Tester si le nœud est feuille ou non, Fonction Gauche_Arbre (A: Arbre): *Noeud
 …
Début
Si (Vide_Arbre(A)) alors
Return(Null)
Si non
Return(A*.FilsG)
Fin si
Fin
Chapitre 4: Les arbres

Opérations sur les arbres binaires

Pour manipuler les arbres binaires, on utilise les fonctions ayant les objectifs suivants:
 Créer un arbre,
 Vérifier si l’arbre est vide,
 Retourner le fils gauche ou droite d’un arbre,
 Tester si le nœud est feuille ou non, Fonction Droite_Arbre (A: Arbre): *Noeud
 …
Début
Si (Vide_Arbre(A)) alors
Return(Null)
Si non
Return(A*.FilsD)
Fin si
Fin
Chapitre 4: Les arbres

Opérations sur les arbres binaires

Pour manipuler les arbres binaires, on utilise les fonctions ayant les objectifs suivants:
 Créer un arbre,
 Vérifier si l’arbre est vide,
 Retourner le fils gauche ou droite d’un arbre, Fonction Est_Feuille (N: *Noeud): Booléen
 Tester si le nœud est feuille ou non,
Début
 … Si (Vide_Arbre(N)) alors
Return(Fals)
Si non si ((Vide_Arbre(N*.FilsG) et (Vide_Arbre(N*.FilsG)) alors
Return(True)
Si non
Return(Fals)
Fin si
Fin si
Fin
Chapitre 4: Les arbres

Opérations sur les arbres binaires

Pour manipuler les arbres binaires, on utilise les fonctions ayant les objectifs suivants:
 Créer un arbre,
 Vérifier si l’arbre est vide,
 Retourner le fils gauche ou droite d’un arbre, Fonction Est_Feuille (N: *Noeud): Booléen
 Tester si le nœud est feuille ou non,
Début
 … Si (Vide_Arbre(N)) alors
Return(Fals)
Si non si ((Vide_Arbre(N*.FilsG) et (Vide_Arbre(N*.FilsG)) alors
Return(True)
Si non
Return(Fals)
Fin si
Fin si
Fin
Chapitre 4: Les arbres

Exercice

Pour manipuler les arbres binaires, on utilise les fonctions ayant les objectifs suivants:
 Créer un arbre,
 Vérifier si l’arbre est vide,
 Retourner le fils gauche ou droite d’un arbre,
 Tester si le nœud est feuille ou non,
 Calculer la hauteur
Chapitre 4: Les arbres

Exemple d’arbre binaire

A

B C

D E F G

H I J K L M

I I P Q