Arbres au Bac NSI : vocabulaire, parcours, arbres binaires de recherche et récursivité
Mis à jour le · AprenAI
Les arbres sont dans 13 exercices sur les 136 des annales de Métropole (9,6 %), répartis sur 13 sujets entre 2021 et 2026, et la plupart portent sur les arbres binaires de recherche (ABR). On y attend le vocabulaire (racine, feuille, taille, hauteur), les parcours, l'insertion d'une clé et l'écriture d'une fonction récursive.
- 50 sujets officiels
- 9,9 % des sujets
- 2021-2026 années
Que faut-il savoir sur les arbres et les arbres binaires de recherche ?
Un arbre est une structure hiérarchique de nœuds. Le nœud initial, sans père, est la racine. Un nœud sans enfant est une feuille. Dans un arbre binaire, chaque nœud a au plus deux fils, un gauche et un droit. L'arbre des débats de l'exercice de 2026 n'est pas binaire : sa racine possède quatre enfants, et c'est la justification attendue à la question qui le demande.
Deux mesures sont toujours rappelées dans l'énoncé. La taille est le nombre de nœuds. La hauteur est le nombre de nœuds du plus long chemin de la racine à une feuille, avec la convention que l'arbre à un seul nœud a une hauteur de 1 et l'arbre vide une hauteur de 0. L'arbre de l'exercice de 2021 a ainsi 9 nœuds et une hauteur de 4. Lisez toujours cette convention avant de répondre, car elle peut changer d'un sujet à l'autre.
Un arbre binaire de recherche (ABR) range ses clés pour accélérer la recherche : les clés du sous-arbre gauche sont inférieures à celle du nœud, celles du sous-arbre droit sont supérieures. Selon le sujet, les clés sont toutes distinctes (2021, 2023), ou une clé égale va à droite (2024) ou à gauche (certains sujets de 2022). Pour insérer une clé, on part de la racine, on compare, on descend à gauche ou à droite jusqu'à trouver une place libre, où la clé devient une feuille.
Il y a deux grandes familles de parcours. Le parcours en profondeur existe en trois variantes selon le moment où on traite la racine : préfixe (racine, gauche, droite), infixe (gauche, racine, droite) et suffixe (gauche, droite, racine). Le parcours en largeur visite les nœuds niveau par niveau de gauche à droite, avec une file. Le parcours infixe d'un ABR donne les clés dans l'ordre croissant : c'est la réponse à retenir quand on demande comment obtenir un classement de la plus petite à la plus grande valeur.
Les algorithmes sur les arbres sont naturellement récursifs : on traite la racine, puis on relance la même fonction sur le sous-arbre gauche et sur le sous-arbre droit. Un cas de base arrête la récursion (arbre vide ou feuille). C'est la structure des fonctions présent, de recherche ou de somme des exercices.
- Racine: Nœud sans père, au sommet de l'arbre.
- Feuille: Nœud sans enfant.
- Taille: Nombre de nœuds de l'arbre.
- Hauteur: Nombre de nœuds du plus long chemin entre la racine et une feuille (1 pour un arbre à un seul nœud).
- Arbre binaire de recherche: Arbre binaire où chaque nœud est supérieur aux clés de son sous-arbre gauche et inférieur à celles de son sous-arbre droit.
- Parcours infixe: Sous-arbre gauche, puis racine, puis sous-arbre droit. Dans un ABR, il liste les clés dans l'ordre croissant.
- Parcours en largeur: Visite des nœuds niveau par niveau, de la racine vers les feuilles, avec une file.
| Parcours | Ordre | Résultat sur un ABR |
|---|---|---|
| Préfixe | racine, gauche, droite | Racine d'abord |
| Infixe | gauche, racine, droite | Clés triées par ordre croissant |
| Suffixe | gauche, droite, racine | Racine en dernier |
| Largeur | niveau par niveau | Utilise une file |
Quels exercices de Bac sont tombés sur les arbres ?
Sur 13 exercices (répartition : 2021 : 4 ; 2022 : 4 ; 2023 : 1 ; 2024 : 1 ; 2025 : 2 ; 2026 : 1), le thème est donné chaque année. En 2021 et 2022, huit exercices ou parties en parlent, dont sept exercices entiers de 4 points consacrés aux arbres binaires. Depuis 2023, ce sont des parties de 2,5 à 6 points : 3,75 points en 2024, 2025 et 2026, jusqu'à 6 points pour l'exercice de compression de Shannon-Fano en 2025.
- Vocabulaire, taille, hauteur et sous-arbres (5): Compter les feuilles, donner la hauteur et la taille, décrire un sous-arbre, reconnaître la racine, les feuilles et les sous-arbres d'un schéma. Exemples : « Métropole France 1 2021, exercice 1 » (valeurs possibles de val dans l'ABR), « Métropole France 1 2022, exercice 4 » (somme des nœuds et parcours en largeur) et « Métropole France 1 2026, exercice 3, partie A » (arbre de débat).
- ABR : insertion et parcours infixe (5): Insérer des clés successives, dessiner l'arbre obtenu, donner un parcours, expliquer pourquoi le parcours infixe trie les clés. Exemples : « Métropole France 1 2024, exercice 3 » (insertion de onze équipes selon leur temps, puis suppression de deux nœuds) et « Métropole France 2 remplacement 2022, exercice 2 » (parcours suffixe, insertion de 28, hauteur).
- Algorithmes récursifs et implémentation (3): Compléter une fonction récursive sur un ABR, ou une classe de nœud. Exemples : « Métropole France 1 remplacement 2022, exercice 1 » (fonction de recherche d'une valeur), « Métropole France 1 2025, exercice 3, partie D » (table de routage en ABR) et « Métropole France 2 2025, exercice 1 » (arbre de codage de Shannon-Fano).
- Exercice 1 · Métropole 2021 (sujet 1) · Vocabulaire, taille, hauteur et sous-arbres
- Exercice 4 · Métropole 2022 (sujet 1) · Vocabulaire, taille, hauteur et sous-arbres
- Exercice 3 - Arbres binaires de recherche · Métropole 2024 (sujet 1) · ABR : insertion et parcours infixe
- Exercice 2 · Métropole 2 remplacement 2022 · ABR : insertion et parcours infixe
- Exercice 1 · Métropole 1 remplacement 2022 · Algorithmes récursifs et implémentation
- Exercice 3 - Partie D : Arbres binaires de recher… · Métropole 2025 (sujet 1) · Algorithmes récursifs et implémentation
Entraîne-toi : Arbres et arbres binaires de recherche (50 sujets officiels)
Tous les sujets de NSI sur « Arbres et arbres binaires de recherche » (2021-2026), avec le corrigé.
Comment résoudre un exercice sur les arbres binaires de recherche ?
Exemple : « Métropole France 1 2021, exercice 1 ». On donne un ABR de racine 18 avec une clé inconnue val, puis on pose six questions indépendantes. Les réponses du corrigé : 4 feuilles, hauteur 4, taille 9.
- Lire les conventions: L'énoncé précise que les clés sont distinctes et qu'un ABR à un nœud a une hauteur de 1. Notez-le avant de répondre.
- Repérer les feuilles et compter: Les feuilles sont 12, val, 21 et 32 : il y en a 4. L'arbre a 9 nœuds. Le sous-arbre gauche du nœud 23 est le nœud 19, qui a pour seul enfant un fils droit 21.
- Encadrer la clé inconnue: val est dans le sous-arbre gauche de 18, donc val < 18. Il est aussi dans le sous-arbre droit de 15, donc val > 15. Seules les valeurs entières 16 et 17 conviennent.
- Appliquer le bon parcours: Le parcours infixe donne les clés dans l'ordre croissant : 12, 13, 15, 16, 18, 19, 21, 23, 32. Le parcours suffixe visite le sous-arbre gauche, le sous-arbre droit, puis la racine : 12, 13, 16, 15, 21, 19, 32, 23, 18.
- Reconstituer un arbre par insertions: On insère les clés une à une depuis la racine en comparant : 12 < 18 va à gauche, 13 > 12 va à droite de 12, etc. Chaque comparaison est écrite, ce qui prouve la démarche.
À ne pas confondre
- Taille ≠ Hauteur: La taille compte les nœuds. La hauteur compte les nœuds du plus long chemin racine-feuille.
- Parcours infixe ≠ Parcours suffixe: L'infixe traite la racine entre les deux sous-arbres et trie un ABR. Le suffixe traite la racine en dernier.
- Parcours en profondeur ≠ Parcours en largeur: La profondeur descend d'abord jusqu'aux feuilles. La largeur explore niveau par niveau avec une file.
- Arbre binaire ≠ Arbre binaire de recherche: Un arbre binaire limite à deux enfants par nœud. Un ABR ajoute une règle d'ordre sur les clés.
- Feuille ≠ Racine: La racine n'a pas de père. Une feuille n'a pas d'enfant. Un arbre à un seul nœud a une racine qui est aussi une feuille.
Mode Bac : ce qui rapporte des points
- Hauteur et taille: Hauteur : plus long chemin en nombre de nœuds (1 pour un seul nœud). Taille : nombre total de nœuds.
- Règle de l'ABR: Gauche plus petit, droite plus grand. Vérifiez-la pour chaque nœud, pas seulement pour la racine.
- Parcours infixe: Dans un ABR, il donne les clés dans l'ordre croissant : c'est la réponse à « classer de la plus petite à la plus grande ».
- Insertion: On compare à chaque nœud rencontré depuis la racine et on place la clé en feuille.
- Récursivité: Dire où est le cas de base (arbre vide) et où se fait l'appel récursif sur le sous-arbre gauche ou droit.
Quelles erreurs éviter sur les arbres ?
Les corrigés de ce thème sont des réponses détaillées, sans barème par question. Voici ce qu'ils attendent explicitement.
- Se tromper de convention pour la hauteur: Certains sujets donnent la hauteur en nombre de nœuds et partent de 1 pour un seul nœud. Dans l'exercice du 2022 (Métropole France 2), la branche 15, 21, 18, 20 donne une hauteur 4.
- Mal gérer les clés égales: Dans l'exercice de 2024, la règle est : strictement plus rapide à gauche, moins rapide ou égal à droite. Dans celui de 2021, les clés sont distinctes. Appliquez la règle de l'énoncé.
- Confondre infixe et suffixe: Dans l'exercice de 2021, le parcours suffixe donne 12, 13, 16, 15, 21, 19, 32, 23, 18 et l'infixe donne l'ordre croissant. La racine ferme le suffixe.
- Oublier de justifier que l'arbre n'est pas binaire: Pour l'arbre de débat de 2026, il faut dire qu'un nœud peut avoir plus de deux fils, par exemple la racine qui a quatre enfants.
- Oublier le cas de base: Une fonction récursive sur un arbre doit traiter l'arbre vide ou la feuille avant d'appeler les sous-arbres. Dans la fonction present de 2023, la valeur trouvée à la racine renvoie True, une valeur plus grande relance la recherche à droite, sinon à gauche.
- Supprimer sans méthode: Pour supprimer un nœud à un fils (eq2 en 2024), on relie directement son fils à son père. Pour un nœud à deux fils (eq5), on le remplace par le plus petit nœud de son sous-arbre droit.
Comment réviser les arbres pour le Bac NSI ?
- Dessiner: Prenez un ABR, dessinez-le, donnez ses trois parcours, sa hauteur, sa taille. Refaites-le avec une insertion.
- Écrire les trois algorithmes de base: Recherche d'une valeur, calcul de la hauteur et calcul de la taille, en version récursive.
- Connaître la classe Noeud: Les sujets donnent une classe avec racine, gauche et droit. Entraînez-vous à écrire des méthodes qui l'utilisent.
- Voir le lien avec la POO: Dans plusieurs sujets (2021, 2022, 2024), les arbres sont mêlés à la programmation orientée objet.
- Faire le lien avec la compression: L'exercice de 2025 utilise un arbre de codage où le code d'un symbole est le chemin de la racine à sa feuille. Pour le décoder, on descend dans l'arbre bit par bit.
Quelle est la hauteur d'un arbre à un seul nœud en NSI ?
Dans les sujets du Bac qui la définissent en nombre de nœuds, elle vaut 1, et l'arbre vide a une hauteur de 0. Vérifiez toujours la convention rappelée dans l'énoncé.
Quel parcours donne les clés d'un ABR dans l'ordre croissant ?
Le parcours infixe : sous-arbre gauche, racine, sous-arbre droit. C'est la réponse attendue pour un classement de la plus petite à la plus grande valeur.
Comment insère-t-on une clé dans un ABR ?
On part de la racine et on compare : plus petit, on va à gauche ; plus grand, à droite. On continue jusqu'à un sous-arbre vide, où la clé devient une feuille.
Comment décode-t-on un mot binaire avec un arbre de codage ?
On part de la racine, on suit la branche 0 ou 1 selon chaque bit jusqu'à une feuille, qui donne le symbole, puis on recommence depuis la racine pour le bit suivant.
Pourquoi un arbre de débat n'est-il pas binaire ?
Parce qu'un nœud peut avoir plus de deux enfants : dans l'exercice de 2026, la racine en a quatre.
Plus sur l'épreuve de NSI
- Piles, files, listes et dictionnaires · 66 sujets
- Programmation orientée objet · 46 sujets
- Graphes : modélisation et parcours · 27 sujets
- Bases de données et SQL · 83 sujets
- Binaire, entiers et opérateurs booléens · 16 sujets
- Architectures matérielles et systèmes d'exploitation · 32 sujets
- Réseaux : adressage IP et sous-réseaux · 39 sujets
- Protocoles de routage : RIP et OSPF · 51 sujets
- Sécurisation des communications : chiffrement et HTTPS · 9 sujets
- Récursivité · 24 sujets
- Modularité, API et paradigmes de programmation · 6 sujets
- Mise au point des programmes : bugs, assertions et tests · 13 sujets
- Programme comme donnée, calculabilité et décidabilité · 2 sujets
- Diviser pour régner · 8 sujets
- Programmation dynamique · 7 sujets
- Recherche textuelle et algorithme de Boyer-Moore · 3 sujets
- Coût des algorithmes, tris et recherche · 23 sujets