Cette page est un exercice complet, résolu pas à pas : l'énoncé, l'analyse du problème, la solution en Python, une trace détaillée sur l'exemple déjà connu de la fiche « Les arbres binaires », puis une vérification et deux exercices supplémentaires à faire seul(e).
src/arbres_binaires_exercice.py, dans le sous-dossier src à côté de cette page, contient la classe Noeud, la méthode compter_feuilles, et tous les tests. Après l'avoir téléchargé, on l'exécute dans un terminal, dans le dossier où il a été enregistré, avec python3 arbres_binaires_exercice.py (Python doit être installé sur l'ordinateur). Le fichier affiche « OK » pour chaque test s'il n'y a pas d'erreur.
Noeud (attributs gauche, racine, droit), comme dans la fiche « Les arbres binaires ». Écrire une méthode compter_feuilles qui renvoie le nombre de feuilles de l'arbre, c'est-à-dire le nombre de nœuds qui n'ont ni fils gauche ni fils droit.
On reprend exactement le même arbre que dans la fiche « Les arbres binaires », avec ses 8 nœuds A, G, D, Gp, O, P, Dg, Dd :
Rappel : une feuille est un nœud dont les deux sous-arbres (gauche et droit) sont vides. Dans cet arbre, les feuilles sont O, P, Dg et Dd : il y en a donc 4.
Dans les méthodes hauteur et taille de la fiche « Les arbres binaires », il suffisait de distinguer deux cas : l'arbre vide, et l'arbre non vide (avec un appel récursif de chaque côté). Ici, deux cas ne suffisent pas.
self vaut None) : il ne contient aucune feuille, donc compter_feuilles doit renvoyer 0.gauche et son droit valent tous les deux None) : ce nœud compte à lui seul pour une feuille, donc compter_feuilles doit renvoyer 1, sans continuer à descendre dans l'arbre (il n'y a plus rien en dessous).taille (« 1 + taille du sous-arbre gauche + taille du sous-arbre droit »), on obtiendrait pour une feuille comme O : compter_feuilles(O) = compter_feuilles(vide) + compter_feuilles(vide) = 0 + 0 = 0. C'est faux : O est bien une feuille, la réponse doit être 1. C'est pour cela qu'il faut un cas à part, testé avant de descendre récursivement dans les sous-arbres : « ce nœud est-il lui-même une feuille ? ».
def compter_feuilles(self): if self is None: return 0 elif self.gauche is None and self.droit is None: return 1 else: feuilles_gauche = self.gauche.compter_feuilles() if self.gauche else 0 feuilles_droit = self.droit.compter_feuilles() if self.droit else 0 return feuilles_gauche + feuilles_droit
Cette méthode a exactement la même forme que hauteur et taille : un test sur self is None (qui protège les appels récursifs faits via self.gauche.compter_feuilles() if self.gauche else 0), puis un calcul qui combine les résultats des deux sous-arbres. La seule différence est le cas supplémentaire elif, ajouté avant ce calcul, pour arrêter la récursion dès qu'on atteint une feuille.
A. La ligne de code correspondant au cas utilisé est surlignée ci-dessus.| Nœud | Cas | Calcul | compter_feuilles |
|---|---|---|---|
O | feuille | — | 1 |
P | feuille | — | 1 |
Gp | a des fils (gauche et droit) | 1 (O) + 1 (P) | 2 |
G | a un fils (gauche seulement) | 2 (Gp) + 0 (vide) | 2 |
Dg | feuille | — | 1 |
Dd | feuille | — | 1 |
D | a des fils (gauche et droit) | 1 (Dg) + 1 (Dd) | 2 |
A (racine) | a des fils (gauche et droit) | 2 (G) + 2 (D) | 4 |
compter_feuilles(A) vaut donc 4 : c'est bien le nombre de feuilles de l'arbre (O, P, Dg, Dd).
A = construire_arbre_exemple() # construit A, G, D, Gp, O, P, Dg, Dd comme dans la fiche « Les arbres binaires » assert A.compter_feuilles() == 4 assert A.gauche.compter_feuilles() == 2 # G assert A.droit.compter_feuilles() == 2 # D assert A.gauche.gauche.compter_feuilles() == 2 # Gp assert A.gauche.gauche.gauche.compter_feuilles() == 1 # O (feuille)
On peut aussi vérifier une propriété utile : dans un arbre binaire, taille(A) = compter_feuilles(A) + nombre de nœuds internes. Ici, taille(A) = 8 (vu dans la fiche « Les arbres binaires ») et compter_feuilles(A) = 4, donc l'arbre a aussi 4 nœuds internes (A, G, D, Gp) — ce qui se vérifie bien sur le diagramme.
compter_feuilles est en O(n), où n est le nombre de nœuds de l'arbre : comme pour hauteur et taille, l'appel récursif visite chaque nœud exactement une fois, et fait un travail constant à chaque nœud (un test, puis une addition).
En reprenant exactement la même démarche (analyser les cas, écrire la fonction récursive, tracer sur l'exemple dans un tableau), essayer de résoudre ces deux exercices sur le même arbre A :
compter_noeuds_internes qui renvoie le nombre de nœuds ayant au moins un fils. (Indication : le résultat doit être cohérent avec taille(A) = compter_feuilles(A) + compter_noeuds_internes(A), soit 8 = 4 + 4.)tout_a_gauche qui renvoie la valeur de la racine du dernier nœud atteint en descendant uniquement par les fils gauche, en partant de la racine, jusqu'à un nœud qui n'a pas de fils gauche. (Sur l'arbre A, la réponse attendue est 'O'.)