Compter les feuilles

Exercice · OCaml (option informatique), chapitre 3 — Types sommes et arbres

Énoncé

Écrire nb_feuilles a, le nombre de feuilles (nœuds à deux sous-arbres vides).

Corrigé

let rec nb_feuilles a =
  match a with
  | Vide -> 0
  | Noeud (Vide, _, Vide) -> 1
  | Noeud (g, _, d) -> nb_feuilles g + nb_feuilles d

On distingue trois cas par filtrage : l'arbre vide ( $0$ feuille), la feuille (Noeud (Vide, _, Vide), qui en est une), et le nœud interne (somme des feuilles des deux sous-arbres). L'ordre importe : le motif feuille, plus particulier, doit précéder le motif général Noeud (g, _, d).

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.