Comment parcourir un arbre binaire en largeur ?

Le parcours en largeur (BFS) se fait à l'aide d'une file. On commence par la racine, on l'enfile, puis tant que la file n'est pas vide, on défile un nœud, on le visite, et on enfile ses enfants (gauche puis droit). Cela permet de visiter les nœuds niveau par niveau.

Quel est l'intérêt d'utiliser un arbre binaire plutôt qu'une liste ?

Un arbre binaire de recherche permet des recherches, insertions et suppressions en temps logarithmique (si équilibré), alors qu'une liste non triée nécessite un temps linéaire. De plus, les arbres binaires représentent naturellement des hiérarchies.

Comment calculer la hauteur d'un arbre binaire en Python ?

La hauteur se calcule récursivement : si le nœud est None, renvoyer -1 ; sinon renvoyer 1 + max(hauteur(gauche), hauteur(droit)). Pour un arbre avec un seul nœud (racine), la hauteur est 0.

Qu'est-ce qu'un arbre binaire équilibré ?

Un arbre binaire est équilibré si pour chaque nœud, la différence de hauteur entre ses sous-arbres gauche et droit est au plus 1 (ou une constante). Cela garantit une hauteur logarithmique et donc des opérations efficaces. Les AVL et les arbres rouge-noir sont des exemples d'arbres équilibrés.

Arbres binaires en NSI : le guide complet pour le bac

Q: Quelle est la différence entre un arbre binaire et un arbre binaire de recherche ?

Un arbre binaire n'a pas de contrainte sur l'ordre des valeurs : chaque nœud a au plus deux enfants. Un arbre binaire de recherche (ABR) impose que pour chaque nœud, toutes les valeurs du sous-arbre gauche soient inférieures et toutes celles du sous-arbre droit soient supérieures. Cette propriété permet une recherche efficace en O(log n).

Les arbres binaires sont une structure de données fondamentale en informatique, et tu les retrouveras forcément au programme de NSI en première et terminale. Que ce soit pour représenter une hiérarchie, un arbre généalogique ou un dictionnaire, les arbres binaires sont partout. Dans ce guide complet, on va voir ensemble ce qu'est un arbre binaire, comment le manipuler en Python, et surtout comment le maîtriser pour le bac. Prêt ? C'est parti !

Qu'est-ce qu'un arbre binaire ?

Un arbre binaire est une structure de données hiérarchique composée de nœuds. Chaque nœud peut avoir au maximum deux enfants : un enfant gauche et un enfant droit. Le nœud tout en haut s'appelle la racine. Les nœuds qui n'ont pas d'enfants sont appelés feuilles.

Voici un exemple simple d'arbre binaire :

Ici, le nœud 1 est la racine, les nœuds 4 et 5 sont des feuilles. Chaque nœud peut stocker une valeur (un entier, une chaîne, etc.) et des références vers ses enfants.

Vocabulaire essentiel

Racine : nœud sans parent.
Feuille : nœud sans enfant.
Nœud interne : nœud qui a au moins un enfant.
Hauteur : nombre d'arêtes sur le chemin le plus long de la racine à une feuille.
Profondeur : nombre d'arêtes de la racine à un nœud donné.
Arbre binaire complet : tous les niveaux sont remplis sauf éventuellement le dernier, et les nœuds du dernier niveau sont le plus à gauche possible.

Ces notions sont importantes pour les exercices de bac, alors prends le temps de les mémoriser.

Implémentation d'un arbre binaire en Python

En NSI, on implémente souvent un arbre binaire à l'aide d'une classe Noeud. Chaque nœud contient une valeur, un enfant gauche et un enfant droit. Voici un exemple simple :

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

# Construction de l'arbre :
#       1
#      / \
#     2   3
#    / \
#   4   5

feuille4 = Noeud(4)
feuille5 = Noeud(5)
noeud2 = Noeud(2, feuille4, feuille5)
noeud3 = Noeud(3)
racine = Noeud(1, noeud2, noeud3)

Ce code est très simple et tu peux le réutiliser dans tes projets. Note que None est utilisé pour représenter l'absence d'enfant.

Parcourir un arbre binaire

Il existe trois parcours principaux en profondeur :

Parcours préfixe (racine, gauche, droite) : on visite la racine, puis le sous-arbre gauche, puis le sous-arbre droit.
Parcours infixe (gauche, racine, droite) : on visite le sous-arbre gauche, puis la racine, puis le sous-arbre droit.
Parcours suffixe (gauche, droite, racine) : on visite le sous-arbre gauche, puis le sous-arbre droit, puis la racine.

Voici comment les implémenter en Python :

