type 'a arbre = Vide | Noeud of 'a * 'a arbre * 'a arbre;;

let ex1 = Noeud(1, Noeud(2, Noeud(4, Vide, Vide), Noeud(5, Vide, Vide)), Noeud(3, Noeud(6, Vide, Vide), Noeud(7, Vide, Vide)));;

let rec nbr_sommets a = match a with
| Vide -> 0
| Noeud(_, g, d) -> 1 + nbr_sommets g + nbr_sommets d;;

let rec hauteur a = match a with
| Vide -> 0
| Noeud(_, g, d) -> 1 + max (hauteur g) (hauteur d);;

let rec somme a = match a with
| Vide -> 0
| Noeud(x, g, d) -> x + somme g + somme d;;

let rec miroir a = match a with
| Vide -> Vide
| Noeud(x, g, d) -> Noeud(x, miroir d, miroir g);;

let rec est_miroir a1 a2 = match a1, a2 with
| Vide, Vide -> true
| Vide, Noeud(_, _, _) -> false
| Noeud(_, _, _), Vide -> false
| Noeud(_, g1, d1), Noeud(_, g2, d2) -> est_miroir g1 d2 && est_miroir d1 g2;;

let rec est_complet a = match a with
| Vide -> true
| Noeud(_, Vide, Vide) -> true
| Noeud(_, g, Vide) -> false
| Noeud(_, Vide, d) -> false
| Noeud(_, g, d) -> est_complet g && est_complet d;;

let rec est_parfait a = match a with
| Vide -> true
| Noeud(_, Vide, Vide) -> true
| Noeud(_, g, d) -> est_parfait g && est_parfait d && hauteur g = hauteur d;;

let rec est_arbre_binaire a = match a with
| Vide -> true
| Noeud(_, Vide, Vide) -> true
| Noeud(_, g, Vide) -> est_arbre_binaire g
| Noeud(_, Vide, d) -> est_arbre_binaire d
| Noeud(_, g, d) -> est_arbre_binaire g && est_arbre_binaire d;;

let rec est_arbre_binaire_complet a = match a with
| Vide -> true
| Noeud(_, Vide, Vide) -> true
| Noeud(_, g, Vide) -> false
| Noeud(_, Vide, d) -> false
| Noeud(_, g, d) -> est_arbre_binaire_complet g && est_arbre_binaire_complet d && hauteur g = hauteur d;;

let rec est_arbre_binaire_parfait a = match a with
| Vide -> true
| Noeud(_, Vide, Vide) -> true
| Noeud(_, g, d) -> est_arbre_binaire_parfait g && est_arbre_binaire_parfait d && hauteur g = hauteur d;;

let rec est_arbre_binaire_miroir a = match a with
| Vide -> true
| Noeud(_, Vide, Vide) -> true
| Noeud(_, g, Vide) -> est_arbre_binaire_miroir g
| Noeud(_, Vide, d) -> est_arbre_binaire_miroir d
| Noeud(_, g, d) -> est_arbre_binaire_miroir g && est_arbre_binaire_miroir d;;

let rec est_arbre_binaire_complet_miroir a = match a with
| Vide -> true
| Noeud(_, Vide, Vide) -> true
| Noeud(_, g, Vide) -> false
| Noeud(_, Vide, d) -> false
| Noeud(_, g, d) -> est_arbre_binaire_complet_miroir g && est_arbre_binaire_complet_miroir d && hauteur g = hauteur d;;

let rec est_arbre_binaire_parfait_miroir a = match a with
| Vide -> true
| Noeud(_, Vide, Vide) -> true
| Noeud(_, g, d) -> est_arbre_binaire_parfait_miroir g && est_arbre_binaire_parfait_miroir d && hauteur g = hauteur d;;

let rec noeuds a = match a with
| Vide -> []
| Noeud(x, g, d) -> x::(noeuds g)@(noeuds d);;

let rec nbr_noeuds a = match a with
| Vide -> 0
| Noeud(_,Vide,Vide) -> 0
| Noeud(_,g,d) -> 1 + nbr_noeuds g + nbr_noeuds d;;

let rec nbr_feuilles a = match a with
| Vide -> 0
| Noeud(_, Vide, Vide) -> 1
| Noeud(_, g, d) -> nbr_feuilles g + nbr_feuilles d;;

let rec est_feuille a = match a with
| Vide -> false
| Noeud(_, Vide, Vide) -> true
| Noeud(_, g, d) -> false;;

let rec feuilles a = match a with
| Vide -> []
| Noeud(x, Vide, Vide) -> [x]
| Noeud(_, g, d) -> (feuilles g)@(feuilles d);;

let rec maximum a = match a with
| Vide -> failwith "arbre vide"
| Noeud(x, Vide, Vide) -> x
| Noeud(x, g, d) -> max x (max (maximum g) (maximum d));;

let rec minimum a = match a with
| Vide -> failwith "arbre vide"
| Noeud(x, Vide, Vide) -> x
| Noeud(x, g, d) -> min x (min (minimum g) (minimum d));;

