Dans cette feuille, nous allons implémenter la structure d'arbre binaire en python à l'aide la programmtion objet.
Voici les opérations de base qui seront définies :
Même s'il est possible que des noeuds aient la même valeur, on supposera ici, des raisons de simplification, que les valeurs de tous les noeuds d'un arbre considéré sont distinctes deux à deux.
Il y a de nombreuses façons de représenter un arbre binaire en python.
Une façon traditionnelle consiste à représenter chaque noeud par un objet d'une classe appelée Noeud
. Un objet de cette classe contient trois attributs initialisés par le constructeur :
gauche
pour le sous-arbre gauche.valeur
pour la valeur contenue dans le noeud.droite
pour le sous-arbre droit.L'arbre vide est représenté par la valeur None
.
Comme pour les listes chaînées, on encapsule un arbre binaire dans une classe AB
. Chaque objet de cette classe contient un unique attribut , racine
qui est l'arbre qu'il représente.Le constructeur de cette classe initialise cet attribut avec la valeur None
par défaut (arbre vide).
class Noeud:
'''Classe définissant un noeud d'arbre binaire'''
def __init__(self,gauche,valeur,droite):
self.gauche=gauche
self.valeur=valeur
self.droite=droite
#Ex1
def __str__(self):
'''Renvoie la valeur du noeud (str)'''
pass
class AB:
'''Classe définissant un Arbre Binaire'''
def __init__(self, racine=None):
self.racine=racine
#Ex3
def est_vide(self):
'''renvoie True si et seulement si l'arbre est vide'''
pass
#Ex4
def hauteur(self):
'''renvoie la hauteur de l'arbre'''
pass
#Ex5
def taille(self):
'''renvoie la taille de l'arbre'''
pass
Ecrire la méthode __str__(self)
de la classe Noeud
qui affiche la valeur contenue dans un noeud.
#Afficher la valeur d'un noeud
n1=Noeud(None,42,None)
print(n1)
42
Trouver deux façons de construire l'arbre ci-contre( on ne demande pas de le dessiner):
#méthode 1 :
print(T1.racine)
print(T1.racine.gauche)
print(T1.racine.droite)
1 2 3
#méthode 2 :
print(T1.racine)
print(T1.racine.gauche)
print(T1.racine.droite)
1 2 3
Dans cette partie , nous allons ajouter quelques fonctionnalités sur les arbres binaires. Ces méthodes sont à ajouter dans le code de définition de la classe AB
. De par leur définition , les arbres binaires se prêtent bien à la programmation récursive.
Ecrire la méthode est_vide(self)
qui renvoie True
si l'arbre est vide , False
sinon.
#tests arbre vide
T1=AB(Noeud(Noeud(None,2,None),1,Noeud(None,3,None)))
T2=AB()
assert(T1.est_vide()==False)
assert(T2.est_vide()==True)
Ecrire la méthode hauteur(self)
qui renvoie la hauteur de l'arbre.
Aide :
#tests hauteur
T1=AB(Noeud(Noeud(None,2,None),1,Noeud(None,3,None)))
T2=AB(Noeud(None,1,None))
T3=AB()
assert(T1.hauteur()==2)
assert(T2.hauteur()==1)
assert(T3.hauteur()==0)
Ecrire la méthode taille(self)
qui renvoie la taille de l'arbre.
Aide :
#tests hauteur
T1=AB(Noeud(Noeud(None,2,None),1,Noeud(None,3,None)))
T2=AB(Noeud(None,1,None))
T3=AB()
assert(T1.taille()==3)
assert(T2.taille()==1)
assert(T3.taille()==0)
Ecrire la liste des sommets visités de cet arbre lors d'un parcours en profondeur :
#construction de l'arbre donné en exemple.
A=Noeud(None,'A',None)
E=Noeud(None,'E',None)
U=Noeud(None,'U',None)
I=Noeud(None,'I',None)
O=Noeud(None,'O',None)
Y=Noeud(None,'Y',None)
A.gauche=E
A.droite=U
E.gauche=I
E.droite=O
U.gauche=Y
arbre=AB(A)
Ecrire la fonction profondeur_prefixe(A)
qui affiche les noeuds de l'arbre A
parcouru en profondeur préfixe.
Aide :
def profondeur_prefixe(A):
'''Affiche les noeuds de l'arbre A
parcouru en profondeur préfixe'''
pass
profondeur_prefixe(arbre) # A E I O U Y
A E I O U Y
Ecrire la fonction profondeur_postfixe(A)
qui affiche les noeuds de l'arbre A
parcouru en profondeur postfixe.
Aide :
def profondeur_postfixe(A):
'''Affiche les noeuds de l'arbre A
parcouru en profondeur préfixe'''
pass
profondeur_postfixe(arbre) # I O E Y U A
I O E Y U A
Ecrire la fonction profondeur_infixe(A)
qui affiche les noeuds de l'arbre A
parcouru en profondeur infixe.
Aide :
def profondeur_infixe(A):
'''Affiche les noeuds de l'arbre A
parcouru en profondeur préfixe'''
pass
profondeur_infixe(arbre) # I E O A Y U
I E O A Y U
Il est difficile de visualiser un arbre défini avec les classes et méthodes précédentes. Le but de cet exercice est d'écrire une fonction qui affiche la représentation d'un arbre à l'aide parenthèses ouvrantes et fermantes.
L'arbre ci-contre sera représenté ainsi : ((2)1(3))
PARTIE A :
((B(C))A(D))
PARTIE B :
Ecriture de la fonction affiche(arbre)
qui prend en paramètre un arbre et qui affiche sa représentation.Les tests seront effectués sur l'arbre ci-contre :
affiche
sur cet arbre : (((I)E(O))A((Y)U))
Ecrire ci-dessous la fonction.
def affiche(arbre):
pass
affiche(arbre)
(((I)E(O))A((Y)U))
Un arbre binaire parfait est un arbre binaire dont chaque noeud(sauf les feuilles) possède exactement deux enfants.Toutes les feuilles sont à la même profondeur. Voici un arbre binaire parfait de hauteur 5 :
Ecrire la fonction parfait(h)
qui prend en paramètre la hauteur de l'arbre souhaité et qui renvoie un arbre parfait de hauteur h
.
Aide :
h
vaut $0$, on construit l'arbre vide.h
, et dont les sous-arbres gauche et droite sont des arbres parfaits de hauteur h-1
.h
(récursivement)def parfait(h):
'''Construit un arbre binaire parfait de hauteur h
h : entier >= 0
return : un arbre binaire '''
pass
#tests arbre parfait
A2=parfait(2)
affiche(A2) # ((1)2(1))
((1)2(1))
A4=parfait(4)
affiche(A4) #((((1)2(1))3((1)2(1)))4(((1)2(1))3((1)2(1))))
((((1)2(1))3((1)2(1)))4(((1)2(1))3((1)2(1))))
A0=parfait(0)
affiche(A0) #rien !