(* Exercice II *)


(* 1.

         1
      /    \
     2      3
   /   \    / \
  4     5   6  7
 / \   /
8  9  10

*)
 
(* 2. *)

(* (a) *)

let minpo(apo) = etiquette(apo,0);;

(* (b) *)

let rec arbrebin_of_pa_k(a,k) = 
  if nb_noeuds(a)-1<k 
  then Vide 
  else Enrac(arbrebin_of_pa_k(a,2*k+1),
             etiquette(a,k),
             arbrebin_of_pa_k(a,2*k+2))
;;

let rec arbrebin_of_pa(a) = arbrebin_of_pa_k(a,0);;

(* (c) *)

let rec estpo_bin(a) = match a with
    Vide -> true
  | Enrac(g,r,d) -> estpo_bin(g) && estpo_bin(d) 
       && (vide(g) || r <= racine(g)) 
       && (vide(d) || r <= racine(d))
;;

let estpo(a) = estpo_bin(arbrebin_of_pa(a));;

(* (d) *)

let rec mont(a,k) = 
  if etiquette(a,k)<etiquette(a,(k-1)/2) 
  then mont(echange(a,k,(k-1)/2),(k-1)/2)
  else a   
;;

let insere(apo,x) = 
  let a = Ajoute(apo,x) in 
  let n = nb_noeuds(a) in 
    mont(a,n-1)
;;