Numérique et sciences informatiques (spécialité) · TerminaleBac
Algorithmes sur les arbres binaires : quiz de Terminale NSI
Publié le 7 novembre 2026 · Mis à jour le 7 novembre 2026 · Signaler une erreur
L'essentiel
- Un arbre binaire est soit vide, soit un nœud racine avec un fils gauche et un fils droit, eux-mêmes des arbres binaires 4.
- La taille d'un arbre est son nombre de nœuds ; sa hauteur est limitée par la taille, au maximum n − 1 pour un arbre filiforme 4.
- Taille et hauteur se calculent par récursivité, en traitant l'arbre vide comme cas de base 2.
- Un parcours en largeur donne les étiquettes niveau par niveau ; le parcours infixé d'un arbre binaire de recherche donne les clés dans l'ordre 356.
Avant de commencer
Ce quiz porte sur les algorithmes qui travaillent sur les arbres binaires : reconnaître la structure, calculer une taille ou une hauteur, écrire une fonction récursive, parcourir un arbre et exploiter un arbre binaire de recherche. Le programme de Terminale demande justement de savoir calculer la taille et la hauteur d'un arbre et de le parcourir de différentes façons 2. Réponds d'abord sans regarder ton cours, puis lis chaque explication, même quand ta réponse est bonne : elle montre aussi pourquoi l'erreur la plus tentante est fausse.
Quiz
16 questions · correction immédiate · ton score reste sur ton appareil.
-
Le nombre de nœuds s'appelle la taille 4. La hauteur est une longueur de chemin, pas un nombre de nœuds. La confusion entre taille et hauteur est fréquente : un arbre de taille 7 peut avoir une hauteur de 2 comme de 6.
-
C'est vrai : rien n'oblige les valeurs à être distinctes dans un arbre binaire 4. Penser le contraire vient de l'idée qu'une valeur identifie un nœud ; or un nœud est repéré par sa place dans l'arbre.
-
Dans un arbre complet, il y a nœuds à la profondeur 4. Pour : . L'erreur tentante est de répondre 6 en calculant : le nombre de nœuds double à chaque niveau, il ne croît pas de façon linéaire.
-
À chaque profondeur de 0 à 3, il y a nœuds 4. La taille vaut donc . Répondre 8 revient à ne compter que le dernier niveau.
-
Pour une taille fixée, la hauteur maximale est 4. Avec , on obtient 9. Répondre 10 correspond à l'autre convention, où l'on compte les nœuds du plus long chemin au lieu de ses arêtes : lis toujours la définition donnée par l'énoncé.
-
La hauteur maximale s'obtient avec des arbres filiformes 4 : chaque nœud descend d'un seul côté, comme une liste chaînée. Un arbre complet est au contraire le plus « compact » : il a beaucoup de nœuds pour une petite hauteur.
-
Le sujet du bac 2024 indique qu'un arbre est soit vide, représenté en Python par
None, soit un nœud 5. Utiliser0serait ambigu, car0peut être une étiquette valide ; c'est pour cette raison qu'on testearbre is Nonedans le cas de base. -
Le cas de base est l'arbre vide, de taille 0 ; sinon on compte la racine puis les nœuds des deux fils, ce qui correspond à la structure récursive d'un arbre binaire 24. La deuxième version renvoie 1 pour l'arbre vide et ne compte jamais la racine. La troisième ignore le fils droit et plante sur
None. La quatrième utilisemax, ce qui ne compte pas les nœuds. -
La hauteur est celle du chemin le plus long vers le bas, donc on prend le maximum des deux fils, auquel on ajoute 1 pour l'arête qui descend depuis la racine. Pour un seul nœud, les deux fils sont vides : , ce qui respecte avec 4. Additionner les hauteurs mélange hauteur et taille ; le minimum donnerait le chemin le plus court.
-
Dans ce sujet, la fonction attendue produit une liste contenant les étiquettes de tous les nœuds, dans l'ordre d'un parcours en largeur 5. Ce parcours visite les nœuds niveau par niveau : racine, puis profondeur 1, puis profondeur 2, etc. Il ne trie rien et ne se limite pas aux feuilles.
-
Pour visiter les nœuds niveau par niveau, il faut traiter les fils dans l'ordre où ils ont été découverts : c'est le fonctionnement d'une file. Avec une pile, on repartirait toujours en profondeur vers le dernier fils trouvé, ce qui donnerait un autre ordre de visite, pas un parcours en largeur.
-
Un ABR a pour structure logique un arbre binaire, ses nœuds utilisent les mêmes attributs, dont la clé, et ses clés doivent être comparables, contrairement à un arbre binaire général 6. La dernière affirmation est fausse : la réciproque ne tient pas, car un arbre binaire quelconque peut contenir des valeurs rangées sans aucun ordre.
-
Chaque nœud est traité une seule fois, avec un travail constant, donc le coût est proportionnel à la taille . Un coût en ne vaut que si l'on descend un seul chemin dans un arbre équilibré, ce qui n'est pas le cas d'un parcours complet. Un coût en ou supposerait de revisiter des nœuds.
Les questions qu'on se pose
Quelle différence entre la taille et la hauteur d'un arbre binaire ?
La taille est le nombre de nœuds 4. La hauteur mesure la longueur du plus long chemin descendant depuis la racine. Pour une taille donnée, la hauteur peut varier : elle atteint son maximum pour un arbre filiforme 4 et reste bien plus petite pour un arbre complet, où les niveaux se remplissent. Les deux se calculent par récursivité 2.
Pourquoi les fonctions sur les arbres sont-elles presque toujours récursives ?
Parce que la définition d'un arbre binaire est elle-même récursive : un arbre est vide ou formé d'une racine et de deux arbres binaires 4. Une fonction suit donc le même schéma : un cas de base pour l'arbre vide, puis un appel sur le fils gauche et sur le fils droit, dont on combine les résultats. Une structure de données récursive adaptée est d'ailleurs utilisée pour ces algorithmes 2.
Qu'est-ce qui peut tomber au bac de NSI sur ce sujet ?
Les sujets de bac de NSI proposent des exercices où l'on manipule des arbres binaires en Python, par exemple une fonction qui renvoie la liste des étiquettes en parcours en largeur 5. Savoir calculer la taille et la hauteur et parcourir un arbre fait partie des attendus du programme 2. Entraîne-toi à écrire ces fonctions à la main, en traitant d'abord le cas de l'arbre vide.
Sources
Programme visé : Numérique et sciences informatiques - Spécialité Terminale - Algorithmique : Arbres binaires · Éduscol (Ministère de l'Éducation nationale)
- Numérique et sciences informatiques - Spécialité Terminale - Algorithmique : Arbres binaires, Éduscol (Ministère de l'Éducation nationale). Consulté le 7 novembre 2026.
- Ressource d'accompagnement - Arbres binaires de recherche, Éduscol. Consulté le 7 novembre 2026.
- Types abstraits de données et structures de données, Éduscol. Consulté le 7 novembre 2026.
- Structures de données - NSI Spécialité, Éduscol. Consulté le 7 novembre 2026.
- Sujet du Baccalauréat 2024 - NSI Jour 2, Ministère de l'Éducation nationale. Consulté le 7 novembre 2026.
- Guide pédagogique - Algorithmes sur arbres binaires, Éduscol. Consulté le 7 novembre 2026.
Les numéros dans le texte renvoient à ces sources. Une source qui ne dit pas ce qu'on lui fait dire ? Signale-le.