type 'a tree =
| Leaf of 'a
| Node of 'a tree * 'a tree;;

(**** Q1 ****)
let t =
Node( Node( Node( Leaf "x0" , Leaf "x1" ), Leaf "x2" ) , Node( Leaf "x3" , Leaf "x4" ));;

(**** Q2 ****)
let rec nodes = function
| Leaf x -> 0
| Node (a0,a1) -> 1 + nodes a0 + nodes a1;;

(**** Q3 ****)
let rec height = function
| Leaf x -> 0
| Node (a0,a1) -> 1 + max (height a0) (height a1);;

(**** Q4 ****)
let rec max_tree = function
| Leaf x -> x
| Node (a0,a1) -> max (max_tree a0) (max_tree a1);;

nodes t;;
height t;;
max_tree t;;

(**** Exemple d'arbre de Huffman ****)

let h =
Node( Node( Node( Leaf `o` , Node( Leaf `a` , Node( Leaf `m` , Leaf `u` ))), Node(Leaf `l` , Node( Leaf `c`, Leaf `s`))), Node( Node(Leaf `i` , Leaf `e` ), Node(Leaf `m`, Leaf `t`)));;


(**** Q5 ****)
let rec sub_tree a = function
| [] -> a
| t::q -> match a with
  | Leaf x -> failwith "Mot trop long"
  | Node (a0,a1) -> sub_tree (if t then a0 else a1) q;;

sub_tree h [false;true];;
sub_tree h [false;true;false];;
sub_tree h [false;true;false;false];;

(**** Q6 ****)
let rec read a l = match a with
| Leaf x -> (x,l)
| Node (a0,a1) ->
   match l with
   [] -> failwith "Mot trop court"
   | t::q -> read (if t then a0 else a1) q;;
 
let w = [false;true;false;false;false;false;true;false;true;true;true;true];;
read h w;;


(**** Q7 ****)
let rec decode a = function 
| [] -> ""
| l -> let (c,q) = read a l in (string_of_char c)^(decode a q);;

decode h w;;


(**** Q8 ****)
let liste_tentant = [ (3,`t`); (2,`n`); (1,`a`); (1,`e`)];;

let arbre_tentant = Node (Node (Node (Leaf `a`, Leaf `e`), Leaf `n`), Leaf `t`);;


(**** Q9 ****)
let rec insert x = function
| [] -> [x]
| t::q -> if x>t then t::(insert x q) else x::(t::q);;

(**** Q10 ****)
let rec merge = function
| [] -> failwith "liste vide !!!"
| [(_,a)]->a
| (n1,a1)::((n2,a2)::q) -> merge (insert (n1+n2,Node(a1,a2)) q);;

merge (sort__sort (prefix <=) (map (fun (n,x)->(n,Leaf x)) liste_tentant));;