graph TD
A((A)) --- B((B))
A --- C((C))
B --- D((D))
B --- E((E))
Ch. 5 - Arbres : Cours - Partie 2 - Implémentation des Arbres Binaires en Python
1. Choix de l’implémentation
Pour implémenter un arbre binaire en Python, la méthode la plus standard et la plus “propre” scientifiquement consiste à définir une classe pour les Nœuds.
Un Arbre Binaire est alors simplement :
- Soit
None(l’arbre vide). - Soit une instance de la classe
Noeud(la racine), qui pointe vers deux autres arbres binaires (ses fils).
Cette approche distingue bien la structure récursive et évite de créer des objets “vides” inutiles.
2. La classe Noeud
Voici une implémentation moderne et documentée.
class Noeud:
def __init__(self, etiquette, gauche=None, droit=None):
"""
Crée un nouveau noeud.
Parameters
----------
etiquette : Any
La valeur stockée dans le noeud.
gauche : Noeud, optional
Le sous-arbre gauche (default is None).
droit : Noeud, optional
Le sous-arbre droit (default is None).
"""
self.etiquette = etiquette
self.gauche = gauche
self.droit = droit
def est_feuille(self) -> bool:
"""
Renvoie True si le noeud est une feuille.
Returns
-------
bool
True si le noeud n'a aucun fils, False sinon.
"""
return self.gauche is None and self.droit is NoneConstruction d’un arbre
Pour construire l’arbre suivant :
# Construction de bas en haut (Bottom-Up)
d = Noeud("D")
e = Noeud("E")
b = Noeud("B", d, e)
c = Noeud("C")
a = Noeud("A", b, c)
# L'arbre est représenté par sa racine 'a'
mon_arbre = a3. Fonctions de base sur les arbres
Puisque l’arbre vide est représenté par None, nous ne pouvons pas utiliser de méthodes d’instance (comme arbre.taille()) directement sur un arbre qui pourrait être vide. Nous définissons donc des fonctions qui prennent l’arbre en paramètre.
3.1. Taille et Hauteur
def taille(arbre) -> int:
"""
Calcule la taille de l'arbre (nombre total de noeuds).
Parameters
----------
arbre : Noeud
L'arbre dont on veut calculer la taille.
Returns
-------
int
Le nombre de noeuds de l'arbre.
"""
if arbre is None:
return 0
else:
return 1 + taille(arbre.gauche) + taille(arbre.droit)
def hauteur(arbre) -> int:
"""
Calcule la hauteur de l'arbre.
Convention : Hauteur(vide) = 0, Hauteur(feuille) = 1.
Parameters
----------
arbre : Noeud
L'arbre dont on veut calculer la hauteur.
Returns
-------
int
La hauteur de l'arbre.
"""
if arbre is None:
return 0
else:
return 1 + max(hauteur(arbre.gauche), hauteur(arbre.droit))3.2. Visualisation (Bonus)
Pour visualiser l’arbre, nous pouvons utiliser une fonction récursive qui affiche l’arbre dans la console (tourné à 90°).
def affiche(arbre, niveau=0, prefixe="----"):
"""
Affiche l'arbre dans la console de manière textuelle.
Parameters
----------
arbre : Noeud
L'arbre à afficher.
niveau : int, optional
Le niveau de profondeur actuel (default is 0).
prefixe : str, optional
Le préfixe à afficher avant le noeud (default is "Racine: ").
"""
if arbre is None:
return
# On affiche d'abord le sous-arbre droit (pour qu'il soit en haut)
affiche(arbre.droit, niveau + 1, " /-- ")
# On affiche le noeud courant
print(" " * niveau + prefixe + str(arbre.etiquette))
# On affiche le sous-arbre gauche
affiche(arbre.gauche, niveau + 1, " \\-- ")4. Arbres Binaires de Recherche (ABR)
Pour les ABR, nous pouvons créer une classe spécifique ou simplement utiliser des fonctions d’insertion. Voici une approche fonctionnelle pure (sans modification en place) et une approche avec modification.
Insertion (Version récursive)
def insere_abr(arbre, valeur):
"""
Insère une valeur dans un ABR et renvoie la nouvelle racine.
Si l'arbre est vide, crée un nouveau noeud.
Parameters
----------
arbre : Noeud
L'arbre dans lequel insérer la valeur.
valeur : Any
La valeur à insérer.
Returns
-------
Noeud
La racine de l'arbre après insertion.
"""
if arbre is None:
return Noeud(valeur)
if valeur < arbre.etiquette:
arbre.gauche = insere_abr(arbre.gauche, valeur)
elif valeur > arbre.etiquette:
arbre.droit = insere_abr(arbre.droit, valeur)
# Si valeur == arbre.etiquette, on ne fait rien (pas de doublons)
return arbreExemple d’utilisation :
abr = None
abr = insere_abr(abr, 10)
abr = insere_abr(abr, 5)
abr = insere_abr(abr, 15)
abr = insere_abr(abr, 2)On obtient l’ABR suivant :
graph TD
10((10)) --> 5((5))
10((10)) --> 15((15))
5((5)) --> 2((2))
5((5)) --- invis1( )
style invis1 fill:none,stroke:none
linkStyle 3 stroke-width:0px,markerWidth 3 0,markerHeight 3 0
5. Bonus : visualisation avec Graphviz
def visualise_arbre(arbre):
"""
Visualise l'arbre en utilisant Graphviz.
Parameters
----------
arbre : Noeud
L'arbre à visualiser.
"""
def ajouter_noeud(g, noeud):
if noeud is not None:
g.node(str(id(noeud)), str(noeud.etiquette))
if noeud.gauche is not None:
g.edge(str(id(noeud)), str(id(noeud.gauche)))
ajouter_noeud(g, noeud.gauche)
if noeud.droit is None:
#ajout d'un noeud fantôme pour aligner les branches
fantome = Noeud("")
g.node(str(id(fantome)), "", style="invis")
g.edge(str(id(noeud)), str(id(fantome)), style="invis")
if noeud.droit is not None:
g.edge(str(id(noeud)), str(id(noeud.droit)))
ajouter_noeud(g, noeud.droit)
if noeud.gauche is None:
#ajout d'un noeud fantôme pour aligner les branches
fantome = Noeud("")
g.node(str(id(fantome)), "", style="invis")
g.edge(str(id(noeud)), str(id(fantome)), style="invis")
g = Digraph()
ajouter_noeud(g, arbre)
return g
# Exemple d'utilisation
arbre = insere_abr(None, 10)
arbre = insere_abr(arbre, 5)
arbre = insere_abr(arbre, 15)
arbre = insere_abr(arbre, 2)
g = visualise_arbre(arbre)
g.render('arbre', format='png', view=True)