Les arbres binaires sont une structure de données incontournable au programme de la spécialité NSI. Que ce soit pour stocker des données hiérarchiques, optimiser des recherches ou comprendre des algorithmes avancés, tu les retrouveras dans de nombreux exercices du bac. Pas de panique : on va voir ensemble ce qu'est un arbre binaire, comment le coder en Python, et comment l'exploiter pour réussir tes épreuves.
Qu'est-ce qu'un arbre binaire ?
Un arbre binaire est une structure 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 :
1
/ \
2 3
/ \
4 5Ici, le nœud racine est 1. Ses enfants gauche et droit sont 2 et 3. Le nœud 2 a pour enfants 4 et 5. Les nœuds 3, 4 et 5 sont des feuilles.
Propriétés essentielles
Un arbre binaire peut être :
- parfait : tous les niveaux sont remplis.
- complet : tous les niveaux sont remplis sauf le dernier, qui est rempli de gauche à droite.
- dégénéré : chaque nœud a un seul enfant (ressemble à une liste chaînée).
La hauteur d'un arbre est le nombre de niveaux (racine incluse). La taille est le nombre total de nœuds.
Implémentation en Python
En NSI, on représente souvent un arbre binaire avec des classes et des références. Voici une classe simple :
class Noeud:
def __init__(self, valeur):
self.valeur = valeur
self.gauche = None
self.droit = NonePour créer l'arbre de l'exemple précédent :
racine = Noeud(1)
racine.gauche = Noeud(2)
racine.droit = Noeud(3)
racine.gauche.gauche = Noeud(4)
racine.gauche.droit = Noeud(5)Parcours d'un arbre binaire
Il existe trois parcours en profondeur classiques :
- Préordre : racine, gauche, droit.
- Inordre : gauche, racine, droit.
- Postordre : gauche, droit, racine.
Implémentation récursive en Python :
def parcours_prefixe(noeud):
if noeud:
print(noeud.valeur)
parcours_prefixe(noeud.gauche)
parcours_prefixe(noeud.droit)
def parcours_infixe(noeud):
if noeud:
parcours_infixe(noeud.gauche)
print(noeud.valeur)
parcours_infixe(noeud.droit)
def parcours_suffixe(noeud):
if noeud:
parcours_suffixe(noeud.gauche)
parcours_suffixe(noeud.droit)
print(noeud.valeur)Pour l'arbre exemple, le parcours infixe donne : 4 2 5 1 3.
Arbre binaire de recherche (ABR)
Un arbre binaire de recherche (ABR) est un arbre binaire qui respecte une propriété d'ordre : pour chaque nœud, tous les éléments du sous-arbre gauche sont inférieurs à la valeur du nœud, et tous ceux du sous-arbre droit sont supérieurs. 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 7Pour rechercher 7, on compare à 8, on va à gauche (3), puis à droite (6), puis à droite (7).
Insertion dans un ABR
Voici une fonction d'insertion récursive :
def inserer(racine, valeur):
if racine is None:
return Noeud(valeur)
if valeur < racine.valeur:
racine.gauche = inserer(racine.gauche, valeur)
else:
racine.droit = inserer(racine.droit, valeur)
return racineCas d'usage concrets
Les arbres binaires sont partout en informatique :
- Les systèmes de fichiers : chaque dossier est un nœud, les fichiers sont des feuilles.
- Les bases de données utilisent des arbres (B-trees) pour indexer les données.
- Les algorithmes de compression (Huffman) utilisent des arbres binaires.
- Les moteurs de jeux vidéo utilisent des arbres pour les scènes (octrees).
Conseils pour le bac NSI
Pour l'épreuve écrite, tu dois être capable de :
- Lire et construire un arbre binaire à partir d'un texte ou d'un schéma.
- Implémenter des parcours en Python.
- Écrire une fonction de recherche dans un ABR.
- Analyser la complexité (O(log n) en moyenne pour un ABR équilibré).
Pour t'entraîner, je te recommande de consulter les exercices NSI et les fiches de révision disponibles sur le site. Tu peux aussi approfondir avec des ressources comme AlloBac ou AlloLycée.
N'oublie pas de t'entraîner sur des sujets d'annales. Le cours NSI en ligne peut aussi t'aider à revoir les bases.
Conclusion
Les arbres binaires sont un pilier de la NSI. Avec un peu de pratique, tu les maîtriseras sans difficulté. Rappelle-toi : un arbre, c'est juste des nœuds avec des enfants, et un ABR ajoute une règle d'ordre qui rend la recherche super efficace. Alors lance-toi, code, et décroche ton bac !
