Les arbres organisent des données de façon hiérarchique : arborescence des fichiers, structure d’une page HTML, arbre généalogique. Les arbres binaires, où chaque nœud a au plus deux enfants, se prêtent naturellement aux algorithmes récursifs. Lorsqu’ils sont ordonnés, ce sont des arbres binaires de recherche, qui permettent de retrouver rapidement une valeur.
Une question sur ce cours ?
ULU, le tuteur d’ULUMINE, t’aide à partir de ce cours.
Objectifs
- Utiliser le vocabulaire des arbres : racine, nœud, feuille, sous-arbre, taille, hauteur
- Implémenter un arbre binaire en Python et calculer taille et hauteur récursivement
- Effectuer les parcours préfixe, infixe, suffixe et en largeur
- Rechercher et insérer une clé dans un arbre binaire de recherche
1. Vocabulaire des arbres binaires
Arbre binaire : Structure soit vide, soit formée d’un nœud racine portant une valeur et de deux sous-arbres binaires : le sous-arbre gauche et le sous-arbre droit.
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13- La racine de A est 8. Les feuilles (nœuds sans enfant) sont 1, 4, 7 et 13.
- La taille est le nombre de nœuds : A est de taille 9.
- La profondeur d’un nœud est le nombre de nœuds sur le chemin de la racine à ce nœud (racine comprise) : 8 est à la profondeur 1, 6 à la profondeur 3.
- La hauteur est la plus grande profondeur d’un nœud : A est de hauteur 4.
h ≤ n ≤ 2h − 1
2. Implémentation et algorithmes récursifs
class Noeud:
def __init__(self, valeur, gauche=None, droit=None):
self.valeur = valeur
self.gauche = gauche # sous-arbre gauche (None si vide)
self.droit = droit
def taille(a):
if a is None:
return 0
return 1 + taille(a.gauche) + taille(a.droit)
def hauteur(a):
if a is None:
return 0
return 1 + max(hauteur(a.gauche), hauteur(a.droit))Le schéma est toujours le même : cas de base pour l’arbre vide, puis combinaison des résultats obtenus récursivement sur les deux sous-arbres.
3. Parcours d’un arbre binaire
| Parcours | Ordre de traitement | Résultat sur A |
|---|---|---|
| Préfixe | nœud, sous-arbre gauche, sous-arbre droit | 8 3 1 6 4 7 10 14 13 |
| Infixe | sous-arbre gauche, nœud, sous-arbre droit | 1 3 4 6 7 8 10 13 14 |
| Suffixe (postfixe) | sous-arbre gauche, sous-arbre droit, nœud | 1 4 7 6 3 13 14 10 8 |
| En largeur | niveau par niveau, de gauche à droite | 8 3 10 1 6 14 4 7 13 |
def infixe(a):
if a is not None:
infixe(a.gauche)
print(a.valeur)
infixe(a.droit)
from collections import deque
def largeur(a):
f = deque([a])
while len(f) > 0:
n = f.popleft()
if n is not None:
print(n.valeur)
f.append(n.gauche)
f.append(n.droit)4. Arbres binaires de recherche (ABR)
Arbre binaire de recherche : Arbre binaire dont les nœuds portent des clés comparables et tel que, pour chaque nœud, toutes les clés du sous-arbre gauche sont inférieures à sa clé et toutes celles du sous-arbre droit lui sont supérieures. L’arbre A est un ABR.
def recherche(a, x):
if a is None:
return False
if x == a.valeur:
return True
if x < a.valeur:
return recherche(a.gauche, x)
return recherche(a.droit, x)
def inserer(a, x):
if a is None:
return Noeud(x)
if x < a.valeur:
a.gauche = inserer(a.gauche, x)
else:
a.droit = inserer(a.droit, x)
return aRechercher 7 dans A
- 7 < 8 : on descend à gauche, vers 3.
- 7 > 3 : on descend à droite, vers 6.
- 7 > 6 : on descend à droite et on trouve 7.
4 nœuds examinés : on ne suit qu’un seul chemin depuis la racine.
À retenir
- Un arbre binaire est vide ou formé d’une racine et de deux sous-arbres binaires.
- Taille = nombre de nœuds ; hauteur = plus grande profondeur (convention à vérifier).
- Préfixe, infixe, suffixe : parcours en profondeur ; largeur : avec une file.
- Dans un ABR, gauche < nœud < droite pour chaque nœud ; l’infixe donne l’ordre croissant.
- Recherche dans un ABR : coût proportionnel à la hauteur.
Et maintenant, à toi !
Vérifie que tu as compris avec les exercices, puis révise avec la fiche.