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.

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.

ParcoursOrdreRésultat sur un ABR
Préfixeracine, gauche, droiteRacine d'abord
Infixegauche, racine, droiteClés triées par ordre croissant
Suffixegauche, droite, racineRacine en dernier
Largeurniveau par niveauUtilise 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.

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.

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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

Mode Bac : ce qui rapporte des points

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.

Comment réviser les arbres pour le Bac NSI ?

  1. Dessiner: Prenez un ABR, dessinez-le, donnez ses trois parcours, sa hauteur, sa taille. Refaites-le avec une insertion.
  2. Écrire les trois algorithmes de base: Recherche d'une valeur, calcul de la hauteur et calcul de la taille, en version récursive.
  3. 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.
  4. Voir le lien avec la POO: Dans plusieurs sujets (2021, 2022, 2024), les arbres sont mêlés à la programmation orientée objet.
  5. 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