let rec entier a = match a with
| Vide -> true
| Noeud(_, Vide, Vide) -> true
| Noeud(_, Vide, _) -> false
| Noeud(_, _, Vide) -> false
| Noeud(x, g, d) -> entier g && entier d;;

let rec prefixe a = match a with
| Vide -> []
| Noeud(r,Vide,Vide)-> [r]
| Noeud(x, g, d) -> (x::prefixe g)@(prefixe d);;

let rec infixe a = match a with
| Vide -> []
| Noeud(r,Vide,Vide)-> [r]
| Noeud(x, g, d) -> (infixe g)@(x::infixe d);;

let rec postfixe a = match a with
| Vide -> []
| Noeud(r,Vide,Vide)-> [r]
| Noeud(x, g, d) -> (postfixe g)@(postfixe d)@[x];;

let rec liste_racines l = match l with
| [] -> []
| (Noeud(x, _, _)::q) -> x::(liste_racines q);;

let rec liste_fils l = match l with
| [] -> []
| (Noeud(_, g, d)::q) -> (g::d::(liste_fils q));;


let rec parcours_largeur a =
  let rec aux l = match l with
  | [] -> []
  | _ -> (liste_racines l)@(aux (liste_fils l)) in
  aux [a];;

type arbre_bin = Vide | Noeud of int * arbre_bin * arbre_bin;;

type compa = Inf | Sup | Egal;;

let compare_int x y = if x < y then Inf else if x > y then Sup else Egal;;

let rec recherche (a:arbre_bin) f (x:int) = match a with
| Vide -> false
| Noeud(y, g, d) -> match f x y with
  | Egal -> true
  | Inf -> recherche g f x
  | Sup -> recherche d f x;;

let rec min_gauche_max_droit a = match a with
| Vide -> failwith "arbre vide"
| Noeud(e,Vide,Vide) -> (e,e)
| Noeud(e,ag,Vide)-> let (min, max) = min_gauche_max_droit ag in (min, e)
| Noeud(e,Vide,ad)-> let (min, max) = min_gauche_max_droit ad in (e, max)
| Noeud(e,ag,ad)-> let (min, max) = min_gauche_max_droit ag in (min, max);;

let rec verif_encadre a f x y= match a with
| Vide -> true
| Noeud(e,ag,ad) -> not(f e x = Inf) && not(f e y = Sup) && verif_encadre ag f x e && verif_encadre ad f e y;;

let verif_arbre_recherche a f = let (min, max) = min_gauche_max_droit a in verif_encadre a f min max;;

let rec verif_tri l f = match l with
| [] -> true
| [x] -> true
| t::t1::q -> not(f t t1 = Sup) && verif_tri (t1::q) f;;

let rec infixe2 a = match a with
| Vide -> []
| Noeud(r,Vide,Vide)-> [r]
| Noeud(x, g, d) -> (infixe2 g)@(x::infixe2 d);;

let verif_arbre_recherche2 a f = verif_tri (infixe2 a) f;;

let rec insere_feuille a f x = match a with
| Vide -> Noeud(x, Vide, Vide)
| Noeud(e, g, d) -> match f x e with
  | Egal -> a
  | Inf -> Noeud(e, insere_feuille g f x, d)
  | Sup -> Noeud(e, g, insere_feuille d f x);;

let rec decoupe (a:arbre_bin) f (x:int) : arbre_bin * arbre_bin= match a with
| Vide -> (Vide, Vide)
| Noeud(e, g, d) -> match f x e with
  | Egal -> (g, d)
  | Inf -> let (g1, d1) = decoupe g f x in (g1, Noeud(e, d1, d))
  | Sup -> let (g1, d1) = decoupe d f x in (Noeud(e, g, g1), d1);;

let insere_racine a f x = let (g, d) = decoupe a f x in Noeud(x, g, d);;

let rec construction_feuille l f = match l with
| [] -> Vide
| t::q -> insere_feuille (construction_feuille q f) f t;;

let rec construction_racine l f = match l with
| [] -> Vide
| t::q -> insere_racine (construction_racine q f) f t;;

let rec rotation_gauche a = match a with
| Vide -> Vide
| Noeud(x, Vide, Vide) -> Noeud(x, Vide, Vide)
| Noeud(x, Noeud(y, g, d), Vide) -> Noeud(y, g, Noeud(x, d, Vide))
| Noeud(x, g, d) -> Noeud(x, rotation_gauche g, d);;

let rec rotation_droite a = match a with
| Vide -> Vide
| Noeud(x, Vide, Vide) -> Noeud(x, Vide, Vide)
| Noeud(x, Vide, Noeud(y, g, d)) -> Noeud(y, Noeud(x, Vide, g), d)
| Noeud(x, g, d) -> Noeud(x, g, rotation_droite d);;

let rec fusionne a1 a2 = match a1, a2 with
| Vide, Vide -> Vide
| Vide, Noeud(x, g, d) -> Noeud(x, g, d)
| Noeud(x, g, d), Vide -> Noeud(x, g, d)
| Noeud(x, g, d), Noeud(y, g1, d1) -> let (min, max) = min_gauche_max_droit a2 in Noeud(min, g, fusionne d a2);;