
voici un exemple (une erreur en fait) intéressant que nous avons rencontré
on définit 1 arbre binaire de recherche (ABR – voir figure ci-dessus) par une classe Nœud
class Noeud:
def __init__(self, v, l, r):
"""initialisation des attributs"""
self.value = v
self.left = l
self.right = r
on veut maintenant développer une fonction appartient(x, a) pour savoir si l’élément x appartient à l’arbre a ; 2 possibilités :
- méthode 1 : définition directe d’une fonction (externe à la classe)
- méthode 2 : définition d’une méthode associée à l’objet (on en profite pour créer une nouvelle classe ABR par héritage
fonction (externe) appartient 🥴
rien de neuf sous le soleil ; par exemple, directement inspiré du site Terminale-NSI.fr :
def appartient(x, a):
"""détermine si x apparaît dans l'ABR a"""
if a is None:
return False
if x < a.valeur:
return appartient(x, a.gauche)
elif x > a.valeur:
return appartient(x, a.droit)
else:
return True
petit problème avec la méthode appartient dans la sous-classe ABR 👽
nous avons d’abord essayé le programme suivant, qui ne marche pas :
class Noeud:
"""un noeud d'un arbre binaire"""
def __init__(self, g, v, d):
self.gauche = g
self.valeur = v
self.droit = d
class ABR(Noeud):
"""un noeud d'un arbre binaire de recherche"""
def appartient(self, x):
"""détermine si x apparaît dans l'ABR a"""
if self is None:
return False
if x < self.valeur:
return self.gauche.appartient(x)
elif x > self.valeur:
return self.droit.appartient(x)
else:
return True
pourquoi cela ne marche pas … une petite recherche nous a finalement permis de mettre le doigt dessus !
précédemment, lors de la récurrence, nous utilisions sur None la fonction appartient (parfait) mais maintenant nous demandons à None (qui n’est pas de la classe ABR) d’exploiter la méthode appartient (impossible car None n’est de la classe ABR et ne dispose donc pas de cette méthode)
on résout ce petit problème qui nous à pris un peu de temps à être identifié par un simple test if else !
et voilà une méthode qui marche (à optimiser bien-sûr) 👏
class Noeud:
"""un noeud d'un arbre binaire"""
def __init__(self, g, v, d):
self.gauche = g
self.valeur = v
self.droit = d
class ABR(Noeud):
"""un noeud d'un arbre binaire de recherche"""
def appartient(self, x):
"""détermine si x apparaît dans l'ABR a"""
if self is None:
return False
elif x < self.valeur:
if self.gauche is None:
return False
else:
return self.gauche.appartient(x)
elif x > self.valeur:
if self.droit is None:
return False
else:
return self.droit.appartient(x)
else:
return True
mon_arbre = ABR(ABR(ABR(None,1,None),3,ABR(ABR(None,4,None),6,ABR(None,7,None))),8,ABR(None,10,ABR(ABR(None,13,None),14,None)))
print(mon_arbre.appartient(17))

à bientôt, math13net
Poster un Commentaire