NSI (Spé) — Algorithmique
Algorithmes sur les arbres
Parcours d'arbres (préfixe, infixe, suffixe, largeur), insertion et recherche dans un ABR
Résumé synthétiqueFiche en 5 sectionsQuiz de 10 questionsGratuit, sans pub
Résumé
Un arbre se définit lui-même en plus petit : un nœud, plus un sous-arbre gauche et un sous-arbre droit… qui sont à leur tour des arbres. Voilà pourquoi presque tout algorithme sur les arbres est récursif. On distingue les parcours en profondeur — préfixe (racine, gauche, droit), infixe (gauche, racine, droit) et suffixe (gauche, droit, racine) — et le parcours en largeur (BFS), qui visite niveau par niveau à l'aide d'une file. Sur un arbre binaire de recherche (ABR), la recherche descend à gauche ou à droite selon la comparaison : une véritable dichotomie. L'insertion descend de même et accroche une feuille. Tout cela coûte $O(h)$, la hauteur de l'arbre — soit $O(\log n)$ s'il est équilibré, mais $O(n)$ s'il dégénère en peigne.
Un parcours en profondeur plonge dans un sous-arbre avant de passer au suivant. Selon le moment où l'on traite la racine par rapport à ses fils, on obtient trois ordres : préfixe, infixe et suffixe. Tous suivent le même schéma récursif.
Sur cet arbre, préfixe = 5, 3, 1, 4, 7 ; infixe = 1, 3, 4, 5, 7 (ordre croissant) ; suffixe = 1, 4, 3, 7, 5.
- Préfixe (préordre) : racine → gauche → droit. Pratique pour copier ou sérialiser un arbre.
- Infixe (inordre) : gauche → racine → droit. Sur un ABR, donne les valeurs en ordre croissant.
- Suffixe (postordre) : gauche → droit → racine. Pratique pour libérer (supprimer) l'arbre des feuilles vers la racine.
- Schéma récursif commun : cas de base (arbre vide → on ne fait rien), puis appels sur les deux sous-arbres.
- Seul l'ordre de la ligne « traiter la racine » change entre les trois parcours.
- Complexité : $O(n)$ — chaque nœud est visité exactement une fois.
Exemple
def infixe(arbre):
if arbre is None: # cas de base
return
infixe(arbre.gauche) # 1) sous-arbre gauche
print(arbre.valeur) # 2) racine
infixe(arbre.droit) # 3) sous-arbre droit
# Pour passer en préfixe : déplacer le print AVANT l'appel gauche.
if arbre is None: # cas de base
return
infixe(arbre.gauche) # 1) sous-arbre gauche
print(arbre.valeur) # 2) racine
infixe(arbre.droit) # 3) sous-arbre droit
# Pour passer en préfixe : déplacer le print AVANT l'appel gauche.
Piège à éviter
Les trois parcours ne diffèrent que par la position de la ligne qui traite la racine. Inverser par erreur l'ordre des appels gauche/droit change le résultat : sur un ABR, seul l'infixe gauche puis droit donne l'ordre croissant.
Le parcours en largeur visite l'arbre étage par étage : d'abord la racine, puis tous les nœuds de niveau 1, puis ceux de niveau 2. Contrairement aux parcours en profondeur, il n'est pas récursif : il s'appuie sur une file.
- Visite niveau par niveau : racine (niveau 0), ses fils (niveau 1), les petits-fils (niveau 2), etc.
- Outil : une file (FIFO) — on enfile la racine, puis on défile, on traite, et on enfile les fils.
- Algorithme : tant que la file n'est pas vide : noeud = defiler() ; traiter(noeud) ; enfiler le fils gauche puis le fils droit s'ils existent.
- Sur l'arbre de la fiche précédente, le BFS donne 5, 3, 7, 1, 4.
- Complexité : $O(n)$ en temps ; mémoire en $O(w)$ où $w$ est la largeur maximale (un niveau entier dans la file).
- Application : trouver le nœud le plus proche de la racine vérifiant une condition.
Exemple
from collections import deque
def bfs(racine):
file = deque([racine])
while file:
noeud = file.popleft() # on défile (FIFO)
print(noeud.valeur)
if noeud.gauche: file.append(noeud.gauche)
if noeud.droit: file.append(noeud.droit)
def bfs(racine):
file = deque([racine])
while file:
noeud = file.popleft() # on défile (FIFO)
print(noeud.valeur)
if noeud.gauche: file.append(noeud.gauche)
if noeud.droit: file.append(noeud.droit)
Piège à éviter
Remplacer la file par une pile (utiliser pop() au lieu de popleft()) transforme le BFS en parcours en profondeur : on n'explore plus par niveaux. La structure de données fait toute la différence.
Dans un ABR, tout ce qui est à gauche d'un nœud lui est inférieur, tout ce qui est à droite lui est supérieur. La recherche exploite cette règle pour éliminer la moitié de l'arbre à chaque comparaison.
- Principe : comparer v à la racine. v < racine → descendre à gauche ; v > racine → à droite ; v = racine → trouvé.
- Cas de base : arbre vide → la valeur n'y est pas (retourner False).
- Versions récursive et itérative (une boucle while qui descend) donnent le même résultat.
- Complexité : $O(h)$ (hauteur) — donc $O(\log n)$ si équilibré, $O(n)$ si dégénéré en peigne.
- Analogie : c'est une recherche dichotomique matérialisée par la forme de l'arbre.
- À chaque étape, on ne descend que d'un niveau : on ne revient jamais en arrière.
Exemple
def recherche(arbre, v):
if arbre is None:
return False # absent
if v == arbre.valeur:
return True
if v < arbre.valeur:
return recherche(arbre.gauche, v)
return recherche(arbre.droit, v)
if arbre is None:
return False # absent
if v == arbre.valeur:
return True
if v < arbre.valeur:
return recherche(arbre.gauche, v)
return recherche(arbre.droit, v)
Piège à éviter
La recherche n'est rapide que si l'ABR est équilibré. Inséré dans le désordre il l'est souvent ; mais construit à partir de données déjà triées, il devient un peigne et la recherche retombe à $O(n)$.
Insérer revient à chercher la valeur : on descend comme pour une recherche jusqu'à tomber sur une place vide (None), où l'on accroche le nouveau nœud. Le nouvel élément devient toujours une feuille.
- Descendre puis accrocher : suivre le chemin de recherche jusqu'au premier sous-arbre vide.
- Le nouvel élément est toujours inséré comme une feuille (jamais au milieu).
- L'insertion préserve la propriété d'ABR (gauche < nœud < droit).
- L'ordre d'insertion fixe la forme : 3, 1, 5, 2, 4 donne un arbre équilibré ; 1, 2, 3, 4, 5 donne un peigne.
- Complexité : $O(h)$, comme la recherche : on ne modifie qu'un chemin de la racine à la feuille.
- La version récursive renvoie le sous-arbre éventuellement modifié, que le parent réaffecte.
Exemple
def inserer(arbre, v):
if arbre is None:
return Noeud(v) # place vide trouvée : nouvelle feuille
if v < arbre.valeur:
arbre.gauche = inserer(arbre.gauche, v)
else:
arbre.droit = inserer(arbre.droit, v)
return arbre
if arbre is None:
return Noeud(v) # place vide trouvée : nouvelle feuille
if v < arbre.valeur:
arbre.gauche = inserer(arbre.gauche, v)
else:
arbre.droit = inserer(arbre.droit, v)
return arbre
Piège à éviter
Oublier de réaffecter le résultat (arbre.gauche = inserer(arbre.gauche, v)) fait que l'insertion est perdue : la fonction crée bien la feuille, mais personne ne la raccroche à l'arbre.
La plupart des mesures sur un arbre se calculent par la même recette récursive : un cas de base pour l'arbre vide ou la feuille, puis une combinaison des résultats des deux sous-arbres.
- Taille : 0 si vide, sinon 1 + taille(gauche) + taille(droit).
- Hauteur : -1 si vide, sinon 1 + max(hauteur(gauche), hauteur(droit)).
- Nombre de feuilles : 1 si pas de fils, sinon feuilles(gauche) + feuilles(droit).
- Somme des valeurs : 0 si vide, sinon valeur + somme(gauche) + somme(droit).
- Schéma unique : cas de base + décomposition en deux sous-problèmes plus petits.
- On peut aussi vérifier qu'un arbre est un ABR ou qu'il est équilibré par le même principe.
Exemple
def hauteur(arbre):
if arbre is None:
return -1 # convention : arbre vide
hg = hauteur(arbre.gauche)
hd = hauteur(arbre.droit)
return 1 + max(hg, hd)
if arbre is None:
return -1 # convention : arbre vide
hg = hauteur(arbre.gauche)
hd = hauteur(arbre.droit)
return 1 + max(hg, hd)
Piège à éviter
Oublier le cas de base (if arbre is None) provoque une descente sans fin et une RecursionError. Tout algorithme récursif sur un arbre commence par traiter l'arbre vide.
Quiz - Algorithmes sur les arbres
10 questions
S'entraîner
- Quiz : Algorithmes sur les arbres10 questions corrigées sur ce chapitre
- Bac 2026 NSI – MétropoleSujet officiel
- Bac 2025 NSI – MétropoleSujet officiel
- Bac 2024 NSI – MétropoleSujet officiel
- Annales du bac de NSITous les sujets officiels, par année
- Coefficient de NSI au bacPoids de l'épreuve dans la note finale
Thème complet
Voir tous les chapitres « Algorithmique et programmation » de la Seconde à la Terminale
Ce thème dans une autre classe
Articles utiles
Questions fréquentes
Les points clés à retenir sur Algorithmes sur les arbres, extraits du quiz de révision.
Dans quel ordre le parcours infixe visite-t-il les nœuds ?
Réponse :
Gauche, racine, droit
Le parcours infixe visite d'abord le sous-arbre gauche, puis la racine, puis le sous-arbre droit. Dans un ABR, cela donne les valeurs en ordre croissant.
Quelle structure de données utilise le parcours en largeur ?
Réponse :
Une file
Le parcours en largeur (BFS) utilise une file (FIFO) pour traiter les nœuds niveau par niveau.
Quelle est la complexité de la recherche dans un ABR équilibré de n nœuds ?
Réponse :
O(log n)
Dans un ABR équilibré, la hauteur est O(log n), et la recherche descend d'un niveau à chaque comparaison, soit O(log n) au total.
Le parcours suffixe (postordre) visite les nœuds dans l'ordre :
Réponse :
Gauche, droit, racine
Le parcours suffixe visite d'abord le sous-arbre gauche, puis le sous-arbre droit, et enfin la racine. Il est utile pour évaluer des expressions arithmétiques en notation postfixée.