Dans un arbre binaire, qu'appelle-t-on une feuille ?

Un nœud dont les deux sous-arbres sont vides

Le nœud situé tout en haut de l'arbre

Un nœud qui possède exactement un fils

N'importe quel nœud situé au dernier niveau dessiné

On construit un ABR en insérant successivement les valeurs 1, 2, 3, 4, 5, 6, 7 dans cet ordre. Quel est le coût d'une recherche dans le pire cas ?

O(n), car l'arbre obtenu est filiforme

O(log n), car un ABR est toujours équilibré

O(1), car les valeurs sont consécutives

O(n log n), comme un tri efficace

Algorithmes sur les arbres et les graphes

Terminale · NSI · Algorithmique

Algorithmique

Les arbres binaires et les arbres binaires de recherche

Un arbre est une structure de données hiérarchique : une racine, des branches, des feuilles. En Terminale, tu travailles surtout sur les arbres binaires (chaque nœud a au plus deux fils) et sur un cas particulier redoutablement efficace : l'arbre binaire de recherche (ABR). Tous les algorithmes du chapitre reposent sur la même idée : un arbre est fait d'arbres plus petits, donc on le parcourt récursivement.

L'arbre de référence du chapitre. On utilisera partout le même arbre, note-le sur un brouillon :
Racine 8. Fils gauche de 8 : 3, dont le fils gauche est 1 et le fils droit est 6 ; les fils de 6 sont 4 (gauche) et 7 (droit). Fils droit de 8 : 10, qui n'a pas de fils gauche et dont le fils droit est 14 ; le fils gauche de 14 est 13.
Sa taille est de 9 nœuds, sa hauteur vaut 3 (chemin 8 → 3 → 6 → 4) et il possède 4 feuilles : 1, 4, 7 et 13.

Les quatre parcours. Parcourir un arbre, c'est visiter chacun de ses nœuds une fois et une seule. Trois parcours sont dits en profondeur : ils descendent le plus loin possible avant de remonter, et se programment naturellement de façon récursive. Ils ne diffèrent que par le moment où l'on traite la valeur du nœud par rapport aux appels sur les deux sous-arbres. Le quatrième parcours, en largeur, visite l'arbre niveau par niveau et s'écrit avec une file.

Parcours	Ordre des opérations	Sur l'arbre de référence	Usage typique
Préfixe	Nœud, puis gauche, puis droit	8, 3, 1, 6, 4, 7, 10, 14, 13	Copier ou sauvegarder un arbre
Infixe	Gauche, puis nœud, puis droit	1, 3, 4, 6, 7, 8, 10, 13, 14	Obtenir les valeurs d'un ABR triées
Suffixe	Gauche, puis droit, puis nœud	1, 4, 7, 6, 3, 13, 14, 10, 8	Calculer une expression, libérer la mémoire
En largeur	Niveau par niveau, de gauche à droite	8, 3, 10, 1, 6, 14, 4, 7, 13	Afficher un arbre, trouver le nœud le plus proche

Écrire un parcours récursif sans se tromper

Étape 1 — Traite d'abord le cas de base : si l'arbre est vide, on ne fait rien (ou on renvoie 0, ou la liste vide selon ce qu'on calcule).
Étape 2 — Sinon, écris systématiquement les trois lignes : traiter le nœud, appeler la fonction sur le sous-arbre gauche, l'appeler sur le sous-arbre droit.
Étape 3 — Range ces trois lignes dans l'ordre du parcours demandé : nœud en 1er (préfixe), en 2e (infixe), en 3e (suffixe).
Étape 4 — Pour une fonction qui renvoie un résultat (taille, hauteur), combine les deux appels récursifs : taille = 1 + taille(gauche) + taille(droit), et hauteur = 1 + max(hauteur(gauche), hauteur(droit)).
Étape 5 — Déroule ton code à la main sur un petit arbre de 3 nœuds : c'est le meilleur moyen de repérer une inversion.

Les pièges classiques sur les arbres

La recherche dans un ABR coûte O(h) où h est la hauteur, pas O(log n) systématiquement. Si l'arbre est filiforme (par exemple construit en insérant 1, 2, 3, 4, 5 dans l'ordre), la hauteur vaut n − 1 et la recherche redevient linéaire, O(n) : aussi lente qu'une liste !
La propriété d'ABR est globale : il ne suffit pas que chaque fils gauche soit plus petit que son père. TOUT le sous-arbre gauche doit l'être.
Ne confonds pas parcours préfixe et parcours en largeur : les deux commencent par la racine, mais le préfixe plonge tout de suite dans le sous-arbre gauche alors que la largeur termine d'abord le niveau courant.
Un parcours infixe qui ne rend pas une suite croissante prouve que l'arbre n'est PAS un ABR.
Oublier le cas de base d'une fonction récursive sur un arbre provoque une erreur (accès à un arbre vide) ou une récursion infinie.

