type 'a tree = Nil | T of 'a tree * 'a * 'a tree
                                            
let rec treerecon inl = function        (* 2 liste: inordine preordine *)
  | [] -> if inl = [] then Nil else raise Exit
  | root :: tpre ->
     let rec split2 (li, lp) = function (* parcurge (in, pre) si acumuleaza *)
       | (hi :: ri, rp) ->
          if hi = root then let left = treerecon (List.rev li) (List.rev lp)
                            and right = treerecon ri rp in T(left, root, right)
          else if rp = [] then raise Exit
          else split2 (hi::li, List.hd rp::lp) (ri, List.tl rp)
       | _ -> raise Exit
     in try split2 ([], []) (inl, tpre)
        with Exit -> failwith "inconsistent lists"
;;
treerecon [1; 7; 5; 6; 11; 2; 8; 4; 9] [2; 7; 1; 6; 5; 11; 8; 9; 4];;

This document was generated using caml2html