Hauteur d'un arbre général

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

Énoncé

Écrire hauteur_arbre : $1$ pour une feuille, et $1$ de plus que la hauteur maximale de ses sous-arbres sinon (forêt vide $\to$ hauteur $0$ ).

Corrigé

let rec hauteur_arbre a =
  match a with
  | Noeud (_, f) -> 1 + hauteur_foret f
and hauteur_foret f =
  match f with
  | [] -> 0
  | a :: reste ->
      let h = hauteur_arbre a and hr = hauteur_foret reste in
      if h > hr then h else hr

hauteur_foret renvoie la plus grande hauteur des arbres de la forêt (et $0$ pour la forêt vide). Une feuille Noeud (x, []) a donc pour hauteur 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.