taille récursive d'un arbre binaire (2)
Un arbre binaire est soit vide, représenté en Python par la valeur None, soit un nœud,
contenant une étiquette et deux sous-arbres gauche et droit et représenté par une instance
de la classe Noeud donnée ci-dessous.
🐍 Script Python
class Noeud:
def __init__(self, etiquette, gauche, droit):
self.v = etiquette
self.gauche = gauche
self.droit = droit
L’arbre ci-dessus sera donc implémenté de la manière suivante :
🐍 Script Python
a = Noeud(1, Noeud(4, None, None), Noeud(0, None, Noeud(7, None, None)))
Écrire une fonction récursive taille prenant en paramètre un arbre a et qui renvoie la
taille de l’arbre que cette instance implémente.
Écrire de même une fonction récursive hauteur prenant en paramètre un arbre a et qui
renvoie la hauteur de l’arbre que cette instance implémente.
On considère que la hauteur d’un arbre vide est -1 et la taille d’un arbre vide est 0.
Exemples
🐍 Console Python
>>> hauteur(a)
2
>>> taille(a)
4
>>> hauteur(None)
-1
>>> taille(None)
0
>>> hauteur(Noeud(1, None, None))
0
>>> taille(Noeud(1, None, None))
1
Compléter le code ci-dessous
###
# Testsbksl-nlbksl-nla = Noeud(1, Noeud(4, None, None), Noeud(0, None, Noeud(7, None, None)))bksl-nlassert hauteur(a) == 2bksl-nlassert taille(a) == 4bksl-nlassert hauteur(None) == -1bksl-nlassert taille(None) == 0bksl-nlassert hauteur(Noeud(1, None, None)) == 0bksl-nlassert taille(Noeud(1, None, None)) == 1bksl-nlbksl-nl# Autres testsbksl-nlbksl-nlarbre = Noeud(1, Noeud(4, None, None), bksl-nlNoeud(0, None, Noeud(7, Noeud(1, None, None), Noeud(8, None, None)))) bksl-nlassert hauteur(arbre) == 3bksl-nlassert taille(arbre) == 6bksl-nlbksl-nl 5/5