Objectifs :
À la fin de cette séquence vous serez capable de :
- Identifier des situations nécessitant une structure de données arborescente.
- Évaluer quelques mesures des arbres binaires (taille, encadrement de la hauteur, etc.)
1. Définitions
Un arbre est appelé arbre binaire si chaque nœud a zéro enfant, un enfant ou deux enfants.
Un arbre binaire peut se définir de manière récursive, ce qui reflète parfaitement sa structure.
Définition récursive :
Un arbre binaire est soit :
- vide,
- soit un nœud contenant une valeur, un sous-arbre gauche et un sous-arbre droit, qui sont eux-mêmes des arbres binaires.
Cette définition permet de créer des fonctions récursives dont la structure imite exactement celle de l’arbre.
Rappel :
- Racine : le nœud au sommet de l’arbre ;
- Sous-arbre : un arbre attaché à un nœud.
- Niveau : c'est l’ensemble de tous les nœuds de même profondeur.
- Hauteur d'un arbre ou profondeur d'un arbre : le nombre total de niveaux de l'arbre.
- Taille d'un arbre : le nombre de nœuds de cet arbre.
- Feuille ou nœud externe : un nœud sans enfant.
2. Opérations de base sur les structures de données abstraites arbres binaires
- est_vide() : Renvoie True si l'arbre AB est vide, False sinon.
- inserer(AB, elt) : insère elt dans AB.
- supprimer(AB, elt) : efface elt dans AB.
- rechercher(AB, elt) : Renvoie True si elt est présent dans AB, False sinon.
- Parcourir un arbre.
Quelques opérations auxilliaires
- Trouver la taille de l'arbre ;
- Trouver la hauteur de l'arbre ;
- Trouver le niveau qui a la plus grande somme
3. Parcourir un arbre
Afin de traiter les arbres, on a besoin de visiter ses différents nœuds.
Le processus de visite de tous les nœuds d'un arbre est appelé parcours d'arbre. Chaque nœud n'est traité qu'une seule fois mais il peut être visité plus d'une fois.
3.1. Parcourir un arbre en profondeur d'abord
3.1.1. Parcours préfixe (on dit aussi préordre)
Le parcours s'effectue comme suit :
- on visite d'abord la racine ;
- puis on parcourt le sous-arbre gauche en préfixe ;
- et enfin, on parcourt le sous-arbre droit en préfixe.
L'algorithme du parcours préfixe
Fonction parcours_prefixe(AB)
"""
Entrée : AB est un arbre binaire ;
Sortie : Tous les nœuds de l'arbre ont été visités en préfixe.
"""
Si AB est vide :
retourner
Sinon :
traiter la racine de AB
parcours_prefixe(AB.gauche)
parcours_prefixe(AB.droit)
FinSi
FinFonction
Exemple :
Ce qui donne : 23 → 14 → 7 → 9 → 17 → 31
3.1.2. Parcours postfixe (on dit aussi postordre)
Le parcours s'effectue comme suit :
- on parcourt d'abord le sous-arbre gauche en postfixe ;
- puis, on parcourt le sous-arbre droit en postfixe.
- enfin, on visite la racine ;
3.1.3. Parcours infixe (on dit aussi en ordre)
Le parcours s'effectue comme suit :
on visite
- on parcourt d'abord, en infixe, le sous-arbre gauche ;
- puis, on visite la racine ;
- enfin, on parcourt, en infixe, le sous-arbre droit.
3.2. Parcourir un arbre en largeur d'abord
Parcourir un arbre en largeur d'abord revient à parcourir un arbre niveau par niveau.
- on visite la racine (niveau 0),
- puis tous les nœuds de niveau 1,
- puis tous les nœuds de niveau 2,
- etc.
Pour réaliser ce parcours, on utilise une file : elle permet de traiter les nœuds dans l’ordre où ils apparaissent dans l’arbre.
Fonction parcours_en_largeur(AB)
"""
Entrée : AB est un arbre binaire ;
Sortie : Tous les nœuds de AB ont été visités en largeur d'abord.
"""
Si AB est vide :
retourner
F ← file vide
enfiler(F, AB)
Tant que F n'est pas vide :
N ← défiler(F)
traiter N.valeur
Si N.gauche n'est pas vide :
enfiler(F, N.gauche)
Si N.droit n'est pas vide :
enfiler(F, N.droit)
Fin Tant que
Fin Fonction
Exemple :
Ce qui donne : 23 → 14 → 31 → 7 → 17 → 9
3.5. Déterminer la taille d'un arbre binaire
Calculez la taille des sous-arbres gauche et droit de manière récursive, ajoutez 1 (nœud racine).
L'algorithme de détermination de la taille d'un arbre
Fonction taille_recursive(AB)
"""
Entrée : AB est un arbre binaire ;
Sortie : Renvoie le nombre de nœuds de AB.
"""
Si AB est vide :
renvoyer 0
Sinon :
renvoyer 1
+ taille_recursive(AB.gauche)
+ taille_recursive(AB.droit)
FinFonction
4. Une implantation d'un arbre binaire à l'aide de nœuds liés
4.1. Une implémentation
class Noeud:
"""Modélise un nœud d'un arbre binaire."""
def __init__(self, valeur, gauche = None, droit = None):
self.cle = valeur
self.gauche = gauche
self.droit = droit
#Afficher le noeud
def __str__(self):
"""Affiche la valeur du nœud."""
return f"{self.valeur}"
def __repr__(self):
"""représentation détaillée du nœud."""
return f"Noeud({repr(self.valeur)}, {repr(self.gauche)}, {repr(self.droit)})"
class ArbreBinaire:
"""Représente un arbre binaire."""
def __init__(self, racine=None):
"""racine est un noeud ou None"""
self.racine = racine
#Afficher l'AB
def __repr__(self):
"""Affiche l'arbre binaire."""
return f"ArbreBinaire({repr(self.racine)})"
def est_vide(self):
"""Renvoie True si l'AB est vide, False sinon."""
...
def get_droit(self):
"""Renvoie l'AB droit."""
...
def get_gauche(self):
"""Renvoie l'AB gauche."""
...
4.2. Créer une instance d'ArbreBinaire
noeud7 = Noeud(7)
noeud9 = Noeud(9)
noeud14 = Noeud(14)
noeud17 = Noeud(17)
noeud23 = Noeud(23)
noeud31 = Noeud(31)
noeud23.gauche = noeud14
noeud23.droit = noeud31
noeud14.gauche = noeud7
noeud14.droit = noeud17
noeud7.droit = noeud9
mon_AB = ArbreBinaire(noeud23)
Faites-vous plaisir 1 :
- Créer l'arbre binaire un_AB, donné ci-dessus.
-
Compléter les méthodes d'arbre binaire get_droit et get_gauche de la structure de données abstraite arbre binaire.
Tester vos méthodes avec l'instance mon_AB. - En utlisant l'algorithme du parcours préfixé, écrire en langage Python puis l'insérer dans la classe ArbreBinaire, la méthode affiche_prefixe qui affiche les clés de l'AB.
- En déduire les méthodes affiche_postfixe et affiche_infixe.
- En vous inspirant de la méthode taille_recursive, écrire, en Python, la méthode somme_recursive qui renvoie la somme des valeurs de l'arbre binaire.
- En vous inspirant de la méthode taille_recursive, écrire, en Python, la méthode hauteur_recursive qui renvoie le nombre de niveau de l'arbre binaire.
- Traduire, en langage Python, la méthode parcours_largeur dont l'algorithme est donné ci-dessus.
4.2. Un nœud est considéré comme un arbre binaire
#un noeud est considéré comme un arbre binaire
class AB:
"""Représente un arbre binaire."""
def __init__(self, valeur, gauche = None, droit = None):
self.valeur = valeur
self.gauche = gauche
self.droit = droit
#Afficher l'arbre
def __repr__(self):
"""Affiche l'AB."""
return f"AB({repr(self.valeur)}, {repr(self.gauche)}, {repr(self.droit)})"
def get_gauche(self):
"""Renvoie le sous-arbre gauche (AB ou None)."""
...
def set_gauche(self, nouveau_sous_arbre):
"""Modifie le sous-arbre gauche."""
...
def set_valeur(self, nouvelle_valeur):
"""Modifie la valeur du nœud."""
...
def est_feuille(self):
"""Renvoie True si le nœud n'a aucun sous-arbre."""
...
5. Une autre implantation d'un arbre binaire à l'aide de fonctions et listes imbriquées
def cree_arbre_binaire(cle, gauche=None, droite=None):
"""
Renvoie un arbre binaire représenté par une liste de 3 éléments :
[cle, sous_arbre_gauche, sous_arbre_droit]
Un arbre vide est représenté par [].
"""
if gauche is None:
gauche = []
if droite is None:
droite = []
return [cle, gauche, droite]
# Tester si un arbre est vide
def est_vide(AB):
return AB == [] or AB is None
6. Une implantation d'un arbre binaire à l'aide de fonctions et dictionnaires imbriqués
def cree_arbre_binaire(cle:any, gauche:[dict|None]=None, droit:[dict|None]=None):
"""
Crée un arbre binaire avec une racine donnée et des sous-arbres gauche et droit.
"""
return {"clé": cle, "gauche": gauche, "droit": droit}
def est_vide(AB):
return AB is None
7. Une application des arbres binaires : Arbres d'expression
Une expression est une suite de symboles qui suivent des règles données. Un symbole peut être soit un opérande, soit un opérateur. On considère, ici, uniquement les opérateurs arithmétiques binaires sous la forme opérande-opérateur-opérande. Les opérateurs arithmétiques standard sont +, -, × et /.
Un arbre d'expression est un arbre binaire avec les propriétés suivantes :
- Chaque feuille est un opérande.
- Les nœuds racine et interne sont des opérateurs.
- Les sous-arbres sont des sous-expressions, la racine étant un opérateur.
Exemple : a × (b + c) + d
