Parcourir un arbre, c’est ordonner la liste des noeuds et feuilles de celui-ci en vue d’effectuer un certain
traitement (par exemple imprimer la liste des étiquettes de cet arbre). On distingue au moins 4 types de parcours :
Le parcours préfixe (parcours en profondeur)
Le parcours suffixe (parcours en profondeur)
Le parcours infixe (parcours en profondeur)
Le parcours hiérarchique(parcours en largeur)
Arbre T
Ballade autour de l'arbre
On se balade autour de l’arbre en suivant les pointillés dans l’ordre des numéros indiqués :
Première définition des trois parcours
Arbre T
A partir de ce contour, on définit trois parcours des sommets de l’arbre :
l’ordre préfixe : on liste chaque sommet la première fois qu’on le rencontre dans la balade.
l’ordre suffixe : on liste chaque sommet la dernière fois qu’on le rencontre.
l’ordre infixe : on liste chaque sommet ayant un fils gauche la seconde fois qu’on le voit et chaque sommet sans fils gauche la première fois qu’on le voit.
Pour tester les différents parcours, nous allons utiliser la classe Noeud et la classe Arbrebin vu au précédant chapitre et le module Digraph en ligne pour vérifier et visualiser les résultats.
from graphviz import Digraph
class Noeud():
"""Représente un noeud dans un arbre binaire
- Propriétés :
* valeur : valeur du noeud
* gauche : noeud gauche ou None
* droit : noeud droit ou None
- Méthodes :
* est_feuille() : renvoie True ou False
* cree_fils_gauche(valeur) : ajoute un fils de valeur valeur
* cree_fils_droit(valeur) : ajoute un fils de valeur valeur
* __repr__() : affichage d'un noeud
* insere(cle) : insere un noeud avec la valeur cle"""
def __repr__(self):
"""la méthode __repr__ définit ce qui sera affiché
lorsqu'on tapera l'objet dans Jupyter ou un terminal
Ici, on affiche juste la valeur du noeud"""
return str(f"## {self.valeur} ##")
def __init__(self,valeur):
self.valeur = valeur
self.gauche = None
self.droit = None
def est_feuille(self):
return self.gauche == None and self.droit == None
def cree_fils_gauche(self,valeur):
self.gauche = Noeud(valeur)
return self.gauche
def cree_fils_droit(self,valeur):
self.droit = Noeud(valeur)
return self.droit
def insere(self, cle):
if cle < self.valeur :
if self.gauche == None :
self.gauche = Noeud(cle)
else :
self.gauche.insere(cle)
elif cle > self.valeur :
if self.droit == None :
self.droit = Noeud(cle)
else :
self.droit.insere(cle)
class Arbrebin:
"""Représente un objet arbre binaire
- Propriétés :
* racine : objet de type Noeud désignant la racine de l'arbre
- Méthodes :
* show() : Représentation graphique de l'arbre à l'aide de graphviz
* taille() : Renvoie la taille d'un arbre
* hauteur(): Renvoie la hauteur d'un arbre
"""
def __init__(self, nd = None):
# Initialise l'arbre à vide par défaut, sinon avec un noeud passé en paramètre otionnel
self.racine = nd
def importe(self, tableau):
"""Importe un arbre depuis un tableau
["Noeud", [S_A_G], [S_A_D]]
[ ] désigne un arbre vide"""
def importe_tableau(tableau):
# Cas particuliers
if tableau == []:
return None
if len(tableau) == 1:
return Noeud(tableau[0])
# tableau a une longueur >= 2
nd = Noeud(tableau[0])
nd.gauche = importe_tableau(tableau[1])
nd.droit = importe_tableau(tableau[2]) if len(tableau) > 2 else None
return nd
self.racine = importe_tableau(tableau)
def show(self):
"""Renvoie un objet graphviz pour la visualisation graphique de l'arbre"""
def representation(dot, noeud):
# Ajoute la représentation du noeud à la représentation dot de l'arbre
if noeud is not None:
dot.node(str(id(noeud)), str(noeud.valeur))
# Appel récursif de la fonction representation
if noeud.gauche is not None:
dot.edge(str(id(noeud)), str(id(noeud.gauche)), label='gauche')
representation(dot, noeud.gauche)
if noeud.droit is not None:
dot.edge(str(id(noeud)), str(id(noeud.droit)), label='droit')
representation(dot, noeud.droit)
dot = Digraph(comment="Arbre binaire", format='svg')
dot.attr('node', shape='circle') # Définit la forme des nœuds
dot.attr('edge', arrowhead='vee') # Définit le style des flèches
dot.attr(rankdir='TB') # Orientation de haut en bas
representation(dot, self.racine)
return dot
def taille(self):
"""Renvoie la taille de l'arbre"""
def taille_arbre(nd):
# condition d'arrêt
if nd is None:
return 0
# Appel récursif
return 1 + taille_arbre(nd.gauche) + taille_arbre(nd.droit)
return taille_arbre(self.racine)
def hauteur(self):
"""Renvoie la hauteur de l'arbre"""
def hauteur_arbre(nd):
# condition d'arrêt
if nd is None:
return 0
# Appel récursif
return 1 + max(hauteur_arbre(nd.gauche) , hauteur_arbre(nd.droit))
return hauteur_arbre(self.racine)
def parcours_prefixe(self):
"""Renvoie la liste des noeuds dans un parcours Prefixe"""
def prefixe(noeud):
# Condition d'arrêt
if noeud is None:
return []
# Appel récursif et renvoi réponse
# La valeur est insérée AVANT les appels
return [noeud.valeur] + prefixe(noeud.gauche) + prefixe(noeud.droit)
return prefixe(self.racine)
Le parcours préfixe
Le parcours préfixe consiste à parcourir l’arbre suivant l’ordre : inspection -→ fils g -→ fils d . On descend de la racine vers une feuille, puis on remonte à la racine, plusieurs fois, afin de passer par tous les noeuds de l’arbre. Dans l’exemple qui suit, il correspond au parcours de l’arbre suivant l’ordre A - B - D - E - C - F - G :
Arbre T
VARIABLE
T : arbre
x : noeud
DEBUT
PARCOURS-PREFIXE(T) :
si T ≠ NIL :
x ← T.racine
affiche x.clé
PARCOURS-PREFIXE(x.gauche)
PARCOURS-PREFIXE(x.droit)
fin si
FIN
Entraînement 1 :
A partir du code précédent, implémenter l'arbre ABCDEFG et tester la méthode parcours_prefixe().
Dans ce mode de parcours, le noeud courant est traité après le traitement des noeuds gauche et droit. Soit parcourir l’arbre suivant l’ordre : fils g. −→ fils d. −→ Inspection. Ainsi, si l'arbre précédent est utilisé, le parcours sera D, E, B, F, G, C, A.
Arbre T
VARIABLE
T : arbre
x : noeud
DEBUT
PARCOURS-SUFFIXE(T) :
si T ≠ NIL :
x ← T.racine
PARCOURS-SUFFIXE(x.gauche)
PARCOURS-SUFFIXE(x.droit)
affiche x.clé
fin si
FIN
Entraînement 2 :
A partir de l'algorithme précédent, implémenter une méthode pour un parcours suffixe d'un arbre binaire et vérifier vos résultats.
Le parcours infixe (ou parcours symétrique) consiste à parcourir l’arbre suivant l’ordre : fils g. −→ Inspection −→ fils d. Le noeud courant est traité entre le traitement des fils gauche et droit. Dans l’exemple précédent, le parcours sera D - B - E - A - F - C puis G.
Arbre T
VARIABLE
T : arbre
x : noeud
DEBUT
PARCOURS-INFIXE(T) :
si T ≠ NIL :
x ← T.racine
PARCOURS-INFIXE(x.gauche)
affiche x.clé
PARCOURS-INFIXE(x.droit)
fin si
FIN
Entraînement 3 :
A partir de l'algorithme précédent, implémenter une méthode pour un parcours infixe d'un arbre binaire et vérifier vos résultats.
Le parcours en largeur correspond à un parcours par niveau de noeuds de l'arbre et en général de la gauche vers la droite pour une profondeur donnée. Un niveau est un ensemble de noeuds ou de feuilles situés à la même profondeur.
Ainsi, si l'arbre de l'exemple est utilisé, le parcours sera A - B - C - D - E - F - G.
Arbre T
VARIABLE
T : arbre
Tg : arbre
Td : arbre
x : noeud
f : file (initialement vide)
DEBUT
PARCOURS-LARGEUR(T) :
enfiler(T.racine, f) //on place la racine dans la file
tant que f non vide :
x ← defiler(f)
affiche x.clé
si x.gauche ≠ NIL :
Tg ← x.gauche
enfiler(Tg.racine, f)
fin si
si x.droit ≠ NIL :
Td ← x.droite
enfiler(Td.racine, f)
fin si
fin tant que
FIN
Cet algorithme n'utilise pas de fonction récursive mais une file (FIFO) pour le parcours en largeur.
Entraînement 4 :
A partir de l'algorithme précédent, implémenter une méthode pour un parcours en largeur d'un arbre binaire.
Un arbre binaire de recherche (ABR) est un arbre binaire dans lequel chaque noeud possède une
étiquette, telle que chaque noeud du sous-arbre gauche ait une étiquette inférieure ou égale à celle du
noeud considéré, et que chaque noeud du sous-arbre droit possède une étiquette supérieure ou égale à
celle-ci.
Exemples
L'arbre 3 n'est pas un ABR à cause de la feuille 9, qui fait partie du sous-arbre gauche de 8 sans lui être inférieure.
L'arbre 4 n'est pas un ABR à cause de la feuille 32, qui fait partie du sous-arbre gauche de 30 sans lui être inférieure.
Entraînement 6 :
Arbre T
Vérifiez que l'arbre ci-dessus est bien un arbre binaire de recherche.
Appliquez l'algorithme de parcours infixe sur l'arbre ci-dessous. Que remarquez vous ?
Un parcours en profondeur infixe donne les nombres par ordre croissant.
Masquer
Pour la suite, nous ajouterons une classe ABR pour les arbres binaires de recherche qui héritera des méthodes des classes Noeud et Arbrebin.
class Abr(Arbrebin):
"""Arbre Binaire de Recherche
Hérite de la classe Arbre binaire
- Propriétés :
* racine : valeur du noeud
- Méthodes :
* insere : insère un noeud à la bonne place"""
def __init__(self):
"""A l'initialisation, notre arbre est vide"""
self.racine = None
def insere(self, cle):
"""Insere un noeud de valeur cle
@param :
cle : étiquette du noeud
"""
self.racine.insere(cle)
Ajouter aussi la méthode insere à la classe Noeud.
Insertion d'une clé dans un arbre binaire de recherche
L'insertion d'un noeud commence par une recherche : on cherche l'étiquette du noeud à insérer. Si
on la trouve, on ne fait rien. Sinon, lorsqu'on ne peut plus descendre dans l'arbre, cela signifie qu'on a
trouvé le père. On insère le noeud en comparant son étiquette à celle de son père : si elle est
inférieure, le nouveau noeud sera son fils gauche ; sinon il sera son fils droit. Ainsi, chaque noeud
ajouté sera une feuille.
La complexité de l'insertion est O(log(n)) dans le cas moyen et O(n) dans le pire des cas.
Entraînement 7 :
Étudier la classe Abr et tester ce programme en insérant les noeuds pour créer l'instance arbre_T de l'exemple précédent.
La recherche dans un arbre binaire d'un noeud ayant une étiquette particulière est un procédé
récursif. On commence par examiner la racine. Si l'étiquette de la racine est l'étiquette recherchée,
l'algorithme se termine et renvoie la racine. Si l'étiquette cherchée est inférieure, alors elle est dans le
sous-arbre gauche, sur lequel on effectue alors récursivement la recherche. De même, si l'étiquette
recherchée est strictement supérieure à l'étiquette de la racine, la recherche continue sur le sous-arbre
droit. Si on atteint une feuille dont l'étiquette n'est pas celle recherchée, on sait alors que cette
étiquette n'est pas dans l'arbre.
Cette opération requiert un temps en O(log(n)) dans le cas moyen, mais O(n) dans le pire des cas
où l'arbre est complètement déséquilibré où chaque père a un seul fil
Entraînement 8 :
Implémenter une méthode permettant de rechercher une clé de valeur k dans un arbre binaire de recherche. Si k est bien présent dans l'arbre binaire de recherche, la méthode renvoie vrai, dans le cas contraire, elle renvoie faux
VARIABLE
T : arbre
x : noeud
k : entier
DEBUT
ARBRE-RECHERCHE(T,k) :
si T == NIL :
renvoyer faux
fin si
x ← T.racine
si k == x.clé :
renvoyer vrai
fin si
si k < x.clé :
ARBRE-RECHERCHE(x.gauche,k)
sinon :
ARBRE-RECHERCHE(x.droit,k)
fin si
FIN
Le parcours préfixe consiste à parcourir l’arbre suivant l’ordre : inspection -→ fils g -→ fils d . On descend de la racine vers une feuille, puis on remonte à la racine, plusieurs fois, afin de passer par tous les noeuds de l’arbre. Dans l’exemple qui suit, il correspond au parcours de l’arbre suivant l’ordre A - B - D - E - C - F - G : Dans l’ordre préfixe : on liste chaque sommet la première fois qu’on le rencontre dans la balade.
Le parcours suffixe consiste a traité le noeud courant après le traitement des noeuds gauche et droit. Soit parcourir l’arbre suivant l’ordre : fils g. −→ fils d. −→ Inspection. Ainsi, si l'arbre précédent est utilisé, le parcours sera D, E, B, F, G, C, A. Dans l’ordre suffixe : on liste chaque sommet la dernière fois qu’on le rencontre.
Le parcours infixe (ou parcours symétrique) consiste à parcourir l’arbre suivant l’ordre : fils g. −→ Inspection −→ fils d. Le noeud courant est traité entre le traitement des fils gauche et droit. Dans l’exemple précédent, le parcours sera D - B - E - A - F - C puis G.
Dans l’ordre infixe : on liste chaque sommet ayant un fils gauche la seconde fois qu’on le voit et chaque sommet sans fils gauche la première fois qu’on le voit.
Le parcours en largeur correspond à un parcours par niveau de noeuds de l'arbre et en général de la gauche vers la droite pour une profondeur donnée. Un niveau est un ensemble de noeuds ou de feuilles situés à la même profondeur.
Ainsi, si l'arbre de l'exemple est utilisé, le parcours sera A - B - C - D - E - F - G.
Les arbres binaires
Un arbre binaire est composé de nœuds, chacun des nœuds possédant éventuellement un sous-arbre gauche et éventuellement un sous-arbre droit. Un nœud sans sous-arbre est appelé feuille. La taille d’un arbre est le nombre de nœuds qu’il contient ; sa hauteur est le nombre de nœuds du plus long chemin qui joint le nœud racine à l’une des feuilles. Ainsi la hauteur d’un arbre réduit à un nœud, c’est-à-dire la racine, est 1.
Dans un arbre binaire de recherche, chaque nœud contient une clé, ici un nombre entier,
qui est :
strictement supérieure à toutes les clés des nœuds du sous-arbre gauche ;
strictement inférieure à toutes les clés des nœuds du sous-arbre droit.
Ainsi les clés de cet arbre sont toutes distinctes.
Un arbre binaire de recherche est dit « bien construit » s’il n’existe pas d’arbre de hauteur
inférieure qui pourrait contenir tous ses nœuds.
