Les arbres binaires
Objectifs
Comprendre la structure hiérarchique des arbres binaires, leur terminologie, leurs applications et maîtriser leur implémentation en Python et en C.
Définition — Arbre binaire
Un arbre est un graphe acyclique. Un arbre dans lequel chaque nœud a au plus 2 enfants est appelé un arbre binaire.
Contrairement aux tableaux, listes chaînées, piles et files d'attente, qui sont des structures de données linéaires, les arbres sont des structures de données hiérarchiques.
Terminologie des arbres
Racine (Root)
Le nœud le plus haut de l'arbre. Dans l'exemple ci-dessus, le nœud A est la racine.
Parent et enfants
Les éléments qui sont directement sous un élément sont appelés ses enfants. L'élément directement au-dessus est appelé son parent.
Exemple : "D" est un enfant de "B" et "B" est le parent de "D".
Feuilles (Leaves)
Les éléments sans enfants sont appelés feuilles.
Exemple : D, E, F, G sont des feuilles.
Sous-arbre gauche / droit
Chaque nœud d'un arbre binaire peut avoir un enfant gauche (sous-arbre gauche) et un enfant droit (sous-arbre droit).
Vocabulaire
- Niveau (level) : distance depuis la racine (racine = niveau 1)
- Hauteur (height) : nombre maximum de nœuds sur un chemin racine → feuille
- Profondeur (depth) : distance d'un nœud à la racine
- Arbre complet (full binary tree) : chaque nœud a 0 ou 2 enfants
- Arbre parfait (perfect binary tree) : tous les nœuds internes ont 2 enfants et toutes les feuilles sont au même niveau
Pourquoi utiliser des arbres ?
Avantages des arbres
- Hiérarchie naturelle : Stocker des informations qui forment naturellement une hiérarchie (système de fichiers, organisation d'entreprise).
- Accès/recherche optimisés : Les arbres binaires de recherche offrent une complexité \(O(\log n)\) pour la recherche, plus rapide qu'une liste chaînée.
- Insertion/suppression efficaces : \(O(\log n)\) en moyenne, plus rapide que les tableaux.
- Aucune limite de taille : Comme les listes chaînées, les nœuds sont liés dynamiquement via des pointeurs.
Principales applications des arbres
Applications
- Données hiérarchiques : Système de fichiers, organisation d'entreprise, structure XML/JSON.
- Recherche optimisée : Arbres binaires de recherche (BST), arbres AVL, arbres rouges-noirs.
- Données triées : Manipulation efficace de listes triées.
- Algorithmes de routage : Arbres de routage, spanning tree dans les réseaux.
- Arbres de décision : Intelligence artificielle, apprentissage automatique.
- Compression de données : Arbres de Huffman.
- Expression arithmétique : Arbres d'expression pour l'évaluation et la simplification.
Représentation d'un arbre binaire
Un arbre est représenté par un pointeur vers le nœud le plus haut dans l'arbre (la racine). Si l'arbre est vide, la racine vaut NULL (ou None en Python).
Un nœud contient trois parties :
- Données : l'information stockée dans le nœud
- Pointeur vers l'enfant gauche
- Pointeur vers l'enfant droit
Représentation classique (nœuds chaînés)
class Noeud:
def __init__(self, val):
self.gauche = None
self.droit = None
self.val = val
struct Noeud {
int val;
struct Noeud *gauche;
struct Noeud *droit;
};
Représentation Python avec liste (alternative compacte)
Représentation par liste imbriquée
En Python, on peut représenter un arbre binaire avec une liste de la forme :
[racine, sous_arbre_gauche, sous_arbre_droit]
Un nœud vide est représenté par une liste vide [].
Exemple : arbre de l'illustration
Arbre sous forme de liste
arbre = ['A',
['B',
['D', [], []],
['E', [], []]],
['C',
['F', [], []],
['G', [], []]]]
Structure
A
/ \
B C
/ \ / \
D E F G
Avantages : représentation compacte, facile à créer et à manipuler pour des petits arbres.
Fonctions d'accès Python
def val(arbre):
"""Retourne la valeur de la racine"""
return arbre[0]
def gauche(arbre):
"""Retourne le sous-arbre gauche"""
return arbre[1]
def droit(arbre):
"""Retourne le sous-arbre droit"""
return arbre[2]
def est_vide(arbre):
"""Teste si l'arbre est vide"""
return arbre == []
Parcours d'un arbre binaire
Il existe trois façons principales de parcourir un arbre binaire :
Parcours préfixe (NLR - Node, Left, Right)
- Visiter la racine
- Parcourir le sous-arbre gauche
- Parcourir le sous-arbre droit
Ordre pour l'exemple : A B D E C F G
Parcours infixe (LNR - Left, Node, Right)
- Parcourir le sous-arbre gauche
- Visiter la racine
- Parcourir le sous-arbre droit
Ordre pour l'exemple : D B E A F C G
Parcours suffixe (LRN - Left, Right, Node)
- Parcourir le sous-arbre gauche
- Parcourir le sous-arbre droit
- Visiter la racine
Ordre pour l'exemple : D E B F G C A
Implémentation des parcours
class Noeud:
def __init__(self, val):
self.val = val
self.gauche = None
self.droit = None
def parcours_prefixe(racine):
"""NLR : Racine → Gauche → Droit"""
if racine:
print(racine.val, end=" ")
parcours_prefixe(racine.gauche)
parcours_prefixe(racine.droit)
def parcours_infixe(racine):
"""LNR : Gauche → Racine → Droit"""
if racine:
parcours_infixe(racine.gauche)
print(racine.val, end=" ")
parcours_infixe(racine.droit)
def parcours_suffixe(racine):
"""LRN : Gauche → Droit → Racine"""
if racine:
parcours_suffixe(racine.gauche)
parcours_suffixe(racine.droit)
print(racine.val, end=" ")
# Représentation par liste : [valeur, gauche, droit]
def parcours_prefixe_liste(arbre):
if arbre:
print(arbre[0], end=" ")
parcours_prefixe_liste(arbre[1])
parcours_prefixe_liste(arbre[2])
def parcours_infixe_liste(arbre):
if arbre:
parcours_infixe_liste(arbre[1])
print(arbre[0], end=" ")
parcours_infixe_liste(arbre[2])
def parcours_suffixe_liste(arbre):
if arbre:
parcours_suffixe_liste(arbre[1])
parcours_suffixe_liste(arbre[2])
print(arbre[0], end=" ")
#include <stdio.h>
#include <stdlib.h>
struct Noeud {
int val;
struct Noeud *gauche;
struct Noeud *droit;
};
// Parcours préfixe (NLR)
void parcours_prefixe(struct Noeud *racine) {
if (racine != NULL) {
printf("%d ", racine->val);
parcours_prefixe(racine->gauche);
parcours_prefixe(racine->droit);
}
}
// Parcours infixe (LNR)
void parcours_infixe(struct Noeud *racine) {
if (racine != NULL) {
parcours_infixe(racine->gauche);
printf("%d ", racine->val);
parcours_infixe(racine->droit);
}
}
// Parcours suffixe (LRN)
void parcours_suffixe(struct Noeud *racine) {
if (racine != NULL) {
parcours_suffixe(racine->gauche);
parcours_suffixe(racine->droit);
printf("%d ", racine->val);
}
}
Construction d'un arbre binaire
Exemple de construction
Construisons l'arbre suivant :
A
/ \
B C
/ \ / \
D E F G
# Création de l'arbre avec la classe Noeud
racine = Noeud('A')
racine.gauche = Noeud('B')
racine.droit = Noeud('C')
racine.gauche.gauche = Noeud('D')
racine.gauche.droit = Noeud('E')
racine.droit.gauche = Noeud('F')
racine.droit.droit = Noeud('G')
print("Parcours préfixe : ", end="")
parcours_prefixe(racine)
print()
print("Parcours infixe : ", end="")
parcours_infixe(racine)
print()
print("Parcours suffixe : ", end="")
parcours_suffixe(racine)
print()
# Création de l'arbre avec la représentation par liste
arbre = ['A',
['B',
['D', [], []],
['E', [], []]],
['C',
['F', [], []],
['G', [], []]]]
print("Parcours préfixe : ", end="")
parcours_prefixe_liste(arbre)
print()
print("Parcours infixe : ", end="")
parcours_infixe_liste(arbre)
print()
print("Parcours suffixe : ", end="")
parcours_suffixe_liste(arbre)
print()
#include <stdio.h>
#include <stdlib.h>
struct Noeud* creer_noeud(int val) {
struct Noeud* nouveau = (struct Noeud*)malloc(sizeof(struct Noeud));
nouveau->val = val;
nouveau->gauche = NULL;
nouveau->droit = NULL;
return nouveau;
}
int main() {
// Création de l'arbre
struct Noeud* racine = creer_noeud('A');
racine->gauche = creer_noeud('B');
racine->droit = creer_noeud('C');
racine->gauche->gauche = creer_noeud('D');
racine->gauche->droit = creer_noeud('E');
racine->droit->gauche = creer_noeud('F');
racine->droit->droit = creer_noeud('G');
printf("Parcours préfixe : ");
parcours_prefixe(racine);
printf("\n");
printf("Parcours infixe : ");
parcours_infixe(racine);
printf("\n");
printf("Parcours suffixe : ");
parcours_suffixe(racine);
printf("\n");
return 0;
}
Sortie
Parcours préfixe : A B D E C F G Parcours infixe : D B E A F C G Parcours suffixe : D E B F G C A
Comparaison des représentations
| Représentation | Avantages | Inconvénients |
|---|---|---|
| Nœuds chaînés (Python/C) |
|
|
| Liste imbriquée (Python uniquement) |
|
|
L'essentiel en bref
Points clés à retenir
- Un arbre binaire est une structure hiérarchique où chaque nœud a au plus deux enfants (gauche et droit).
- Le nœud le plus haut est la racine ; les nœuds sans enfants sont des feuilles.
- Les arbres sont utilisés pour représenter des données hiérarchiques (système de fichiers, arbres généalogiques, expressions arithmétiques).
- Les trois parcours principaux sont :
- Préfixe (NLR) : racine → gauche → droit
- Infixe (LNR) : gauche → racine → droit
- Suffixe (LRN) : gauche → droit → racine
- Deux représentations courantes : nœuds chaînés (C, Python) et liste imbriquée (Python).
Conseils pratiques
- Toujours vérifier si un nœud est
NULL/Noneavant d'accéder à ses enfants. - Privilégier la représentation par nœuds chaînés pour les applications réelles.
- Utiliser la liste imbriquée pour les tests rapides et les petits exemples.
Un peu d'histoire
Les arbres binaires ont été formalisés dans les années 1960 par Donald Knuth et d'autres pionniers de l'informatique. Ils sont au cœur de nombreux algorithmes fondamentaux et restent une structure incontournable en programmation.
Sortie
// La sortie apparaîtra ici…
Discussion (0)
Soyez le premier à laisser un commentaire !
Laisser un commentaire
Votre commentaire sera visible après modération.