🌳 1.
Arbres binaires
🔷 Définition
Un arbre binaire est une structure de données où chaque nœud a au
plus deux sous-arbres (appelés fils gauche et fils droit).
🔹 Représentation d’un nœud
Type Noeud
E : Entier
gauche : *Noeud
droite : *Noeud
FinType
🔹 Exemple d’arbre binaire :
10
/ \
5 15
/ \
2 20
🔹 Parcours d’un arbre (très important)
▪ Parcours Infixe (gauche → racine → droite)
▪ Parcours Préfixe (racine → gauche → droite)
▪ Parcours Postfixe (gauche → droite → racine)
Ces trois types sont utilisés pour parcourir et analyser des arbres selon le
contexte (ex: expression mathématique, tri, etc.)
🌲 2. Arbres Binaires de Recherche (ABR)
🔷 Définition
Un ABR est un arbre binaire qui respecte cette propriété :
Pour chaque nœud N :
Tous les éléments du sous-arbre gauche sont < [Link]
Tous les éléments du sous-arbre droit sont > [Link]
🔹 Exemple :
10
/ \
5 15
/ \ \
2 7 20
✅ Cet arbre est un ABR, car :
5 < 10, 15 > 10,
2 < 5 < 10, 7 < 10,
20 > 15 > 10, etc.
🔹 Insertion dans un ABR
Procédure Inserer(var A : *Noeud, x : Entier)
Début
Si A = NIL alors
Allouer(A)
A→E ← x
A→gauche ← NIL
A→droit ← NIL
Sinon Si x < A→E alors
Inserer(A→gauche, x)
Sinon
Inserer(A→droit, x)
FinSi
Fin
🔹 Avantages d’un ABR
Recherche rapide : O(log n) dans le meilleur des cas.
Structure très utile pour des données triées dynamiquement.
⚠️Si les données sont insérées dans l'ordre (ex : 1, 2, 3...), l’arbre devient
déséquilibré (comme une liste) → complexité O(n).
🌳 Procédures et Fonctions Pré-définies pour
ABR
🔹 1. Création d’un nœud
Procédure CreerNoeud(var A : *Noeud, x : Entier)
Début
Allouer(A)
A→E ← x
A→gauche ← NIL
A→droit ← NIL
Fin
🔹 2. Insertion dans un ABR
Procédure Inserer(var A : *Noeud, x : Entier)
Début
Si A = NIL alors
CreerNoeud(A, x)
Sinon Si x < A→E alors
Inserer(A→gauche, x)
Sinon
Inserer(A→droit, x)
FinSi
Fin
🔹 3. Recherche d’un élément
Fonction Rechercher(A : ^Noeud, x : Entier) : Booléen
Début
Si A = NIL alors
Retourner Faux
Sinon Si A→val = x alors
Retourner Vrai
Sinon Si x < A→val alors
Retourner Rechercher(A→gauche, x)
Sinon
Retourner Rechercher(A→droit, x)
FinSi
Fin
🔹 4. Parcours Infixe (ordre croissant)
Procédure ParcoursInfixe(A : *Noeud)
Début
Si A ≠ NIL alors
ParcoursInfixe(A→gauche)
Afficher(A→E)
ParcoursInfixe(A→droit)
FinSi
Fin
🔹 5. Suppression dans un ABR
Procédure Supprimer(var A : *Noeud, x : Entier)
Var Temp : *Noeud
Début
Si A = NIL alors
Afficher("Élément non trouvé")
Sinon Si x < A→E alors
Supprimer(A→gauche, x)
Sinon Si x > A→E alors
Supprimer(A→droit, x)
Sinon // x trouvé
Si A→gauche = NIL alors
Temp ← A
A ← A→droit
Libérer(Temp)
Sinon Si A→droit = NIL alors
Temp ← A
A ← A→gauche
Libérer(Temp)
Sinon
Temp ← TrouverMin(A→droit)
A→val ← Temp→val
Supprimer(A→droit, Temp→val)
FinSi
FinSi
Fin
🔹 6. Trouver le minimum
Fonction TrouverMin(A : *Noeud) : *Noeud
Début
Tant que A→gauche ≠ NIL faire
A ← A→gauche
FinTantQue
TrouverMin ← A
Fin
🔹 7. Hauteur de l’arbre
Fonction Hauteur(A : *Noeud) : Entier
Début
Si A = NIL alors
Retourner 0
Sinon
Retourner 1 + Max(Hauteur(A→gauche), Hauteur(A→droit))
FinSi
Fin
Utile pour mesurer l'équilibre de l'arbre.
🔹 8. Nombre total de nœuds(taille de l’arbre)
Fonction CompterNoeuds(A : *Noeud) : Entier
Début
Si A = NIL alors
Retourner 0
Sinon
Retourner 1 + CompterNoeuds(A→gauche) +
compterNoeuds(A→droit)
FinSi
Fin