🎯 Objectifs de la lecon
- •Définir un arbre binaire et ses propriétés
- •Parcourir un arbre binaire en préfixe, infixe et suffixe
- •Implémenter un arbre binaire en Python
Un arbre binaire est une structure de données hiérarchique fondamentale en informatique. Chaque nœud a au plus deux enfants, appelés gauche et droit. Tu vas apprendre à le définir, le parcourir et l'implémenter en Python.
Définition et propriétés d'un arbre binaire
Un arbre binaire est un ensemble fini de nœuds. Il peut être vide. S'il n'est pas vide, il est composé d'une racine et de deux sous-arbres binaires disjoints : le sous-arbre gauche et le sous-arbre droit.
La racine est le nœud principal, sans parent. Un nœud sans enfant est une feuille. La hauteur d'un arbre est le nombre maximal d'arêtes entre la racine et une feuille. La taille est le nombre total de nœuds.
« Un arbre avec une racine A, un enfant gauche B et un enfant droit C a une hauteur de 1 et une taille de 3. »
Point fort : Tu vois bien la distinction entre hauteur et taille sur un exemple simple.
✔️ A retenir
Un arbre binaire est soit vide, soit un nœud racine avec deux sous-arbres binaires. La hauteur se mesure en arêtes, la taille en nœuds.
Parcours préfixe, infixe et suffixe
Parcourir un arbre binaire, c'est visiter chaque nœud dans un ordre précis. Les trois parcours principaux sont préfixe, infixe et suffixe. Ils se définissent récursivement.
Dans le parcours préfixe, on visite d'abord la racine, puis le sous-arbre gauche, puis le sous-arbre droit. Dans le parcours infixe, on visite le sous-arbre gauche, puis la racine, puis le sous-arbre droit. Dans le parcours suffixe, on visite le sous-arbre gauche, puis le sous-arbre droit, puis la racine.
« Pour un arbre de racine A, enfant gauche B, enfant droit C : préfixe donne A B C, infixe donne B A C, suffixe donne B C A. »
Point fort : L'exemple montre clairement la différence d'ordre entre les trois parcours.
✔️ A retenir
Préfixe : racine, gauche, droit. Infixe : gauche, racine, droit. Suffixe : gauche, droit, racine.
Implémentation d'un arbre binaire en Python
On implémente un arbre binaire avec une classe Noeud. Chaque nœud contient une valeur, un enfant gauche et un enfant droit. Un arbre vide est représenté par None.
La classe Noeud a un constructeur __init__(self, valeur) qui initialise la valeur et met les enfants à None. On ajoute des méthodes pour insérer ou parcourir.
« La classe Noeud se définit ainsi : class Noeud: def __init__(self, v): self.valeur = v; self.gauche = None; self.droit = None. »
Point fort : Tu obtiens une structure simple et récursive, prête à être utilisée.
Pour créer l'arbre de l'exemple précédent (racine A, gauche B, droit C), on écrit : racine = Noeud('A'); racine.gauche = Noeud('B'); racine.droit = Noeud('C').
⚠️ Attention
N'oublie pas que les enfants sont des objets Noeud, pas des chaînes de caractères. Chaque appel à Noeud crée un nouveau nœud.
Implémenter les parcours en Python
Les parcours s'écrivent sous forme de fonctions récursives. Elles prennent un nœud en paramètre et affichent ou retournent les valeurs dans l'ordre souhaité.
Pour le parcours préfixe, on affiche la valeur du nœud, puis on appelle la fonction sur le sous-arbre gauche, puis sur le sous-arbre droit. Pour l'infixe, on appelle d'abord sur le sous-arbre gauche, puis on affiche, puis sur le sous-arbre droit. Pour le suffixe, on appelle sur le sous-arbre gauche, puis sur le sous-arbre droit, puis on affiche.
« Fonction préfixe : def prefixe(noeud): if noeud: print(noeud.valeur); prefixe(noeud.gauche); prefixe(noeud.droit). »
Point fort : La récursivité suit exactement l'ordre du parcours, c'est simple à retenir.
✔️ A retenir
Chaque parcours est une fonction récursive qui vérifie d'abord si le nœud n'est pas None, puis applique l'ordre : affichage et appels récursifs.
Erreurs fréquentes
Une erreur courante est d'oublier le cas de base : si le nœud est None, la fonction doit s'arrêter. Sans cela, tu obtiendras une erreur de récursion infinie.
Autre erreur : confondre les ordres de parcours. Par exemple, écrire un parcours infixe en affichant la racine en premier, ce qui donne un parcours préfixe.
⚠️ Attention
Vérifie toujours que tu appelles la fonction sur les enfants après avoir traité la racine dans l'ordre correct. Un simple décalage change tout le parcours.
Mini-quiz
Question 1 : Quel est l'ordre du parcours infixe ? Réponse : sous-arbre gauche, racine, sous-arbre droit.
Question 2 : Quelle est la hauteur d'un arbre binaire composé uniquement d'une racine ? Réponse : 0 (aucune arête).
Question 3 : En Python, comment représente-t-on un arbre vide ? Réponse : par None.