def parcours_prefixe(noeud):
    if noeud is not None:
        print(noeud.valeur)
        parcours_prefixe(noeud.gauche)
        parcours_prefixe(noeud.droit)

def parcours_infixe(noeud):
    if noeud is not None:
        parcours_infixe(noeud.gauche)
        print(noeud.valeur)
        parcours_infixe(noeud.droit)

def parcours_suffixe(noeud):
    if noeud is not None:
        parcours_suffixe(noeud.gauche)
        parcours_suffixe(noeud.droit)
        print(noeud.valeur)

Teste ces fonctions sur l'arbre de l'exemple précédent. Pour l'arbre 1-2-3-4-5, le parcours infixe donne : 4, 2, 5, 1, 3. C'est logique car on parcourt d'abord le sous-arbre gauche (4, 2, 5), puis la racine (1), puis le sous-arbre droit (3).

L'arbre binaire de recherche (ABR)

Un arbre binaire de recherche (souvent abrégé ABR) est un arbre binaire qui respecte une propriété importante : pour chaque nœud, toutes les valeurs du sous-arbre gauche sont inférieures à la valeur du nœud, et toutes les valeurs du sous-arbre droit sont supérieures. Cette propriété permet de rechercher une valeur très rapidement, en temps O(log n) si l'arbre est équilibré.

Exemple d'ABR :

       8
      / \
     3   10
    / \    \
   1   6    14
      / \
     4   7

Ici, à la racine 8, tous les nœuds à gauche (3,1,6,4,7) sont plus petits, tous ceux à droite (10,14) sont plus grands.

Recherche dans un ABR

La recherche est récursive :

def rechercher(noeud, valeur):
    if noeud is None:
        return False
    if valeur == noeud.valeur:
        return True
    elif valeur < noeud.valeur:
        return rechercher(noeud.gauche, valeur)
    else:
        return rechercher(noeud.droit, valeur)

C'est super efficace : à chaque étape, on divise l'espace de recherche par deux.

Insertion dans un ABR

Pour insérer une valeur, on descend dans l'arbre jusqu'à trouver une place libre :

def inserer(noeud, valeur):
    if noeud is None:
        return Noeud(valeur)
    if valeur < noeud.valeur:
        noeud.gauche = inserer(noeud.gauche, valeur)
    else:
        noeud.droit = inserer(noeud.droit, valeur)
    return noeud

Attention : cette version ne gère pas les doublons (elle les mettra à droite). Si tu veux éviter les doublons, ajoute une condition d'égalité.

Applications concrètes des arbres binaires

Les arbres binaires sont utilisés dans de nombreux domaines :

Expressions arithmétiques : un arbre binaire peut représenter une expression comme (3 + 4) * 5. Les opérateurs sont aux nœuds internes, les nombres aux feuilles.
Moteurs de recherche : les index inversés utilisent des arbres pour accélérer la recherche de mots-clés.
Compression de données : l'algorithme de Huffman utilise un arbre binaire pour coder les caractères de manière optimale.
Bases de données : les index B-tree sont des arbres binaires équilibrés.

En NSI, tu verras souvent des exercices sur les arbres binaires de recherche pour implémenter un dictionnaire ou un ensemble. Par exemple, tu peux créer un ABR pour stocker des mots et vérifier rapidement si un mot existe.

Conseils pour le bac NSI

Voici quelques conseils pour réussir les questions sur les arbres binaires au bac :

Maîtrise les parcours : préfixe, infixe, suffixe, et aussi le parcours en largeur (BFS) avec une file. Savoir les implémenter et les reconnaître est essentiel.
Comprends la propriété d'ABR : elle permet de trier les éléments (un parcours infixe donne les valeurs dans l'ordre croissant).
Entraîne-toi à dessiner des arbres : à partir d'une liste de valeurs, construis l'ABR correspondant. Fais l'inverse : à partir d'un arbre, donne l'ordre des parcours.
Révise les algorithmes récursifs : hauteur, taille, recherche, insertion, suppression (un peu plus complexe).
Utilise les ressources du site : va voir les cours, les exercices et les fiches pour t'entraîner.

N'oublie pas que les arbres binaires sont un sujet classique au bac, alors ne les néglige pas ! Si tu as besoin d'aide supplémentaire, tu peux consulter AlloBac ou AlloLycée pour des vidéos et des exercices corrigés.

Conclusion

Tu as maintenant toutes les clés pour comprendre les arbres binaires en NSI. On a vu la définition, l'implémentation en Python, les parcours, l'arbre binaire de recherche et ses applications. N'oublie pas de t'entraîner régulièrement, car c'est en pratiquant que tu deviendras un as des arbres binaires. Bon courage pour le bac, et n'hésite pas à revenir sur ce guide si besoin !