Adloun

Taille d'un arbre général

Exercice · OCaml (option informatique), chapitre 7 — Enregistrements et types mutuellement récursifs

Énoncé

Avec les types mutuellement récursifs arbre / foret, écrire taille_arbre (nombre de nœuds).

Corrigé

let rec taille_arbre a =
  match a with
  | Noeud (_, f) -> 1 + taille_foret f
and taille_foret f =
  match f with
  | [] -> 0
  | a :: reste -> taille_arbre a + taille_foret reste

Deux fonctions mutuellement récursives, à l'image des deux types : taille_arbre compte pour le nœud plus la taille de sa forêt ; taille_foret parcourt la liste des sous-arbres. La feuille Noeud (x, []) a pour taille 1 + 0 = 1.

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.