NSI Terminale
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)->int:
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 : lorsqu'on arrive à une feuille, ou à un nœud qui n'a qu'un seul fils, self.filsdroit et/ou self.filsgauche sont égaux à None,
à partir duquel on ne peut évidemment pas appeler la méthode taille...
Ce problème ne se posait pas avec la fonction taille, qui est définie "en dehors" de la classe ABR, et "existe" donc toujours,
même si les arbres sont égaux à None...
On peut compléter l'algorithme de calcul de taille présenté dans le cours, en tenant compte de toutes les situations que l'on peut rencontrer :
class ABR(Arbre):
....
def taille(self)->int:
"""Renvoie le nombre de nœuds présents dans un ABR"""
if self.filsdroit is None and self.filsgauche is None: # le noeud est une feuille : cas de base
return 1
elif self.filsdroit is None: # le noeud n'a pas de fils droit,
return 1 + self.filsgauche.taille() # alors l'appel récursif se fait sur le fils gauche ( qui existe forcément, le nœud n'est pas une feuille ! )
elif self.filsgauche is None: # nœud qui n'a pas de fils gauche
return 1 + self.filsdroit.taille()
else:
return 1 + self.filsgauche.taille() + self.filsdroit.taille() # nœud qui a ses deux fils
Mais on perd alors "l'élégance" de la solution à un seul appel récursif !...
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.
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))