Bonjour,
Je ne comprends pas d'où peut provenir mon erreur quand à la fonction nb_feuilles que j'utilise dans la fonction parameters. En effet, une feuille est bien un noeud dont l'arité vaut 0.
Ci-dessous le code de ma fonction nb_feuilles :
let rec nb_feuilles t = match t with |Empty -> 0 |Bin(x,t1,t2) -> if (arity t1 = 0) && (arity t2 = 0) then (1+ nb_feuilles t1 + nb_feuilles t2) else (nb_feuilles t1 + nb_feuilles t2) ;;
Merci d'avance,
Cordialement,
Jon STARK
Bonjour,
au lieu de créer une fonction qui compte ton nombre de feuilles, tu peux utiliser ta fonction btree_size.
nombre de feuilles = nombre de nœuds + 1
Cordialement,
Mathieu DUBAN
Merci de ta réponse, mais j'aimerais plutôt utiliser la fonction arity qui compte le nombre de fils d'un noeud, et qui me servira ensuite pour la fonction nb_noeud_arite_1 et nb_noeud_arite_2.
Comme une feuille est un noeud d'arité 0, je ne vois pas pourquoi la fonction ci-dessus ne fonctionne pas...
Merci.
La relation
nombre de feuilles = nombre de nœuds + 1
n'est pas correcte. D'une part, il faut retenir que toute feuille est un nœud particulier.
D'autre part, un arbre dans lequel tous les nœuds ont un sous-arbre gauche vide a une seule feuille, et peut par contre avoir autant de nœuds qu'on veut.
Lorsque l'arbre est plein (pas de noeud d'arité 1), alors
nombre de feuilles = nombre de nœuds internes + 1
On peut partir d'un exemple: l'arbre du diaporama du cours 1, diapo 24/53, a 4 feuilles : les nœuds d'étiquettes 4, 6, 7, 9, qui sont les seuls à ne pas avoir de fils. Le sous-arbre gauche a 3 feuilles et le sous-arbre droit en a une.
Dans l'arbre Bin(x,t1,t2), il n'y a qu'un seul cas où x est une feuille : quand son arité soit 0, donc quand t1 et t2 sont vides. Sinon, x n'est pas une feuille, donc les feuilles de l'arbre sont soit des feuilles de t1 soit des feuilles de t2.
Merci de votre réponse,
Il faut donc que je rajoute dans mon match la condition suivante ?
|Bin(x,Empty,Empty) -> 1
C'est pourtant ce que j'avais testé pour chaque sous-arbres avec la condition suivante : if arity t1=0 && arity t2=0 et seulement dans ce cas, j'incrémentais le nombre de feuilles de 1 dans l'appel récursif suivant. Sinon je continuais à parcourir l'ensemble des sous-arbres récursivement sans incrémenter le nombre de feuilles.
Je ne vois toujours pas d'où peut provenir le problème...
Cordialement,
On peut effectivement ajouter ce cas.
Le cas où
(arity t1 = 0) && (arity t2 = 0)n'est pas le même, il dit que
t1 et t2 sont réduits à des feuilles.
La question qu'il faut se poser est : que retourner si x n'est pas une feuille ?