Aller au contenu
FR

Numérique et sciences informatiques (spécialité) · TerminaleBac

Algorithmes sur les arbres binaires : exercices de Terminale NSI

Publié le 7 novembre 2026 · Mis à jour le 7 novembre 2026 · Signaler une erreur

L'essentiel

  • Un arbre binaire est vide, ou formé d'une racine avec un fils gauche et un fils droit, eux-mêmes des arbres binaires : presque tous les algorithmes s'écrivent donc par récursivité.
  • La taille est le nombre de nœuds ; la hauteur se compte en arêtes sur le plus long chemin de la racine à un nœud (un nœud seul a une hauteur de 0).
  • Pour une taille n, la hauteur maximale est n − 1 (arbre filiforme) ; un arbre complet de hauteur h a 2^p nœuds à chaque profondeur p.
  • Dans un arbre binaire de recherche, le parcours infixe donne les clés dans l'ordre croissant ; le parcours en largeur utilise une file.

Comment utiliser ces exercices

Ces exercices vont du calcul à la main sur un petit arbre jusqu'à l'écriture de fonctions Python. Cherche d'abord seul, sur papier, avec un brouillon où tu dessines l'arbre. Ouvre un indice seulement si tu es bloqué, puis compare ta réponse à la correction étape par étape. Si ton résultat diffère, repère l'étape où vos chemins se séparent : c'est là que se trouve l'erreur à comprendre.

Pour écrire un nœud, on utilise les attributs cle (la valeur contenue dans le nœud), gauche et droit, comme dans les ressources officielles où l'on note n.clé la valeur d'un nœud 6. Voici la classe commune :

class Noeud:
    def __init__(self, cle, gauche=None, droit=None):
        self.cle = cle
        self.gauche = gauche
        self.droit = droit

Un nœud sans fils se crée simplement par Noeud(4) : ses deux fils valent None, c'est-à-dire qu'ils sont des arbres vides.

Les exercices

Exercice 1 Compter les nœuds d'un arbre

★☆☆Environ 8 min

On construit l'arbre suivant en Python :

arbre = Noeud(8,
    Noeud(3, Noeud(1), Noeud(6, Noeud(4), Noeud(7))),
    Noeud(10, None, Noeud(14, Noeud(13), None)))

Quelle est la taille de cet arbre, c'est-à-dire son nombre de nœuds 4 ?

Indice 1

Dessine l'arbre : la racine porte 8, son fils gauche porte 3 et son fils droit porte 10.

Indice 2

Compte séparément le sous-arbre gauche et le sous-arbre droit, puis ajoute 1 pour la racine.

Voir la correction pas à pas

  1. Le sous-arbre gauche a pour racine 3. Ses fils sont 1 (une feuille) et 6, qui a elle-même deux fils, 4 et 7. Il contient donc les nœuds 3, 1, 6, 4 et 7 : 5 nœuds.

  2. Le sous-arbre droit a pour racine 10. Son fils gauche est vide ; son fils droit est 14, qui a un seul fils, 13. Il contient 10, 14 et 13 : 3 nœuds.

  3. On applique la relation récursive : taille = 1 (la racine) + 5 + 3 = 9.

La taille de l'arbre est 9. Cette relation « 1 + taille du fils gauche + taille du fils droit » est exactement ce que fera la fonction récursive de l'exercice 5.

Exercice 2 Calculer une hauteur par récursivité

★☆☆Environ 8 min

Soit l'arbre :

b = Noeud(5, Noeud(2, None, Noeud(9)), Noeud(7))

On utilise la convention du début de page : un arbre vide a pour hauteur −1, et la hauteur d'un arbre non vide vaut 1 plus le maximum des hauteurs de ses deux fils. Calcule la hauteur de b.

Indice 1

Commence par les feuilles : quelle est la hauteur d'un nœud sans fils ?

Indice 2

Le nœud 2 n'a qu'un fils droit : son fils gauche vide vaut −1.

Voir la correction pas à pas

  1. La feuille 9 a deux fils vides : sa hauteur est 1 + max(−1 ; −1) = 0.

  2. Le nœud 2 a un fils gauche vide (−1) et le fils droit 9 (hauteur 0) : sa hauteur est 1 + max(−1 ; 0) = 1.

  3. La feuille 7 a pour hauteur 0, comme la feuille 9.

  4. La racine 5 a pour fils 2 (hauteur 1) et 7 (hauteur 0) : sa hauteur est 1 + max(1 ; 0) = 2.

La hauteur de b est 2 : le plus long chemin descend de 5 à 2, puis à 9. Remarque que la branche la plus longue décide seule du résultat, grâce au maximum.

Exercice 3 Combien de nœuds dans un arbre complet ?

★★☆Environ 10 min

