Arbres binaires NSI : la checklist pour réussir

Les arbres binaires sont au programme de NSI, et ils font peur à beaucoup d'élèves. Pourtant, une fois que tu as compris la logique, c'est l'une des structures les plus élégantes de l'informatique. Dans cet article, je te propose une checklist complète pour maîtriser les arbres binaires en NSI : vocabulaire, parcours, arbre binaire de recherche, code Python et méthode de révision. Prêt ? On part de la racine et on descend ensemble.

1. Vocabulaire : parler arbre sans se perdre

Avant de coder, il faut parler la même langue que ton professeur et que le jury du bac. Un arbre binaire est une structure de données hiérarchique où chaque nœud possède au maximum deux enfants : un enfant gauche et un enfant droit. C'est une définition simple, mais elle cache un vocabulaire précis que tu dois absolument connaître.

Les mots-clés à retenir

• Racine (root) : le nœud tout en haut, le point d'entrée de l'arbre. Il n'a pas de parent.
• Feuille : un nœud sans aucun enfant. C'est là que l'arbre s'arrête.
• Nœud interne : un nœud qui possède au moins un enfant.
• Parent / enfant : relation directe entre deux nœuds reliés.
• Frères : deux nœuds qui partagent le même parent.
• Hauteur : longueur du plus long chemin entre la racine et une feuille. Un arbre réduit à une feuille a une hauteur de 0.
• Taille : nombre total de nœuds de l'arbre.
• Sous-arbre : tout nœud et ses descendants forment eux-mêmes un arbre binaire.

Retiens bien ces termes : ils tombent très souvent dans les sujets écrits et pratiques. Si tu veux des fiches synthétiques, jette un œil aux fiches de révision NSI.

Arbre binaire vs arbre général

Un arbre général autorise un nombre quelconque d'enfants par nœud. Un arbre binaire en autorise au plus deux, et on distingue gauche et droite. Cette distinction est essentielle : elle permet des parcours ordonnés et des recherches efficaces.

2. Représenter un arbre binaire en Python

En NSI, on représente un arbre binaire de deux manières : avec des tuples/listes imbriqués, ou avec une classe Noeud. La deuxième est plus lisible et c'est celle que tu utiliseras en pratique.

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

# Construction manuelle d'un petit arbre
#        5
#       / \
#      3   8
#     / \
#    1   4
arbre = Noeud(5,
            Noeud(3, Noeud(1), Noeud(4)),
            Noeud(8))

Chaque nœud contient une valeur, un pointeur vers son sous-arbre gauche et un vers son sous-arbre droit. Quand un enfant n'existe pas, on utilise None.

Mesurer la taille et la hauteur

Ces deux fonctions sont des classiques du bac. Elles se font naturellement en récursif.

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

def hauteur(a):
    if a is None:
        return -1   # convention : arbre vide = -1
    return 1 + max(hauteur(a.gauche), hauteur(a.droite))

Attention à la convention pour la hauteur : certains sujets considèrent qu'un arbre vide a une hauteur de -1 (comme ci-dessus), d'autres 0. Lis toujours l'énoncé !

3. Les parcours : le cœur du programme

Parcourir un arbre, c'est visiter tous ses nœuds dans un ordre précis. Il existe deux grandes familles : les parcours en profondeur et les parcours en largeur.

Parcours en profondeur (DFS)

Trois ordres à connaître par cœur :

• Préfixe (racine, gauche, droite) : on traite le nœud avant ses enfants.
• Infixe (gauche, racine, droite) : on traite le nœud entre ses deux enfants. Sur un ABR, cela donne les valeurs triées !
• Suffixe (gauche, droite, racine) : on traite le nœud après ses enfants.

def parcours_prefixe(a):
    if a is None:
        return []
    return [a.valeur] + parcours_prefixe(a.gauche) + parcours_prefixe(a.droite)

def parcours_infixe(a):
    if a is None:
        return []
    return parcours_infixe(a.gauche) + [a.valeur] + parcours_infixe(a.droite)

def parcours_suffixe(a):
    if a is None:
        return []
    return parcours_suffixe(a.gauche) + parcours_suffixe(a.droite) + [a.valeur]

