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

Algorithmes sur les arbres binaires : cours 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é, avec le cas vide comme cas de base.
Taille = nombre de nœuds ; hauteur = longueur du plus long chemin de la racine à un nœud (un arbre réduit à sa racine est de hauteur 0, l'arbre vide de hauteur −1 par convention).
Parcours en profondeur : préfixe (racine, gauche, droit), infixe (gauche, racine, droit), suffixe (gauche, droit, racine) ; seul l'ordre des trois étapes change.
Parcours en largeur : niveau par niveau, de gauche à droite, avec une file ; ce n'est pas une récursion.
Sur un arbre binaire de recherche, le parcours infixé donne les clés dans l'ordre croissant. Chaque nœud est visité une fois : coût proportionnel à la taille.

Pourquoi étudier les algorithmes sur les arbres

Une liste, un tableau, une pile : ce sont des structures linéaires, où les éléments se suivent les uns les autres. L'arbre binaire est différent. Il est rangé dans la catégorie des structures hiérarchiques : chaque élément peut avoir deux « suivants » et non un seul.⁴ Cette forme sert à représenter une organisation (dossiers et sous-dossiers, décisions successives, expressions de calcul) et à ranger des données pour les retrouver vite.

Le programme de Terminale demande de savoir calculer la taille et la hauteur d'un arbre, et de le parcourir de différentes manières.² Dans ce cours, tu vas apprendre à écrire ces algorithmes toi-même, à les dérouler à la main sur un exemple, et à éviter les erreurs que l'on retrouve chaque année dans les copies du bac.

Le fil conducteur est une idée simple : un arbre est fait d'arbres plus petits. Dès que tu l'as compris, la plupart des algorithmes tiennent en trois ou quatre lignes.

Définition d'un arbre binaire

Cette définition est récursive : elle utilise le mot qu'elle définit. Cela ne tourne pas en rond, car il y a un point d'arrêt, l'arbre vide. Un arbre contenant un seul nœud est donc un nœud dont les deux fils sont des arbres vides.

Un nœud contient une donnée. Pour simplifier, on suppose ici que ces données sont des entiers.⁴ Une même valeur peut apparaître dans deux nœuds différents.⁴

Représenter un arbre binaire en Python

Pour programmer, il faut choisir une représentation. Les sujets de bac notent l'absence d'arbre avec la valeur None de Python ; dans tous les autres cas, l'arbre est un nœud.⁵ Un nœud regroupe sa valeur et ses deux sous-arbres. Nous utilisons une classe, mais un énoncé peut employer un tuple ou un dictionnaire : seule la lecture des champs change, pas la logique des algorithmes.

MéthodeUne classe Noeud

class Noeud:
    def __init__(self, valeur, gauche=None, droit=None):
        self.valeur = valeur
        self.gauche = gauche   # un arbre : None ou un Noeud
        self.droit = droit     # idem

L'arbre d'exemple se construit de bas en haut :

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

Un arbre vide s'écrit simplement None.

Cas de baseQue renvoyer pour l'arbre vide (None) ?
Appels sur les filsAppeler la fonction sur gauche et sur droit.
CombinerAssembler ces résultats avec la racine.
VérifierTester sur vide, racine seule, petit arbre.

Écrire une fonction récursive sur un arbre · La même démarche sert pour la taille, la hauteur et les parcours.

Taille et hauteur d'un arbre

Comment raisonner ? Un arbre non vide contient sa racine, plus tous les nœuds de son sous-arbre gauche, plus tous ceux de son sous-arbre droit. On obtient la relation, pour un arbre non vide :

$\text{taille}(a) = 1 + \text{taille}(\text{gauche}) + \text{taille}(\text{droit}).$

Il suffit de la traduire en Python.

MéthodeAlgorithme de la taille

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

Sur l'arbre d'exemple : les feuilles valent $1$ chacune. Le nœud $6$ vaut $1+1+1=3$ . Le nœud $3$ vaut $1+1+3=5$ . Le nœud $13$ vaut $1$ , donc $14$ vaut $1+1+0=2$ et $10$ vaut $1+0+2=3$ . Enfin la racine vaut $1+5+3=9$ .

Pour un arbre non vide, la hauteur est $1$ de plus que la hauteur du plus haut de ses deux fils, car il faut ajouter l'arête qui relie la racine à ce fils. Pour que la formule marche aussi quand un fils est vide, on convient que l'arbre vide a pour hauteur $-1$ : une racine seule vaut alors $1+\max(-1,-1)=0$ .

$\text{hauteur}(a) = 1 + \max\big(\text{hauteur}(\text{gauche}),\ \text{hauteur}(\text{droit})\big).$

MéthodeAlgorithme de la hauteur

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

Sur l'arbre d'exemple, on trouve $0$ pour $1$ , $4$ , $7$ , $13$ ; puis $1$ pour $6$ ; $2$ pour $3$ ; $1$ pour $14$ (son fils droit est vide, valeur $-1$ , mais son fils gauche vaut $0$ ) ; $2$ pour $10$ ; et enfin $3$ pour la racine.

Arbres complets et arbres filiformes : les bornes de la hauteur

Calculons la taille d'un arbre complet de hauteur $h$ . Il y a $1$ nœud à la profondeur $0$ , $2$ à la profondeur $1$ , $4$ à la profondeur $2$ , et ainsi de suite jusqu'à $2^h$ . Le total est la somme d'une suite géométrique :

$n = 1 + 2 + 4 + \dots + 2^h = 2^{h+1} - 1.$

Par exemple, un arbre complet de hauteur $3$ contient $2^4-1=15$ nœuds.

Les parcours en profondeur

Parcourir un arbre, c'est visiter chacun de ses nœuds une fois, dans un ordre précis, par exemple pour afficher ou rassembler ses valeurs. Il existe plusieurs façons de le faire.² Les trois premières sont dites en profondeur : on descend jusqu'au bout d'une branche avant de passer à la suivante. Elles ne diffèrent que par le moment où l'on traite la racine, par rapport aux deux appels récursifs.

MéthodeÉcrire les trois parcours

On construit une liste de résultats. Chaque fonction renvoie la liste des valeurs dans l'ordre voulu.

def prefixe(a):
    if a is None:
        return []
    return [a.valeur] + prefixe(a.gauche) + prefixe(a.droit)

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

def suffixe(a):
    if a is None:
        return []
    return suffixe(a.gauche) + suffixe(a.droit) + [a.valeur]

Les trois fonctions sont identiques, à une permutation près des trois termes de la dernière ligne.

Les parcours sur l'arbre d'exemple
Parcours	Ordre de visite	Résultat
Préfixe	racine, gauche, droit	8, 3, 1, 6, 4, 7, 10, 14, 13
Infixe	gauche, racine, droit	1, 3, 4, 6, 7, 8, 10, 13, 14
Suffixe	gauche, droit, racine	1, 4, 7, 6, 3, 13, 14, 10, 8
Largeur	niveau par niveau	8, 3, 10, 1, 6, 14, 4, 7, 13

Les parcours sur l'arbre d'exemple · Même arbre, ordres de visite différents.

Démonstration · Pourquoi la fonction se termine et visite chaque nœud une fois

Chaque appel récursif porte sur un sous-arbre strictement plus petit que l'arbre courant : il a au moins un nœud de moins (la racine). La taille décroît donc strictement et finit par atteindre $0$ , c'est-à-dire l'arbre vide, où la fonction s'arrête sans nouvel appel. Par ailleurs, chaque nœud est la racine d'exactement un sous-arbre, donc la fonction est appelée une seule fois sur lui avec un arbre non vide. Pour $n$ nœuds, il y a ainsi $n$ appels sur des nœuds et $n+1$ appels sur des arbres vides (chaque nœud a deux fils, soit $2n$ appels, dont $n-1$ sur des nœuds non racine, donc $2n-(n-1)=n+1$ sur des arbres vides). Le nombre total d'appels est proportionnel à $n$ : le coût est linéaire en la taille.

Le parcours en largeur

Le parcours en largeur visite l'arbre niveau par niveau : d'abord la racine, puis tous les nœuds de profondeur $1$ de gauche à droite, puis ceux de profondeur $2$ , etc. Il figure au programme et revient dans les sujets : un sujet de baccalauréat demande d'écrire une fonction qui, pour un arbre donné, fournit sous forme de liste les étiquettes de ses nœuds dans l'ordre d'un parcours en largeur.⁵

Sur l'arbre d'exemple, on lit : $8$ ; puis $3, 10$ ; puis $1, 6, 14$ ; puis $4, 7, 13$ . Le résultat est $[8, 3, 10, 1, 6, 14, 4, 7, 13]$ .

Cette fois, la récursivité ne convient pas directement : après avoir visité $3$ , on ne descend pas dans ses fils, on passe à $10$ . Il faut donc mémoriser les nœuds à visiter plus tard, dans l'ordre où on les a rencontrés. La structure adaptée est la file : premier entré, premier sorti. On y met la racine, puis on répète : retirer le nœud en tête de file, le traiter, ajouter ses fils non vides à la fin de la file.

MéthodeAlgorithme du parcours en largeur

from collections import deque

def largeur(a):
    resultat = []
    if a is None:
        return resultat
    file = deque([a])
    while file:
        n = file.popleft()          # on sort le plus ancien
        resultat.append(n.valeur)
        if n.gauche is not None:
            file.append(n.gauche)
        if n.droit is not None:
            file.append(n.droit)
    return resultat

On ajoute le fils gauche avant le droit : c'est ce qui garantit l'ordre « de gauche à droite » dans chaque niveau.

Le cas des arbres binaires de recherche

Une classe particulière d'arbres binaires est celle des arbres binaires de recherche (ABR). Ils ont pour structure logique un arbre binaire et supportent des opérations de recherche et de modification.⁶ Leurs nœuds utilisent les mêmes attributs que ceux d'un arbre binaire : le programme note par exemple n.clé la valeur contenue dans le nœud $n$ .⁶ La différence est qu'on y range les clés selon un ordre : à la différence d'un arbre binaire quelconque, il faut que l'on puisse comparer entre elles deux clés d'un ABR.⁶

MéthodeÉcrire une recherche dans un ABR

Comme les clés sont ordonnées, une recherche n'explore qu'une seule branche : si la clé cherchée est plus petite que celle du nœud courant, on continue à gauche ; si elle est plus grande, on continue à droite.

def contient(a, cle):
    if a is None:
        return False
    if cle == a.valeur:
        return True
    if cle < a.valeur:
        return contient(a.gauche, cle)
    return contient(a.droit, cle)

Le nombre d'appels est au plus la hauteur plus un : dans un arbre équilibré, c'est de l'ordre de $\log_2(n)$ ; dans un arbre filiforme, c'est $n$ . D'où l'intérêt de maîtriser la hauteur.

Méthode générale et erreurs fréquentes

ExempleCompter les feuilles

Application de la méthode. Cas de base : l'arbre vide a $0$ feuille. Cas général : si les deux fils sont vides, la racine est une feuille ; sinon le nombre de feuilles est la somme de celles des deux fils.

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

Sur l'arbre d'exemple : $4$ feuilles ( $1$ , $4$ , $7$ , $13$ ).

Exercices corrigés

Exercice 1 Taille d'un arbre complet

★☆☆Environ 8 min

On considère un arbre binaire complet de hauteur $4$ (la racine est à la profondeur $0$ ).

Combien de nœuds y a-t-il à chacune des profondeurs $0$ , $1$ , $2$ , $3$ et $4$ ?
En déduire la taille de l'arbre.
Vérifie ton résultat avec la formule $2^{h+1}-1$ .

Indice 1

À la profondeur $p$ , il y a $2^p$ nœuds dans un arbre complet.

Indice 2

La taille est la somme des nœuds de toutes les profondeurs, de $0$ à $4$ .

Voir la correction pas à pas

Profondeur $0$ : $2^0 = 1$ nœud ; profondeur $1$ : $2$ ; profondeur $2$ : $4$ ; profondeur $3$ : $8$ ; profondeur $4$ : $16$ .
On additionne : $1+2+4+8+16 = 31$ .
Avec la formule : $2^{4+1}-1 = 32-1 = 31$ . Les deux calculs coïncident.

Un arbre complet de hauteur $4$ contient $31$ nœuds, dont $16$ feuilles. Le nombre de nœuds double presque à chaque niveau ajouté, ce qui explique qu'un arbre équilibré reste de faible hauteur même pour beaucoup de données.

Exercice 2 Hauteur d'un arbre de recherche construit par insertions

★★☆Environ 15 min

On construit un arbre binaire de recherche en insérant, dans cet ordre, les clés $50, 30, 70, 20, 40, 60, 80, 35$ . La première clé devient la racine. Pour chaque clé suivante, on part de la racine : si la clé est plus petite que celle du nœud, on descend à gauche, sinon à droite, jusqu'à trouver une place vide où l'on crée un nouveau nœud.

Dessine l'arbre obtenu.
Donne son parcours infixe.
Quelle est sa hauteur (racine seule = hauteur $0$ ) ?

Indice 1

Place $35$ en dernier : il est plus petit que $50$ , plus grand que $30$ , plus petit que $40$ .

Indice 2

La hauteur est le nombre d'arêtes du plus long chemin depuis la racine.

Voir la correction pas à pas

On insère $50$ (racine), puis $30$ à gauche de $50$ , $70$ à droite, $20$ à gauche de $30$ , $40$ à droite de $30$ , $60$ à gauche de $70$ , $80$ à droite de $70$ .
On insère $35$ : $35<50$ donc à gauche ; $35>30$ donc à droite ; $35<40$ donc à gauche de $40$ , qui est libre.
Le parcours infixe donne les clés dans l'ordre croissant : $[20, 30, 35, 40, 50, 60, 70, 80]$ .
Le plus long chemin est $50 \to 30 \to 40 \to 35$ : $3$ arêtes, soit une hauteur de $3$ . Les autres branches ont une longueur de $2$ au plus.

La hauteur est $3$ pour $8$ nœuds. Le parcours infixe est bien croissant, comme attendu pour un ABR. Si l'on avait inséré les mêmes clés dans l'ordre croissant, on aurait obtenu un arbre filiforme de hauteur $7$ : l'ordre d'insertion compte.

Les questions qu'on se pose

Pourquoi la hauteur de l'arbre vide vaut-elle −1 ?

C'est une convention qui rend la formule $1+\max(h_g, h_d)$ valable partout. Avec la convention où une racine seule est de hauteur $0$ ,⁴ il faut que l'arbre vide soit à $-1$ pour que $1+\max(-1,-1)=0$ . Certains énoncés choisissent de compter en nœuds ; la valeur du cas de base change alors. Lis l'exemple du sujet pour savoir laquelle est utilisée.

Quelle est la différence entre parcours en profondeur et parcours en largeur ?

Le parcours en profondeur descend jusqu'aux feuilles d'une branche avant de passer à la suivante et s'écrit naturellement par récursivité (préfixe, infixe, suffixe). Le parcours en largeur visite l'arbre niveau par niveau et utilise une file.⁵ Les deux visitent chaque nœud une seule fois.

Comment savoir quel parcours utiliser à l'examen ?

L'énoncé le nomme ou donne un exemple de résultat. Si tu dois obtenir les clés d'un arbre de recherche rangées dans l'ordre, c'est l'infixe.³ Si l'énoncé parle de « niveau par niveau » ou demande les étiquettes dans l'ordre d'un parcours en largeur,⁵ c'est la file. En cas de doute, déroule l'exemple du sujet à la main avec chaque ordre et garde celui qui donne la liste attendue.

Pourquoi mes fonctions récursives plantent-elles sur certains arbres ?

Dans la grande majorité des cas, le cas de base est absent ou mal placé : on essaie de lire .gauche ou .valeur sur None. Écris toujours if a is None: en première ligne. Autre cause possible : un return oublié devant un appel récursif. Enfin, un arbre filiforme très grand peut dépasser la profondeur maximale de récursion de Python ; ce n'est pas le cas dans les exercices du programme.

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