On décide de prendre l'implémentation des arbres donnée ci-dessous :
class Arbre:
def __init__(self, valeur):
self.v = valeur
self.fg = None
self.fd = None
def ajout_gauche(self, val):
self.fg = Arbre(val)
return self
def ajout_droit(self, val):
self.fd = Arbre(val)
return self
def affiche(self):
"""permet d'afficher un arbre"""
if self == None:
return None
else :
return [self.v, Arbre.affiche(self.fg), Arbre.affiche(self.fd)]
def taille(self):
if self == None:
return 0
else :
return 1 + Arbre.taille(self.fg) + Arbre.taille(self.fd)
def hauteur(self):
if self == None:
return 0
elif self.fg == None and self.fd == None:
return 0
else :
return 1 + max(Arbre.hauteur(self.fg), Arbre.hauteur(self.fd))
def get_valeur(self):
if self == None:
return None
else:
return self.v
Prise en main de l'implémentation
Implémenter cet arbre :
Dans cette partie, nous allons aborder les parcours en profondeur. Il existe trois manières de parcourir un arbre en profondeur comme nous allons le voir. L'idée de ces parcours, c'est de descendre tout en bas de l'arbre avant de se déplacer vers la droite de l'arbre.
Ces parcours sont parfois notés DPS pour Depth-First Search.
Ces parcours serviront à réaliser des algorithmes de recherche textuelle par exemple ou à gérer des "AI" de jeux vidéos.
Parcours préfixe
Dans le parcours préfixe, on note tous les nœuds en commençant par la racine puis les deux sous arbres.
Réaliser à la main le parcours préfixe de cet arbre :
Algorithme du parcours préfixe.
Voilà la méthode écrite en Python du parcours préfixe d'un arbre.
Cette méthode fait partie de la classe Arbre
(comme le prouve le début
des trois dernières lignes).
Comme les arbres ont une structure récursive, il est plus simple de l'écrire en récursif :
def dfs_prefixe(self):
if self == None:
return None
else :
Arbre.get_valeur(self) # D'abord la racine : racine en "pre"mier dans le parcours "pré"fixe
Arbre.dfs_prefixe(self.fg) # Appel récursif sous forme de fonction de la classe Arbre
Arbre.dfs_prefixe(self.fd)
Les explications :
Parcours infixe
Dans le parcours infixe, on note tous les nœuds en commençant par le sous arbre gauche puis la racine puis le sous arbre droit.
Réaliser à la main le parcours infixe de cet arbre :
Écrire l'algorithme du parcours infixe.
Parcours suffixe
Dans le parcours suffixe, on note tous les nœuds en commençant par le sous arbre gauche puis le sous arbre droit et enfin la racine .
Réaliser à la main le parcours suffixe de cet arbre :
Écrire l'algorithme du parcours suffixe.
Pour retenir le nom différent entre ces trois parcours, il suffit de retenir la position de la racine dans chaque des parcours :
"préfixe" : la racine est avant ses sous-arbres ; "pré" comme précéder.
"infixe" : la racine est entre ses sous-arbres ; "in" comme intérieur.
"suffixe" : la racine est après ses sous-arbres ; "su" comme succéder.
Dans cette partie, nous allons aborder les parcours en largeur.
Ce parcours est parfois noté BFS pour Breadth-First Search.
Parcours en largeur
Lors d'un parcours en largeur d'un arbre, on note chaque sommet niveau par niveau et en commençant par la gauche.
le parcours en largeur de cet arbre :
est : 8-5-7-9-3-5-1
On reprend l'implémentation de file vu dans SD3
class Element:
#chaque élément (d'une liste doublement chaînée) a pour attribut : le précédent , le suivant et la valeur de l'élément
def __init__(self, x):
self.val = x
self.precedent = None
self.suivant = None
def __str__(self): # méthode qui permet d\'afficher un tel objet grâce à un print
return str(self.val) + "<-" + str(self.suivant)
l'objet file :
class File:
# ici une file est la donnée de deux attributs :
# la queue de la file de type Element et le premier élément de la file (la tête) de type Element
# l'éventuel corps de la file sera progressivement atteinte grâce aux attributs precedent et suivant des objets de la classe Element
# precedent sert à remonter vers la tête, suivant à descendre vers la queue.
def __init__(self):
self.tete = None
self.queue = None
def enfile(self, x):
e = Element(x) # on transforme l'élément à ajouter en un objet Element de listes doublement Chainées
if self.tete == None:
self.tete = e # file initiale vide : la tete est remplacée par l'élément e
else:
e.precedent = self.queue # le précédent de l'élément pointe sur l'ancienne queue de la file
self.queue.suivant = e # l'ancienne queue de la file pointe sur e avec suivant
self.queue = e # on redéfinit self.queue par e.
def file_vide(self):
return self.tete is None #renvoie True si None et False sinon
def defile(self):
if not self.file_vide():
e = self.tete # on stocke l'élément à defiler
if e.suivant is None: # cas où il n'y a qu'un élément
self.tete = None
self.queue = None
else:
self.tete = e.suivant
self.tete.precedent = None
return e.val
def __str__(self):
return str(self.tete)
Algorithme BFS de parcours en largueur
def BFS(arbre):
f = File()
f.enfile(arbre)
l = []
while not f.file_vide():
a = f.defile()
l.append(a.v)
if a.fg != None:
f.enfile(a.fg)
if a.fd != None:
f.enfile(a.fd)
return l
Tester l'algorithme sur cet arbre :
Le précédent algorithme BFS de parcours en largeur consiste à chaque Noeud étudié de noter sa valeur puis de mettre en mémoire le fait qu'il faudra visiter ses enfants après les noeuds qu'il était déjà prévu de visiter : d'où l'utilisation d'une file de mémorisation pour un parcours en largeur.
Voila l'implémentation des arbres binaires de recherche que nous avons vu dans sd4
class ABR:
def __init__(self, valeur, fg=None, fd=None):
self.v = valeur
self.fg = fg
self.fd = fd
def ajoute(self, valeur):
if self == None:
return ABR(valeur, None, None)
elif valeur < self.v:
return ABR(self.v, ABR.ajoute(self.fg, valeur), self.fd)
else:
return ABR(self.v, self.fg, ABR.ajoute(self.fd, valeur))
def affiche(self):
if self == None:
return None
else :
return [self.v, ABR.affiche(self.fg), ABR.affiche(self.fd)]
Implémenter l'arbre suivant :
Écrire la méthode recherche(self, val)
qui renvoie True
si val
est une clé de
l'arbre et False
sinon.
Le principe ici est celui de la dichotomie. On élimine grâce à la structure des arbres binaires de recherche la moitié des nœuds restant à chaque étape.
La méthode qui insère un élément dans un arbre binaire de recherche est déjà écrite. Quelle est-elle ?
Commenter cette méthode.
Écrire une méthode min(self)
qui renvoie la clé minimale d'un arbre binaire de recherche.
Écrire une méthode max(self)
qui renvoie la clé maximale d'un arbre binaire de recherche.
Donner tous les arbres binaires de recherche formés des trois nœuds : 7, 52, 40
Écrire une fonction listeEnArbre(l)
qui en paramètre reçoit une liste d'entiers et qui renvoie
un arbre binaire de recherche contenant les éléments de la liste l
.
Cet exercice reprend la seule question du sujet de bac non traitée dans le sujet déjà commencé dans SD4.
On considère l'arbre binaire de recherche représenté ci-dessous, où val
représente l'entier 16 :
On rappelle qu’un parcours infixe depuis un nœud consiste, dans l’ordre, à faire un parcours
infixe sur le sous arbre-gauche, afficher le nœud puis faire un parcours infixe sur le sous-arbre
droit.
Dans le cas d’un parcours suffixe, on fait un parcours suffixe sur le sous-arbre gauche puis un
parcours suffixe sur le sous-arbre droit, avant d’afficher le nœud.
Donner les valeurs d’affichage des nœuds dans le cas du parcours infixe de l’arbre.
Donner les valeurs d’affichage des nœuds dans le cas du parcours suffixe de l’arbre.
Les différents
auteurs mettent l'ensemble du site à disposition selon les termes de la licence Creative
Commons Attribution - Pas d’Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0
International