Hauteur d'un arbre

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

Énoncé

Écrire hauteur a : $0$ pour l'arbre vide, et $1$ de plus que la hauteur du plus haut des deux sous-arbres sinon.

Corrigé

let rec hauteur a =
  match a with
  | Vide -> 0
  | Noeud (g, _, d) ->
      let hg = hauteur g and hd = hauteur d in
      1 + (if hg > hd then hg else hd)

On nomme les deux hauteurs (let ... and ...) pour ne les calculer qu'une fois chacune, puis on prend la plus grande. L'arbre vide a hauteur 0, une feuille hauteur 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.