(* Déterminer si une liste d'entiers correspond ou non aux profondeurs
   des feuilles d'un arbre binaire, considérées dans l'ordre infixe.

   Ainsi, la liste [1;3;3;2] correspond à un arbre
   mais pas la liste [1;3;3]. *)

let rec is_tree_rec left right = match left, right with
  | _, [] -> false
  | [], [d] -> d = 0
  | [], d :: l -> is_tree_rec [d] l
  | d1 :: l1, d2 :: l2 when d1 = d2 -> is_tree_rec l1 (d1 - 1 :: l2)
  | l1, d2 :: l2 -> is_tree_rec (d2 :: l1) l2

let is_tree l =
  is_tree_rec [] l

(* tests *)

let () = assert (is_tree [0])
let () = assert (not (is_tree [1]))
let () = assert (is_tree [1;3;3;2])
let () = assert (not (is_tree [1;3;3]))
let () = assert (not (is_tree [1;3;2]))

(* Note : Il est facile d'adapter ce programme pour reconstruire l'arbre *)

type tree =
  | E
  | N of tree * tree

exception NoTree

let rec is_tree_rec left right = match left, right with
  | _, [] -> raise NoTree
  | [], [0, t] -> t
  | [], [_] -> raise NoTree
  | [], dt :: l -> is_tree_rec [dt] l
  | (d1, t1) :: l1, (d2, t2) :: l2 when d1 = d2 ->
      is_tree_rec l1 ((d1 - 1, N (t1, t2)) :: l2)
  | l1, dt2 :: l2 -> is_tree_rec (dt2 :: l1) l2

let is_tree l =
  is_tree_rec [] (List.map (fun i -> i, E) l)

This document was generated using caml2html