def taille(arbre):
if arbre is None:
return 0
else:
return 1 + taille(arbre.filsgauche) + taille(arbre.filsdroit)
La première idée est d'écrire :
class ABR(Arbre):
....
def taille(self):
if self is None:
return 0
else:
return 1 + self.filsgauche.taille() + self.filsdroit.taille()
Mais ce code génère alors cette erreur : AttributeError: 'NoneType' object has no attribute 'taille'...
Interprétation : lorsque self est une feuille, alors self.filsgauche ( ou self.filsdroit ) est donc égal à None, à partir duquel on ne peut évidemment pas appeler la
méthode taille...
Ce problème ne se posait pas avec la fonction hauteur, qui est définie "en dehors" de la classe ABR, et "existe" donc toujours,
même si les arbres sont égaux à None...
On peut tout simplement rajouter un paramètre à la méthode, l'équivalent du paramètre arbre de la fonction :
class ABR(Arbre):
....
def taille(self, arbre):
if arbre is None:
return 0
else:
return 1 + self.taille(arbre.filsgauche) + self.taille(arbre.filsdroit)
Lors de l'appel de la méthode, il faudra alors penser à passer l'objet Arbre lui-même en argument :
print(arbre.taille(arbre))
Ce n'est donc pas très élégant...en plus, du point de vue de l'interface, l'utilisateur sait qu'il faut appeler la méthode à partir de l'objet, mais pas qu'il faut aussi le passer en paramètre ! Ce n'est donc pas du tout ergonomique...
On garde le même algorithme dans une méthode "privée" à la classe ( donc qui ne fait pas partie de son interface ), et on utilise une autre méthode "publique" pour l'appeler en
lui passant la racine de l'arbre au premier appel comme paramètre, comme la fonction taille précédente; cette méthode "publique" renverra également le résultat renvoyé
par la méthode "privée" :
class ABR(Arbre):
....
def taille(self): # méthode "publique"
return self._taille(self) # 'self' représente ici la racine de l'arbre
def _taille(self, arbre): # méthode "privée" ( le caractère underscore '_' signale une méthode "privée", qui ne fait donc pas partie de l'interface )
if arbre is None:
return 0
else:
return 1 + self._taille(arbre.filsgauche) + self._taille(arbre.filsdroit)
On appelle alors la méthode "publique", sans avoir besoin de passer l'arbre en paramètre.
On change d'algorithme :
class ABR(Arbre):
...
def taille(self):
nbn = 0
if self.valeur is None: # self est une feuille ?
return 0
else:
if self.filsgauche is not None:
nbn = nbn + self.filsgauche.taille()
if self.filsdroit is not None:
nbn = nbn + self.filsdroit.taille()
return 1 + nbn
...
Remarque : cet algorithme pourrait aussi très bien être implémenté dans une fonction externe à la classe...
def hauteur(arbre):
if arbre is None:
return -1
else:
return 1 + max(hauteur(arbre.filsgauche), hauteur(arbre.filsdroit))
La valeur -1 renvoyée par le cas de base correspond au fait qu'il ne faut pas compter la branche de la feuille lors de la "remontée" dans l'arbre.
class ABR(Arbre):
....
def hauteur(self): # méthode "publique"
return self._hauteur(self) # 'self' représente ici la racine de l'arbre
def _hauteur(self, arbre): # méthode "privée" ( le caractère underscore '_' signale une méthode "privée", qui ne fait donc pas partie de l'interface )
if arbre is None:
return -1
else:
return 1 + max(self._hauteur(arbre.filsgauche), self._hauteur(arbre.filsdroit))
class ABR(Arbre):
...
def hauteur(self):
listeh = []
if self.valeur is None:
return 0
if self.filsgauche is None and self.filsdroit is None : # noeud = feuille
return 0
else:
if self.filsgauche is not None:
listeh.append(self.filsgauche.hauteur())
if self.filsdroit is not None:
listeh.append(self.filsdroit.hauteur())
return max(listeh) + 1
...