None, méthode et récursivité

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