Sur l'arbre exemple, parcours_infixe(arbre) renvoie [1, 3, 4, 5, 8]. C'est l'une des propriétés les plus utiles des arbres binaires de recherche.

Parcours en largeur (BFS)

On visite niveau par niveau, de gauche à droite. On utilise une file (collections.deque).

from collections import deque

def parcours_largeur(a):
    if a is None:
        return []
    resultat = []
    file = deque([a])
    while file:
        noeud = file.popleft()
        resultat.append(noeud.valeur)
        if noeud.gauche:
            file.append(noeud.gauche)
        if noeud.droite:
            file.append(noeud.droite)
    return resultat

Ce parcours sert notamment à afficher un arbre niveau par niveau ou à trouver le plus court chemin en nombre d'arêtes.

4. L'arbre binaire de recherche (ABR)

Un arbre binaire de recherche est un arbre binaire qui respecte une règle d'ordre : pour chaque nœud, toutes les valeurs du sous-arbre gauche sont inférieures à la valeur du nœud, et toutes celles du sous-arbre droit sont supérieures. Cette propriété rend la recherche très rapide : à chaque étape, on divise l'espace de recherche par deux.

Recherche dans un ABR

def recherche(abr, x):
    if abr is None:
        return False
    if abr.valeur == x:
        return True
    if x < abr.valeur:
        return recherche(abr.gauche, x)
    return recherche(abr.droite, x)

Complexité : O(h) où h est la hauteur. Si l'arbre est équilibré, h ≈ log(n), donc la recherche est très efficace. Si l'arbre est dégénéré (chaque nœud n'a qu'un enfant), on retombe sur O(n), comme une liste.

Insertion dans un ABR

def inserer(abr, x):
    if abr is None:
        return Noeud(x)
    if x < abr.valeur:
        abr.gauche = inserer(abr.gauche, x)
    elif x > abr.valeur:
        abr.droite = inserer(abr.droite, x)
    return abr

On descend tant que l'on peut, puis on accroche le nouveau nœud à la place du None rencontré. C'est l'opération de base pour construire un ABR à partir d'une liste de valeurs.

Cas d'usage concret : un dictionnaire ordonné

Imagine un annuaire de contacts. Tu veux pouvoir ajouter des noms et retrouver rapidement un numéro. Un ABR te donne un accès en O(log n) et permet en plus d'afficher les contacts dans l'ordre alphabétique grâce au parcours infixe. C'est exactement la structure utilisée dans certains index de bases de données.

Si tu veux t'entraîner sur ce genre d'exercice, va voir les exercices NSI et les cours NSI pour consolider les bases.

5. Checklist de révision pour le bac NSI

Voici ta checklist personnelle. Coche chaque case au fur et à mesure.

• Je sais définir racine, feuille, hauteur, taille, sous-arbre.
• Je sais dessiner un arbre binaire à partir d'une liste de valeurs.
• Je sais écrire en Python taille et hauteur en récursif.
• Je connais les trois parcours en profondeur (préfixe, infixe, suffixe) et je sais les coder.
• Je sais coder un parcours en largeur avec une file.
• Je sais expliquer la propriété d'un arbre binaire de recherche.
• Je sais coder recherche et inserer dans un ABR.
• Je sais donner la complexité d'une recherche dans un ABR équilibré (O(log n)) et dégénéré (O(n)).
• Je sais convertir un parcours infixe en liste triée.

Astuce : code ces fonctions sans regarder, puis compare avec ton cours. La récursivité sur les arbres est un réflexe à acquérir, un peu comme les boucles for en Première.

Pour aller plus loin et travailler avec un prof, tu peux aussi consulter les ressources du réseau Allo Education, par exemple AlloLycée pour du soutien scolaire, ou AlloBac pour préparer l'épreuve.

6. Conclusion : tu as les clés

Les arbres binaires en NSI ne sont pas un monstre : ce sont juste des nœuds reliés par des règles simples. Si tu maîtrises le vocabulaire, les parcours et l'ABR, tu couvres 90 % des questions du bac. Entraîne-toi régulièrement, code à la main, dessine tes arbres. Et surtout, n'hésite pas à revenir sur les cours NSI dès qu'un point bloque. Tu vas y arriver 💪