OCaml (option informatique) · Chapitre 3 · Exercice de TD
Compter les feuilles
Types sommes et arbres · niveau 2
É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 dOn distingue trois cas par filtrage : l'arbre vide ( 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).
Exercices semblables
- Hauteur d'un arbre corrigé
- Miroir d'un arbre corrigé
- Évaluer une expression arithmétique corrigé
- Appartenance dans un arbre binaire de recherche corrigé
- Insertion dans un ABR corrigé