Les pièges à éviter sur les arbres binaires en NSI

Les arbres binaires sont une structure de données incontournable en NSI, que ce soit en Première ou en Terminale. Pourtant, beaucoup d'élèves tombent dans les mêmes pièges : confondre arbre binaire et arbre binaire de recherche, mal gérer la récursivité, ou encore se tromper dans les parcours. Dans cet article, on va passer en revue les erreurs les plus fréquentes, avec des exemples concrets en Python, pour que tu les évites aux prochains DS ou au bac. Prêt à devenir un as des arbres ?

Piège n°1 : Confondre arbre binaire et arbre binaire de recherche (ABR)

Un arbre binaire est une structure où chaque nœud a au plus deux enfants (gauche et droite). Un arbre binaire de recherche (ABR) est un cas particulier : pour chaque nœud, tous les éléments du sous-arbre gauche sont plus petits que la valeur du nœud, et tous ceux du sous-arbre droit sont plus grands. C'est une propriété qui permet de faire des recherches rapides.

L'erreur classique : croire que tout arbre binaire est trié. Non ! Un arbre binaire peut contenir des valeurs dans n'importe quel ordre. Par exemple :

# Arbre binaire quelconque
class Noeud:
    def __init__(self, val, gauche=None, droite=None):
        self.val = val
        self.gauche = gauche
        self.droite = droite

# Exemple : pas un ABR car 8 > 5 mais placé à gauche
racine = Noeud(5, Noeud(8), Noeud(3))

Ici, 8 est à gauche de 5, ce qui viole la propriété d'ABR. Pour vérifier si un arbre est un ABR, il faut parcourir et vérifier les bornes. Ne confonds pas la définition générale avec le cas particulier.

Piège n°2 : Implémenter la récursivité sans cas de base

Les algorithmes sur les arbres sont souvent récursifs. L'erreur la plus fréquente : oublier le cas de base if arbre is None. Sans cela, la fonction boucle infiniment ou lève une erreur d'attribut.

Exemple pour calculer la hauteur :

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

Si tu omets le if arbre is None, tu vas essayer d'accéder à arbre.gauche sur None. Pense toujours à traiter le cas de l'arbre vide en premier.

Piège n°3 : Se tromper dans les parcours (ordre des visites)

Les parcours d'arbres (préfixe, infixe, suffixe) sont souvent confondus. Voici un rappel simple :

• Préfixe : on traite la racine, puis sous-arbre gauche, puis sous-arbre droit.
• Infixe : sous-arbre gauche, racine, sous-arbre droit (donne les valeurs triées dans un ABR).
• Suffixe (ou postfixe) : sous-arbre gauche, sous-arbre droit, racine.

Une erreur typique : écrire un parcours infixe et croire qu'il donne l'ordre croissant même si l'arbre n'est pas un ABR. Ce n'est vrai que pour un ABR. Teste toujours avec un arbre quelconque pour vérifier.

Exemple de parcours infixe en Python :

def parcours_infixe(arbre):
    if arbre:
        parcours_infixe(arbre.gauche)
        print(arbre.val)
        parcours_infixe(arbre.droite)

Piège n°4 : Oublier la mutabilité lors de l'insertion dans un ABR

Quand on insère un élément dans un ABR, il faut modifier l'arbre en place ou retourner le nouveau sous-arbre. Beaucoup d'élèves écrivent une fonction qui ne retourne rien et espèrent que l'arbre se modifie tout seul, mais Python passe les objets par référence, donc il faut faire attention.

Voici une insertion correcte qui retourne le nouvel arbre :

def inserer(arbre, val):
    if arbre is None:
        return Noeud(val)
    if val < arbre.val:
        arbre.gauche = inserer(arbre.gauche, val)
    else:
        arbre.droite = inserer(arbre.droite, val)
    return arbre

Si tu oublies le return arbre ou si tu ne réaffectes pas le résultat, l'arbre ne sera pas modifié correctement.

Piège n°5 : Mal gérer la suppression dans un ABR

La suppression d'un nœud dans un ABR est plus complexe. L'erreur courante : oublier de traiter le cas où le nœud a deux enfants. Il faut alors le remplacer par le plus petit du sous-arbre droit (ou le plus grand du sous-arbre gauche).

Exemple simplifié :

def supprimer(arbre, val):
    if arbre is None:
        return None
    if val < arbre.val:
        arbre.gauche = supprimer(arbre.gauche, val)
    elif val > arbre.val:
        arbre.droite = supprimer(arbre.droite, val)
    else:
        # Cas 1 : pas d'enfant ou un seul
        if arbre.gauche is None:
            return arbre.droite
        if arbre.droite is None:
            return arbre.gauche
        # Cas 2 : deux enfants
        min_noeud = trouver_min(arbre.droite)
        arbre.val = min_noeud.val
        arbre.droite = supprimer(arbre.droite, min_noeud.val)
    return arbre

Ne pas oublier de retourner l'arbre modifié à chaque étape.

Piège n°6 : Croire que la récursivité est toujours la meilleure solution

La récursivité est élégante, mais elle peut entraîner une profondeur de récursion excessive si l'arbre est déséquilibré (ex : arbre filiforme). Dans certains cas, une approche itérative avec une pile est plus efficace. En NSI, on te demande souvent d'implémenter les deux versions. Ne néglige pas la version itérative.

Exemple de parcours préfixe itératif :

def parcours_prefixe_iteratif(arbre):
    pile = [arbre]
    while pile:
        noeud = pile.pop()
        if noeud:
            print(noeud.val)
            pile.append(noeud.droite)
            pile.append(noeud.gauche)

Attention à l'ordre d'empilement : on empile d'abord le droit pour que le gauche soit traité en premier.

Piège n°7 : Négliger les arbres binaires dans les exercices de bac

Les arbres binaires sont un thème récurrent au bac NSI. Les exercices peuvent porter sur la création, les parcours, la recherche, l'insertion, la suppression, ou encore l'équilibre. Il est essentiel de maîtriser ces concepts. Pour t'entraîner, consulte les exercices sur les arbres binaires et les fiches de révision. Tu peux aussi revoir le cours sur les arbres pour consolider les bases.

Conseils de méthode pour éviter ces pièges

Voici quelques astuces pour aborder sereinement les arbres binaires :

• Dessine toujours l'arbre avant d'écrire du code. Visualiser les liens aide à comprendre la récursivité.
• Teste ton code sur des cas simples : arbre vide, un seul nœud, arbre déséquilibré.
• Pour les ABR, vérifie la propriété d'ordre avec un parcours infixe.
• Utilise un débogueur ou des print pour suivre l'exécution récursive.
• Révise les parcours en les programmant de plusieurs façons (récursif et itératif).
• Pour t'entraîner, n'hésite pas à consulter des ressources comme AlloBac ou AlloLycée qui proposent des exercices corrigés.

Enfin, souviens-toi que la maîtrise des arbres binaires te servira aussi pour d'autres structures comme les tas ou les arbres binaires de recherche équilibrés (AVL) vus en Terminale.

Conclusion

Les arbres binaires sont un sujet riche mais piégeur. En évitant ces erreurs courantes – confusion entre arbre binaire et ABR, oubli du cas de base, mauvais parcours, mauvaise gestion de l'insertion/suppression – tu seras bien armé pour les épreuves. Continue à t'entraîner régulièrement, et n'oublie pas que chaque erreur est une occasion d'apprendre. Bon courage, tu vas y arriver !