Intermédiaire
🧠 Fondamentaux
20 XP
0 personnes ont réussi
Compter les noeuds d'un arbre
Un exercice de rechauffement recursif : compter combien de noeuds contient un arbre binaire.
Le raisonnement est simple : le nombre total de noeuds, c'est 1 (le noeud ou tu te trouves) plus le nombre de noeuds a gauche, plus le nombre de noeuds a droite.
Exemples : Un arbre vide contient 0 noeuds Un arbre avec juste une racine contient 1 noeud Un BST construit avec [5, 3, 7, 1, 4] contient 5 noeuds
Écris une fonction compter_noeuds(racine) qui retourne le nombre total de noeuds.
Tests (2/4)
Arbre vide
assert compter_noeuds(None) == 0
Cinq noeuds
racine = None
for v in [5, 3, 7, 1, 4]:
racine = insérer(racine, v)
assert compter_noeuds(racine) == 5
+ 0 tests cachés
Indices (3 disponibles)
Solution officielle
class Node:
def __init__(self, valeur):
self.valeur = valeur
self.gauche = None
self.droite = None
def inserer(racine, valeur):
if racine is None:
return Node(valeur)
if valeur < racine.valeur:
racine.gauche = insérer(racine.gauche, valeur)
else:
racine.droite = insérer(racine.droite, valeur)
return racine
def compter_noeuds(racine):
if racine is None:
return 0
return 1 + compter_noeuds(racine.gauche) + compter_noeuds(racine.droite)