(*EXERCICE 1*)
type 'a bintree = Empty | Node('a bintree * 'a * 'a bintree);;

let values bt =
  let rec aux t l = match t with
    | Empty -> l
    | Node (g, r, d) -> r::(aux g (aux d l)) in
  aux bt [];;
		 
(* cela revient à réécrire la concaténation donc non *)
let follow l r = fold_left (::) l r;;

let rec map_tree f bt = match bt with
                        | Empty       -> Empty
		        | Node(l, m, r) -> Node(map_tree f l, f m, map_tree f r);;

let rec fold_tree f bt e = match bt with
                           | Empty       -> e
                           | Node(l, m, r) -> fold_tree f l (f m (fold_tree f r e));;

(*EXERCICE 2*)
type 'a abr = Emptyabr | Nodeabr('a abr*'a*'a abr);;

(*constructeurs plus ou moins intelligents*)
let emptyabr = Emptyabr;;

let is_empty ab = match ab with
                  | Emptyabr -> true
                  | _        -> false;;

let rec add ab e = match ab with
                  | Emptyabr       -> Nodeabr(Emptyabr, e, Emptyabr)
                  | Nodeabr(l,m,r) -> if m <= e then Nodeabr(l, m, add r e)
		                                else Nodeabr(add l e, m, r);;
  
let rec mem ab e = match ab with
               | Emptyabr       -> false
               | Nodeabr(l, m, r) -> (mem l e) || e = m || (mem r e);;
  
let rec fold_abr f ab e = match bt with
                          | Emptyabr       -> e
                          | Nodeabr(l, m, r) -> fold_abr f l (f m (fold_abr f r e));;
  
let rec map_abr f ab = match ab with
                       | Emptyabr       -> Emptyabr
		       | Nodeabr(l, m, r) -> Nodeabr(map_abr f l, f m, map_abr f r);;
		
let cardinal ab =
  let f a b = b+1 in
  fold_abr f ab 0;;
  
let valuesabr ab =
  let rec auxabr t l = match t with
    | Emptyabr -> l
    | Nodeabr (g, r, d) -> r::(aux g (aux d l)) in
  aux bt [];;

let rec cutabr ab v = match ab with
  | Emptyabr       -> (Emptyabr, Emptyabr)
  | Nodeabr(l,m,r) -> if m > v
		      then
			let xl = cutabr l v in
			   (fst xl, Nodeabr(snd xl, m, r))
		      else
			let xr = cutabr r v in
			   (Nodeabr(l, m, fst xr), snd xr);;

(*A completer*)
let fusion ab1 ab2 = match ab1,ab2 with
                     | Emptyabr,_   -> ab2
                     | ab1,Emptyabr -> ab1
		     | _            -> ab2;;

let pop ab e = match ab with
  | Emptyabr       -> Emptyabr
  | Nodeabr(l,m,r) -> if not (mem ab e) then ab
		 else if m > e          then Nodeabr(pop l e, m, r)
		 else if m < e          then Nodeabr(l, m, pop r e)
		                        else fusion l r;;
  
let rec creat n = if n = 0 then add Emptyabr 0
		           else add (creat (n-1)) n;;