Un arbre binaire de hauteur h est dit complet quand chaque niveau est entièrement rempli : à la profondeur p, on compte alors 2p2^p nœuds 4. Par exemple, un arbre complet de hauteur 2 a 1+2+4=71 + 2 + 4 = 7 nœuds, ce qui correspond à l'arbre de taille 7 des ressources officielles 4.

Quelle est la taille d'un arbre complet de hauteur 4 ?

Indice 1

Écris le nombre de nœuds à chaque profondeur, de 0 jusqu'à 4.

Indice 2

Additionne les puissances de 2 obtenues.

Voir la correction pas à pas

  1. Profondeur 0 : 20=12^0 = 1 nœud (la racine). Profondeur 1 : 21=22^1 = 2. Profondeur 2 : 22=42^2 = 4. Profondeur 3 : 23=82^3 = 8. Profondeur 4 : 24=162^4 = 16.

  2. On additionne tous les niveaux : 1+2+4+8+16=311 + 2 + 4 + 8 + 16 = 31.

  3. Vérification par une autre voie : le niveau suivant (profondeur 5) aurait 32 nœuds, et la somme précédente vaut 32 − 1 = 31. On retrouve bien ce résultat.

Un arbre complet de hauteur 4 contient 31 nœuds. On généralise : un arbre complet de hauteur h a 2h+1−12^{h+1} - 1 nœuds. C'est aussi le plus grand nombre de nœuds qu'un arbre de hauteur h puisse contenir, ce qui explique pourquoi un arbre bien équilibré reste peu profond même avec beaucoup de données.

Exercice 4 Le pire cas : l'arbre filiforme

★★☆Environ 8 min

Parmi tous les arbres binaires de n nœuds, les plus hauts sont les arbres « filiformes », dont la hauteur atteint n − 1 4. Un arbre filiforme est un arbre dont chaque nœud a au plus un fils.

  1. Dessine un arbre filiforme de taille 4 et donne sa hauteur.
  2. Quelle est la hauteur maximale d'un arbre binaire de 20 nœuds ?
  3. Pourquoi un tel arbre est-il un mauvais cas pour un algorithme qui descend de la racine jusqu'à une feuille ?
Indice 1

Un arbre filiforme ressemble à une liste chaînée : chaque nœud a un seul fils.

Indice 2

Pour la question 3, compare le nombre de nœuds visités dans un arbre complet et dans un arbre filiforme de même taille.

Voir la correction pas à pas

  1. Question 1 : par exemple 1 → 2 → 3 → 4, chaque nœud étant le fils droit du précédent. Il y a 3 arêtes, donc une hauteur de 3 = 4 − 1.

  2. Question 2 : la hauteur maximale pour 20 nœuds est 20−1=1920 - 1 = 19.

  3. Question 3 : dans cet arbre, descendre jusqu'à la feuille oblige à passer par les 20 nœuds, alors que dans un arbre complet de 31 nœuds on atteint n'importe quelle feuille en 5 nœuds seulement. Le coût d'une descente dépend de la hauteur, et la hauteur est ici aussi grande que possible.

La hauteur maximale pour 20 nœuds est 19. Retiens que la taille ne suffit pas à prévoir le coût d'un algorithme sur un arbre : c'est la hauteur qui compte, et elle varie de très petite (arbre équilibré) à n − 1 (arbre filiforme).

Exercice 5 Écrire les fonctions taille et hauteur

★★☆Environ 15 min

Écris en Python deux fonctions récursives taille(a) et hauteur(a) qui prennent en paramètre un arbre binaire a, éventuellement vide (None) 5. On utilise la convention de hauteur du début de page. Teste-les mentalement sur l'arbre de l'exercice 1 : tu dois trouver une taille de 9 et une hauteur de 3.

Indice 1

Les deux fonctions commencent par if a is None:. Que doivent-elles renvoyer pour un arbre vide ?

Indice 2

Dans chaque cas, appelle la fonction sur a.gauche et sur a.droit, puis combine les résultats avec la racine.

Voir la correction pas à pas

  1. Cas de base de taille : un arbre vide a 0 nœud, donc return 0.

  2. Cas général de taille : on compte la racine, plus les nœuds de chaque sous-arbre : return 1 + taille(a.gauche) + taille(a.droit).

  3. Cas de base de hauteur : return -1 pour l'arbre vide, afin qu'une feuille obtienne 1 + max(-1, -1) = 0.

  4. Cas général de hauteur : return 1 + max(hauteur(a.gauche), hauteur(a.droit)).

  5. Test sur l'arbre de l'exercice 1 : la plus longue branche est 8 → 3 → 6 → 4 (ou 8 → 10 → 14 → 13), soit 3 arêtes, ce qui correspond à la fonction.

Voici la solution complète :

def taille(a):
    if a is None:
        return 0
    return 1 + taille(a.gauche) + taille(a.droit)