Algorithmique

Les graphes : représentations et parcours

Un graphe modélise des objets (les sommets) et des relations entre eux (les arêtes si le graphe est non orienté, les arcs s'il est orienté). Réseau social, plan de métro, routage Internet, labyrinthe : tout se modélise en graphe. Contrairement à un arbre, un graphe peut contenir des cycles — d'où la règle d'or de tous les parcours : marquer les sommets déjà visités.

Le graphe de référence. Graphe non orienté à 6 sommets A, B, C, D, E, F et 7 arêtes :
A–B, A–C, B–D, C–D, C–E, D–F, E–F.
Les voisins sont donc : A : B, C — B : A, D — C : A, D, E — D : B, C, F — E : C, F — F : D, E.
Les degrés valent 2, 2, 3, 3, 2, 2 : leur somme fait 14, soit bien deux fois le nombre d'arêtes.

Critère	Matrice d'adjacence	Liste d'adjacence
Espace mémoire	O(n²), même si le graphe est presque vide	O(S + A), proportionnel au contenu réel
Tester « i et j sont-ils voisins ? »	O(1) : une simple lecture de case	O(degré de i) : il faut parcourir la liste
Énumérer les voisins de i	O(n) : on balaie toute la ligne	O(degré de i) : optimal
Coût d'un parcours complet	O(n²)	O(S + A)
Situation où elle gagne	Graphe dense (beaucoup d'arêtes)	Graphe creux (le cas le plus fréquent)

Parcours en profondeur (DFS) et parcours en largeur (BFS). Les deux parcours suivent le même squelette — partir d'un sommet, explorer les voisins non encore visités, marquer au fur et à mesure — et ne diffèrent que par la structure de données qui mémorise les sommets en attente. Le parcours en profondeur utilise une pile (LIFO), souvent implicite via la récursivité : il plonge le plus loin possible puis revient sur ses pas. Le parcours en largeur utilise une file (FIFO) : il explore par cercles concentriques autour du sommet de départ.

Ce qu'on résout avec ces parcours — les cinq usages à connaître sont listés plus bas : accessibilité, connexité, plus court chemin, détection de cycle et composantes connexes.

Écrire un parcours en largeur qui donne le plus court chemin

Étape 1 — Crée une file contenant le sommet de départ, et un dictionnaire des sommets visités (le départ y est déjà, à la distance 0).
Étape 2 — Tant que la file n'est pas vide, défile un sommet u (on prend toujours le plus anciennement enfilé : c'est ce qui garantit le plus court chemin).
Étape 3 — Pour chaque voisin v de u non encore visité : marque v comme visité, note distance[v] = distance[u] + 1, mémorise parent[v] = u, puis enfile v.
Étape 4 — Marque le voisin au moment où tu l'enfiles, jamais au moment où tu le défiles : sinon un même sommet peut entrer plusieurs fois dans la file.
Étape 5 — Pour reconstituer le chemin jusqu'à un sommet t, remonte les parent[t], parent[parent[t]]… jusqu'au départ, puis inverse la liste obtenue.

Accessibilité : lancer un parcours depuis s et regarder quels sommets ont été marqués donne exactement les sommets accessibles depuis s.
Connexité : un graphe non orienté est connexe si un unique parcours depuis n'importe quel sommet marque les n sommets.
Plus court chemin en nombre d'arêtes : le parcours en largeur, et lui seul, le garantit dans un graphe non pondéré.
Détection de cycle : dans un graphe non orienté, si un parcours rencontre un sommet déjà marqué qui n'est pas le parent immédiat, il y a un cycle. Autre critère rapide : un graphe connexe à n sommets et strictement plus de n − 1 arêtes contient forcément un cycle.
Composantes connexes : relancer un parcours depuis chaque sommet non encore marqué ; le nombre de relances est le nombre de composantes.

Les pièges classiques sur les graphes

Oublier le marquage des sommets visités : sur un graphe contenant un cycle, le programme tourne indéfiniment. C'est l'erreur numéro 1.
Croire que le parcours en profondeur trouve le plus court chemin. Contre-exemple minimal : sommets X, Y, Z, T et arêtes X–Y, Y–Z, Z–T, X–T. En prenant les voisins par ordre alphabétique, la profondeur atteint Y par X → T → Z → Y (3 arêtes) alors que l'arête X–Y en offre un de longueur 1.
Confondre pile et file : une pile rend un parcours en profondeur, une file un parcours en largeur. Intervertir les deux change complètement l'ordre de visite.
Dans un graphe orienté, l'existence d'un chemin de u vers v n'implique pas celle d'un chemin de v vers u : la matrice d'adjacence n'y est plus symétrique.
Un arbre est un cas particulier de graphe : connexe et sans cycle, avec exactement n − 1 arêtes pour n sommets.

Exercices corrigés

Quel parcours d'un arbre binaire de recherche restitue les valeurs triées dans l'ordre croissant ?
- A.Le parcours préfixe
- B.Le parcours infixeBonne réponse
- C.Le parcours suffixe
- D.Le parcours en largeur
Réponse : B — Le parcours infixe
Dans un ABR, tout le sous-arbre gauche d'un nœud contient des valeurs plus petites et tout le sous-arbre droit des valeurs plus grandes. Le parcours infixe (gauche, puis nœud, puis droit) visite donc d'abord tout ce qui est plus petit, ensuite le nœud, ensuite tout ce qui est plus grand : la suite obtenue est croissante. Le préfixe commence par la racine, donc il ne peut pas être trié ; le suffixe finit par la racine, ce qui est tout aussi impossible pour une suite croissante contenant des valeurs plus grandes ; la largeur mélange les niveaux.
L'arbre de référence a pour racine 8, dont le fils gauche est 3 (fils 1 et 6, et 6 a pour fils 4 et 7) et le fils droit est 10 (dont le seul fils est 14, qui a pour fils gauche 13). Quelle est la taille de cet arbre ?
- A.3 nœuds
- B.4 nœuds
- C.9 nœudsBonne réponse
- D.10 nœuds
Réponse : C — 9 nœuds
La taille d'un arbre, c'est son nombre total de nœuds. Comptons-les : 8, 3, 1, 6, 4, 7, 10, 14, 13, soit 9 nœuds. Répondre 3 serait donner la hauteur, et répondre 4 le nombre de feuilles (1, 4, 7 et 13) : trois grandeurs différentes qu'il ne faut pas confondre.
Dans un arbre binaire, qu'appelle-t-on une feuille ?
- A.Le nœud situé tout en haut de l'arbre
- B.Un nœud qui possède exactement un fils
- C.Un nœud dont les deux sous-arbres sont videsBonne réponse
- D.N'importe quel nœud situé au dernier niveau dessiné
Réponse : C — Un nœud dont les deux sous-arbres sont vides
Une feuille est un nœud sans aucun fils, autrement dit un nœud dont le sous-arbre gauche et le sous-arbre droit sont tous les deux vides. Le nœud du haut, c'est la racine. Un nœud avec exactement un fils est un nœud interne, pas une feuille. Et attention à la dernière proposition : un arbre peut parfaitement avoir une feuille à un niveau intermédiaire — dans l'arbre de référence, 1 est une feuille alors que 4 et 7 sont plus bas.
Dans le graphe non orienté de référence (arêtes A–B, A–C, B–D, C–D, C–E, D–F, E–F), quel est le degré du sommet C ?
- A.2
- B.3Bonne réponse
- C.4
- D.6
Réponse : B — 3
Le degré d'un sommet est son nombre de voisins, c'est-à-dire le nombre d'arêtes qui le touchent. Repérons les arêtes contenant C : A–C, C–D et C–E. Il y en a trois, donc le degré de C vaut 3. Répondre 2 serait le degré de A, de B, de E ou de F ; répondre 6 serait donner le nombre de sommets du graphe.
Toujours sur l'arbre de référence (racine 8 ; à gauche 3 avec les fils 1 et 6, et 6 a pour fils 4 et 7 ; à droite 10 dont le seul fils est 14, qui a pour fils gauche 13). Quel est son parcours préfixe ?
- A.8, 3, 1, 6, 4, 7, 10, 14, 13Bonne réponse
- B.1, 3, 4, 6, 7, 8, 10, 13, 14
- C.1, 4, 7, 6, 3, 13, 14, 10, 8
- D.8, 3, 10, 1, 6, 14, 4, 7, 13
Réponse : A — 8, 3, 1, 6, 4, 7, 10, 14, 13
Le parcours préfixe traite le nœud, puis tout le sous-arbre gauche, puis tout le sous-arbre droit. On écrit 8, puis on part à gauche : 3, puis son gauche 1, puis son droit 6 qui donne 6, 4, 7. Le sous-arbre gauche est fini, on passe à droite : 10, puis 14, puis 13. D'où 8, 3, 1, 6, 4, 7, 10, 14, 13. La deuxième option est le parcours infixe (suite croissante), la troisième le suffixe (il se termine par la racine), la quatrième le parcours en largeur.
Quel est le parcours suffixe du même arbre de référence ?
- A.8, 3, 1, 6, 4, 7, 10, 14, 13
- B.8, 3, 10, 1, 6, 14, 4, 7, 13
- C.1, 3, 4, 6, 7, 8, 10, 13, 14
- D.1, 4, 7, 6, 3, 13, 14, 10, 8Bonne réponse
Réponse : D — 1, 4, 7, 6, 3, 13, 14, 10, 8
Le parcours suffixe traite le sous-arbre gauche, puis le sous-arbre droit, puis seulement le nœud : la racine sort donc toujours en dernier, ce qui élimine d'emblée les options qui commencent par 8. Dans le sous-arbre gauche : 1, puis pour 6 on obtient 4, 7, 6, puis 3. À droite : 14 n'a que 13 à gauche, donc 13, 14, puis 10. Enfin la racine 8. Résultat : 1, 4, 7, 6, 3, 13, 14, 10, 8.
Dans le graphe de référence (A–B, A–C, B–D, C–D, C–E, D–F, E–F), on effectue un parcours en largeur depuis A en examinant les voisins par ordre alphabétique. Quel est l'ordre de visite ?
- A.A, B, D, C, E, F
- B.A, B, C, D, E, FBonne réponse
- C.A, C, B, D, F, E
- D.A, B, D, F, E, C
Réponse : B — A, B, C, D, E, F
On enfile A, puis on le défile en enfilant ses voisins B et C. On défile B : son seul voisin neuf est D, qu'on enfile. On défile C : ses voisins sont A (visité), D (déjà enfilé) et E, donc on enfile E. On défile D et on enfile F. On défile E puis F, plus rien de neuf. L'ordre est A, B, C, D, E, F. La première option est le parcours en profondeur : dans un parcours en largeur, il est impossible de visiter D avant C, car C est à distance 1 de A alors que D est à distance 2.
Sur le même graphe, on effectue cette fois un parcours en profondeur récursif depuis A, en examinant les voisins par ordre alphabétique. Quel est l'ordre de visite ?
- A.A, B, C, D, E, F
- B.A, C, E, F, D, B
- C.A, B, D, C, E, FBonne réponse
- D.A, B, D, F, C, E
Réponse : C — A, B, D, C, E, F
Depuis A, le premier voisin est B, on y plonge. Depuis B, le seul voisin non visité est D. Depuis D, les voisins sont B (visité), C et F : par ordre alphabétique on prend C. Depuis C, les voisins sont A (visité), D (visité) et E : on prend E. Depuis E, on atteint F. Depuis F, tout est visité, on remonte et le parcours s'arrête. Ordre : A, B, D, C, E, F. La première option est le parcours en largeur ; la deuxième supposerait de commencer par C alors que B vient avant dans l'ordre alphabétique.
Dans le graphe de référence (A–B, A–C, B–D, C–D, C–E, D–F, E–F), quelle est la distance de A à F, c'est-à-dire le nombre minimal d'arêtes d'un chemin de A vers F ?
- A.2
- B.3Bonne réponse
- C.4
- D.5
Réponse : B — 3
F n'est voisin ni de A, ni d'aucun voisin direct de A, donc la distance est au moins 3. Et le chemin A–B–D–F utilise exactement 3 arêtes : la distance vaut donc 3. On peut le retrouver avec le parcours en largeur, qui donne les distances A = 0, B = 1, C = 1, D = 2, E = 2 et F = 3. Répondre 2 reviendrait à croire que F est voisin de B ou de C, ce qui est faux. Les chemins A–C–D–F et A–C–E–F font aussi 3 arêtes : le plus court chemin n'est pas unique, mais sa longueur, si.
On construit un ABR en insérant successivement les valeurs 1, 2, 3, 4, 5, 6, 7 dans cet ordre. Quel est le coût d'une recherche dans le pire cas ?
- A.O(log n), car un ABR est toujours équilibré
- B.O(1), car les valeurs sont consécutives
- C.O(n), car l'arbre obtenu est filiformeBonne réponse
- D.O(n log n), comme un tri efficace
Réponse : C — O(n), car l'arbre obtenu est filiforme
Chaque nouvelle valeur est plus grande que toutes les précédentes : elle part donc systématiquement à droite et se retrouve accrochée tout en bas. L'arbre obtenu est une simple chaîne 1 → 2 → 3 → 4 → 5 → 6 → 7, de hauteur n − 1. Comme la recherche coûte O(h) où h est la hauteur, elle devient ici O(n) : l'ABR n'apporte plus rien par rapport à une liste. Le O(log n) n'est valable que pour un arbre équilibré, ce qui n'est pas garanti par la définition d'un ABR : c'est exactement le piège de la question.
Un arbre binaire a pour parcours préfixe 5, 3, 2, 4, 8, 7, 9 et pour parcours infixe 2, 3, 4, 5, 7, 8, 9. Quel est le fils droit de la racine ?
- A.7
- B.3
- C.9
- D.8Bonne réponse
Réponse : D — 8
Le préfixe commence par la racine : elle vaut 5. Dans le parcours infixe, tout ce qui précède 5 forme le sous-arbre gauche (2, 3, 4) et tout ce qui suit forme le sous-arbre droit (7, 8, 9). Le sous-arbre gauche contient 3 nœuds, donc dans le préfixe il occupe les positions 2 à 4 (3, 2, 4) et le sous-arbre droit correspond à la fin : 8, 7, 9. Or un parcours préfixe commence toujours par la racine du sous-arbre concerné : la racine du sous-arbre droit est donc 8, c'est-à-dire le fils droit de 5. On peut poursuivre : dans l'infixe 7, 8, 9, le 7 est à gauche de 8 et le 9 à sa droite.
Quelle structure de données faut-il utiliser pour réaliser un parcours en largeur ?
- A.Une pile (LIFO)
- B.Un arbre binaire de recherche
- C.Un dictionnaire trié par clé
- D.Une file (FIFO)Bonne réponse
Réponse : D — Une file (FIFO)
Le parcours en largeur explore les sommets par distance croissante : il doit donc traiter les sommets dans l'ordre exact où il les a découverts. C'est précisément le comportement d'une file, « premier entré, premier sorti ». Avec une pile, on repartirait au contraire du dernier sommet découvert et on obtiendrait un parcours en profondeur. Ni l'ABR ni le dictionnaire trié ne jouent ce rôle de file d'attente.

S'entraîner sur ce chapitre

Ce chapitre compte 37 exercices corrigés dans l'application, avec le suivi de ta progression.

Commencer les exercices