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

Algorithmes sur les arbres binaires : fiche 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 une racine reliée à deux sous-arbres, gauche et droit, qui sont eux-mêmes des arbres binaires ⁴.
Sa taille est son nombre de nœuds ; à taille $n$ fixée, la hauteur la plus grande est $n-1$ , pour un arbre « filiforme » ⁴.
Un arbre complet de hauteur $h$ contient $2^p$ nœuds à chaque profondeur $p$ ⁴.
La structure étant récursive, taille, hauteur et parcours s'écrivent naturellement avec des fonctions récursives ².
Dans un ABR, le parcours infixe fournit les clés dans l'ordre ³.

Ce qu'il faut savoir sur la structure

En Python, l'arbre vide est représenté par la valeur None, et un arbre non vide par un nœud ⁵. La définition utilise le mot qu'elle définit : un arbre est construit à partir d'arbres plus petits. C'est ce qui rend la récursivité naturelle pour tous les algorithmes de cette fiche ².

Calculer la taille et la hauteur

Calculer la taille et la hauteur d'un arbre fait partie des algorithmes de base du programme ². La récursivité suit la définition : un cas pour l'arbre vide, un cas pour l'arbre non vide.

ExempleCode Python

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

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

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

Pour un nœud isolé : taille renvoie $1+0+0=1$ et hauteur renvoie $1+\max(-1,-1)=0$ .

Parcourir un arbre

Un arbre n'est pas linéaire : il faut choisir un ordre pour visiter les nœuds. Le programme demande de savoir parcourir un arbre de différentes manières ². L'une d'elles est le parcours en largeur, qui renvoie la liste des étiquettes des nœuds niveau par niveau ⁵.

MéthodeParcours infixe (en profondeur)

On traite d'abord le sous-arbre gauche, puis la racine, puis le sous-arbre droit.

def infixe(arbre):
    if arbre is None:
        return []
    return infixe(arbre.gauche) + [arbre.valeur] + infixe(arbre.droit)

Pour une version plus efficace, on peut éviter de recopier des listes en ajoutant les valeurs dans une même liste passée en paramètre.

Arbres binaires de recherche (ABR)

Pièges fréquents à l'épreuve

Les questions qu'on se pose

Pourquoi utilise-t-on la récursivité sur les arbres ?

Parce que la structure est elle-même récursive : un arbre binaire est vide ou formé d'une racine et de deux arbres binaires ⁴. Chaque fonction traite l'arbre vide (cas de base), puis s'appelle sur les deux fils.

Quelle valeur renvoyer pour la hauteur de l'arbre vide ?

Si tu veux qu'un nœud seul ait la hauteur $0$ , ce qui correspond à $h=n-1$ pour un arbre filiforme ⁴, l'arbre vide doit renvoyer $-1$ . Dans un énoncé, vérifie toujours la convention donnée avant de coder.

Est-ce que tous les arbres binaires sont des ABR ?

Non. Un ABR est un arbre binaire particulier : ses clés doivent être comparables ⁶, et pour chaque nœud, les clés à gauche sont inférieures ou égales à la sienne, celles à droite supérieures. Un arbre binaire quelconque peut contenir des valeurs sans ordre, et son parcours infixe n'est alors pas trié.

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.

Signaler une erreur sur cette page

Algorithmes sur les arbres binaires : fiche de Terminale NSI

L'essentiel

Ce qu'il faut savoir sur la structure

Calculer la taille et la hauteur

Parcourir un arbre

Arbres binaires de recherche (ABR)

Pièges fréquents à l'épreuve

Questions flash

Les questions qu'on se pose

Sources

Primaire

Collège

Lycée

Supérieur