def hauteur(a):
    if a is None:
        return -1
    return 1 + max(hauteur(a.gauche), hauteur(a.droit))

Calculer la taille et la hauteur d'un arbre fait partie des algorithmes de base au programme 2. Les deux fonctions visitent chaque nœud une fois, et leur forme suit celle de la définition récursive de l'arbre.

Exercice 6 Lire un arbre binaire de recherche dans l'ordre

★★☆Environ 12 min

On construit un arbre binaire de recherche en insérant successivement les clés 8, 3, 10, 1, 6, 14, 4, 7, 13 dans un arbre initialement vide. La règle d'insertion est la suivante : on descend depuis la racine, vers la gauche si la clé à insérer est plus petite que celle du nœud rencontré, vers la droite sinon, jusqu'à trouver une place vide. Les clés d'un tel arbre doivent être comparables 6.

  1. Dessine l'arbre obtenu (tu dois retrouver celui de l'exercice 1).
  2. Le parcours infixe d'un arbre binaire de recherche permet de donner ses éléments dans l'ordre 3. Écris la liste obtenue.
  3. Quelle est la cinquième clé de cette liste ?
Indice 1

Insère les clés dans l'ordre donné ; la première, 8, devient la racine.

Indice 2

Le parcours infixe visite le sous-arbre gauche, puis la racine, puis le sous-arbre droit, à chaque nœud.

Voir la correction pas à pas

  1. Insertions : 8 est la racine. 3 < 8 va à gauche. 10 > 8 va à droite. 1 < 8 puis 1 < 3 : fils gauche de 3. 6 < 8 puis 6 > 3 : fils droit de 3. 14 > 8 puis 14 > 10 : fils droit de 10. 4 < 8, 4 > 3, 4 < 6 : fils gauche de 6. 7 < 8, 7 > 3, 7 > 6 : fils droit de 6. 13 > 8, 13 > 10, 13 < 14 : fils gauche de 14.

  2. Parcours infixe : on lit d'abord tout le sous-arbre gauche de 8 (en infixe : 1, 3, 4, 6, 7), puis 8, puis le sous-arbre droit (en infixe : 10, 13, 14).

  3. La liste obtenue est donc 1, 3, 4, 6, 7, 8, 10, 13, 14 : elle est bien triée par ordre croissant.

  4. La cinquième clé de cette liste est 7.

La cinquième clé est 7. Le parcours infixe d'un arbre binaire de recherche redonne les clés triées : c'est la raison pour laquelle on l'utilise pour obtenir les éléments dans l'ordre 3. Voici une fonction qui construit cette liste :

def infixe(a):
    if a is None:
        return []
    return infixe(a.gauche) + [a.cle] + infixe(a.droit)

Elle fonctionne, mais les concaténations de listes recopient des données ; une version qui ajoute les clés à une unique liste partagée est plus efficace, comme le suggère l'énoncé du guide pédagogique sur la recherche d'une réalisation efficace du parcours infixé 6.

Exercice 7 Parcourir un arbre en largeur avec une file

★★★Environ 20 min

Un parcours en largeur renvoie la liste des étiquettes des nœuds de l'arbre, niveau par niveau, de la racine vers les feuilles et de gauche à droite à l'intérieur d'un niveau 5.

  1. Écris une fonction largeur(a) qui renvoie cette liste pour un arbre a éventuellement vide. Tu utiliseras une file, par exemple collections.deque avec ses méthodes append et popleft.
  2. Applique-la à l'arbre de l'exercice 1.
  3. Calcule la somme des étiquettes situées à la profondeur 2.
Indice 1

La file contient les nœuds restant à traiter. Au départ, elle contient la racine.

Indice 2

À chaque tour de boucle, retire le nœud en tête de file, note sa clé, puis ajoute ses fils non vides en queue de file.

Indice 3

Pour la question 3, repère dans la liste obtenue les nœuds du troisième niveau.

Voir la correction pas à pas

  1. Cas de l'arbre vide : on renvoie directement la liste vide [].

  2. On initialise la file avec la racine et une liste résultat vide.

  3. Tant que la file n'est pas vide : on retire le premier nœud avec popleft(), on ajoute sa cle au résultat, puis on ajoute à la file son fils gauche s'il n'est pas None, puis son fils droit s'il n'est pas None.

  4. Sur l'arbre de l'exercice 1, la file évolue ainsi : 8 ; puis 3, 10 ; puis 10, 1, 6 ; puis 1, 6, 14 ; etc. Le résultat est 8, 3, 10, 1, 6, 14, 4, 7, 13.

  5. Les nœuds de profondeur 2 sont ceux du troisième niveau : 1, 6 et 14. Leur somme vaut 1 + 6 + 14 = 21.

La somme demandée est 21. Voici le code complet :

from collections import deque

