Parcours d'un arbre
On décide de prendre l'implémentation des arbre donné 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)
def ajout_droit(self,val):
self.fd=Arbre(val)
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
else :
return 1+max(Arbre.hauteur(self.fg),Arbre.hauteur(self.fd))
def get_valeur(self):
if self==None:
return None
else:
return print(self.v)
Prise en main de l'implémentation
-
Implémenter cet arbre :
- Tester les différentes méthodes sur cet arbre.
Parcours en profondeur : infixe, préfixe et suffixe
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 algorithme de recherche textuelle par exemple ou à gérer des "AI" de jeux vidéos.
Parcours préfixe
Dans ce parcours 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.
voila la méthode écrite en Python du parcours préfixe d'un arbre de recherche:
def dfs_prefixe(self):
if self==None:
return None
else :
Arbre.get_valeur(self)
Arbre.dfs_prefixe(self.fg)
Arbre.dfs_prefixe(self.fd)
Parcours infixe
Dans ce parcours 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 :
Ecrire l'algorithme du parcours infixe.
Parcours suffixe
Dans ce parcours 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 :
Ecrire l'algorithme du parcours suffixe.
Parcours en largeur d'abord
Dans cette partie, nous allons aborder les parcours en largeur.
Ce parcours est parfois noté BPS pour Breadth-First Search.
Parcours en largeur
Quand on parcourt en largeur 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 a pour attribut : le precedent , 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): #methode qui permet de lance un print sur un tel objet
return str(self.val)+"-"+str(self.suivant)l'objet file :
class File:
#ici une file est la donnée de deux attributs : la file complète de type Element et le dernier élément de la file de type Element
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 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 BFT
def BFT(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 lTester l'algorithme sur cet arbre :
Algorithmes des arbres binaires de recherche
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 :
Recherche d'une clé
Ecrire 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.
Insérer une clé
La méthode qui insère un élément dans un arbre binaire de recherche est déjà écrite. Quel est-elle?
Commenter cette méthode.
Exercices
Ecrire une méthode min(self) qui renvoie la clé minimale d'un arbre.
Ecrire une méthode max(self) qui renvoie la clé maximale d'un arbre.
Donner tous les arbres binaires de recherche formés des trois nœuds : 7, 52, 40
Ecrire une méthode 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.