def largeur(a):
    if a is None:
        return []
    file = deque([a])
    resultat = []
    while file:
        n = file.popleft()
        resultat.append(n.cle)
        if n.gauche is not None:
            file.append(n.gauche)
        if n.droit is not None:
            file.append(n.droit)
    return resultat

La différence avec les parcours récursifs est que la file garantit que tous les nœuds d'un niveau sont traités avant ceux du niveau suivant. Cet algorithme est la base du parcours de graphes en largeur, que tu retrouveras ensuite.

Exercice 8 Combien d'appels récursifs ?

★★★Environ 15 min

On exécute la fonction taille de l'exercice 5 sur un arbre binaire de taille n. À chaque appel, la fonction reçoit soit un nœud, soit None.

  1. Combien de places de fils possède un arbre de n nœuds (chaque nœud en a deux) ?
  2. Parmi ces places, combien sont occupées par un nœud ? En déduire combien contiennent None.
  3. Exprime le nombre total d'appels de taille en fonction de n, puis calcule-le pour l'arbre de l'exercice 1 (n = 9).
Indice 1

Chaque nœud, sauf la racine, est le fils d'un unique autre nœud.

Indice 2

Il y a un appel par nœud, et un appel par arbre vide rencontré.

Voir la correction pas à pas

  1. Question 1 : n nœuds, deux places de fils chacun, soit 2n places.

  2. Question 2 : tous les nœuds sauf la racine occupent une de ces places, soit n − 1 places occupées. Il reste donc 2n−(n−1)=n+12n - (n - 1) = n + 1 places vides, c'est-à-dire n + 1 appels sur None.

  3. Question 3 : il y a un appel par nœud (n) et un appel par place vide (n + 1) : au total n+(n+1)=2n+1n + (n + 1) = 2n + 1 appels. Pour n = 9, cela donne 2×9+1=192 \times 9 + 1 = 19 appels.

Il y a 19 appels pour l'arbre de l'exercice 1. Le nombre d'appels est proportionnel à la taille de l'arbre, quelle que soit sa forme : la fonction taille a un coût linéaire en n. À l'inverse, la hauteur n'intervient pas dans ce calcul, alors qu'elle intervient dans les algorithmes qui descendent un seul chemin.

Les questions qu'on se pose

Pourquoi la hauteur d'un arbre vide vaut-elle −1 dans ces exercices ?

C'est une convention qui rend la formule récursive uniforme : avec −1 pour l'arbre vide, une feuille obtient 1+max⁡(−1,−1)=01 + \max(-1, -1) = 0, et un arbre filiforme de taille n a bien pour hauteur n − 1 4. Certains énoncés comptent la hauteur en niveaux (un nœud seul vaut alors 1) : lis toujours la convention de l'énoncé avant de répondre.

Quelle est la différence entre la taille et la hauteur d'un arbre ?

La taille est le nombre total de nœuds 4. La hauteur mesure la longueur du plus long chemin depuis la racine : elle indique la profondeur maximale. Deux arbres de même taille peuvent avoir des hauteurs très différentes, de la plus petite possible (arbre bien rempli) à n − 1 pour un arbre filiforme 4.

Pourquoi utiliser une file pour le parcours en largeur et la récursivité pour les autres ?

Les parcours récursifs traitent un sous-arbre en entier avant de passer au suivant, ce qui revient à descendre en profondeur. Le parcours en largeur doit au contraire traiter tout un niveau avant le niveau suivant : une file, où l'on retire en tête et où l'on ajoute en queue, donne exactement cet ordre. À l'écrit du bac, un sujet peut demander de renvoyer la liste des étiquettes parcourues en largeur 5.

Sources

Programme visé : Numérique et sciences informatiques - Spécialité Terminale - Algorithmique : Arbres binaires · Éduscol (Ministère de l'Éducation nationale)

  1. Numérique et sciences informatiques - Spécialité Terminale - Algorithmique : Arbres binaires, Éduscol (Ministère de l'Éducation nationale). Consulté le 7 novembre 2026.
  2. Ressource d'accompagnement - Arbres binaires de recherche, Éduscol. Consulté le 7 novembre 2026.
  3. Types abstraits de données et structures de données, Éduscol. Consulté le 7 novembre 2026.
  4. Structures de données - NSI Spécialité, Éduscol. Consulté le 7 novembre 2026.
  5. Sujet du Baccalauréat 2024 - NSI Jour 2, Ministère de l'Éducation nationale. Consulté le 7 novembre 2026.
  6. 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.

Signaler une erreur sur cette page

Je suis en…

Primaire

  • CP Bientôt
  • CE1 Bientôt
  • CE2 Bientôt
  • CM1 Bientôt
  • CM2 Bientôt

Collège

Lycée

Supérieur

  • BTS Bientôt
  • BUT Bientôt
  • Licence Bientôt
  • Prépas Bientôt

Sur cette page