type 'a arbre_bin =
		| Vide
		| Noeud of ('a arbre_bin)*'a*('a arbre_bin);;


(*  Question 1 *)


let ex_1 =
let a1 = Noeud( Vide , 5 ,Vide ) in
let a2 = Noeud(Vide , 17 , Vide ) in
let a3 = Noeud( Vide , 20 , Vide ) in
let a4 = Noeud(Vide , 26 , Vide) in
let a5 = Noeud( a3 , 24 , a4) in
let a6 = Noeud( a2 , 19 , a5 ) in
let a7 = Noeud(a1 , 12 , a6 ) in
let a8 = Noeud(Vide,36 , Vide) in
let a9 = Noeud(Vide , 77 , Vide) in
let a10 = Noeud( a8 , 43 , a9) in
Noeud( a7 , 27 , a10);;


let ex_2 =
let a1 = Noeud( Vide , 25 ,Vide ) in
let a2 = Noeud(Vide , 17 , Vide ) in
let a3 = Noeud( Vide , 20 , Vide ) in
let a4 = Noeud(Vide , 26 , Vide) in
let a5 = Noeud( a3 , 24 , a4) in
let a6 = Noeud( a2 , 19 , a5 ) in
let a7 = Noeud(a1 , 12 , a6 ) in
let a8 = Noeud(Vide,36 , Vide) in
let a9 = Noeud(Vide , 77 , Vide) in
let a10 = Noeud( a8 , 43 , a9) in
Noeud( a7 , 27 , a10);;


type comparaison = Inf | Egal | Sup;;


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

(*  Question 2  *)

let rec recherche arb x compare =
		match arb with
			| Vide -> false
			| Noeud(a_g,e,a_d) ->
					begin
						match (compare x e) with
							| Egal -> true
							| Inf -> recherche a_g x compare
							| Sup ->	recherche a_d x compare
					
					end;;

recherche ex_1 28 compare_int;;			
		

(*  Question 3  *)

let min_gauche_max_droit arb =
	let rec min_gauche arb = match arb with
		| Vide -> failwith "erreur min_gauche"
		| Noeud(Vide , e , Vide ) -> e
		| Noeud(Vide , e , a_d) -> e
		| Noeud(a_g , e , Vide ) -> min_gauche a_g
		| Noeud(a_g, e , a_d ) -> min_gauche a_g
	
	
	in
	let rec max_droit arb = match arb with
		| Vide -> failwith "erreur min_droit"
		| Noeud(Vide , e , Vide ) -> e 
		| Noeud(Vide , e , a_d) -> max_droit a_d
		| Noeud(a_g , e , Vide ) -> e 
		| Noeud(a_g, e , a_d ) -> max_droit a_d
	
	in
	
	( min_gauche arb , max_droit arb );;



let rec min_gauche_max_droit_2 arb =
	match arb with
		| Vide -> failwith "erreur min_gauche"
		| Noeud(Vide , e , Vide ) -> (e,e)
		| Noeud(Vide , e , a_d) -> 
					let min_a_d , max_a_d = min_gauche_max_droit_2 a_d in
							( e , max_a_d )
		| Noeud(a_g , e , Vide ) -> 
					let min_a_g , max_a_g = min_gauche_max_droit_2 a_g in
							( min_a_g , e )
		| Noeud(a_g, e , a_d ) -> 
					let min_a_d , max_a_d = min_gauche_max_droit_2 a_d in
					let min_a_g , max_a_g = min_gauche_max_droit_2 a_g in
							( min_a_g , max_a_d );;


let rec verif_arb_rech arb compare 	=
	match arb with
		| Vide -> failwith " arbre vide "
		| Noeud(Vide , e , Vide ) -> (e, e  , true ) (* min,max,booleen *)
		| Noeud(Vide , e , a_d) -> 
					let (min_a_d , max_a_d , bool_a_d) = verif_arb_rech a_d compare  in
						( e, max_a_d ,   bool_a_d && 
							( (compare e min_a_d = Inf) || (compare e min_a_d = Egal)))
		| Noeud(a_g , e , Vide ) -> 
			let (min_a_g , max_a_g , bool_a_g) = verif_arb_rech a_g compare  in
						( min_a_g, e ,   bool_a_g && 
							( (compare e max_a_g  = Sup) || (compare e max_a_g  = Egal)))		
					
		| Noeud(a_g, e , a_d ) ->
					let (min_a_g , max_a_g , bool_a_g) = verif_arb_rech a_g compare in
		 			let (min_a_d , max_a_d , bool_a_d) = verif_arb_rech a_d compare  in
		 			(min_a_g , max_a_d , bool_a_d && bool_a_g && 
		 				( (compare e min_a_d = Inf) || (compare e min_a_d = Egal))&&
		 				( (compare e max_a_g  = Sup) || (compare e max_a_g  = Egal)))
					;;
let verif_recherche arb compare 	=
	let (min_gauche , max_droit , bool ) = 	verif_arb_rech arb compare in bool ;;


verif_recherche ex_2 compare_int;;



(*  Question 4  *)
let rec verif_tri liste compare =
		match liste with
			| []| [_] -> true
			| a::b::reste -> 
				( not (compare a b = Sup)) && verif_tri (b::reste) compare;;

verif_tri [1;5;19;9 ; 10 ; 12 ; 12 ; 15] compare_int;;			
			
	

(*  Question 5  *)
let rec insere_feuille arb element compare =
			match arb with
				| Vide -> Noeud( Vide , element , Vide )
				| Noeud(a_g , racine , a_d ) ->
						match compare element racine with
							| Egal -> arb
							| Inf ->Noeud( insere_feuille a_g element compare , racine , a_d)
							| Sup ->Noeud(a_g,racine , insere_feuille a_d element compare ) ;;

						
insere_feuille ex_1 14 compare_int;;	


(*  Exercice 6  *)
let rec decoupe arb element compare =
		match arb with
			| Vide -> ( Vide , Vide )
			| Noeud(a_g , racine , a_d ) ->	
				match compare element racine with
					| Egal -> (a_g , a_d )
					| Inf -> let ( a_g_g , a_g_d) = decoupe a_g element compare in
						( a_g_g , Noeud ( a_g_d, racine , a_d ))
					| Sup -> let ( a_d_g , a_d_d ) = decoupe a_d element compare in
						( Noeud(a_g , racine , a_d_g) , a_d_d );;

decoupe ex_1 14 compare_int;;	

let insere_racine  arb element compare =
	let a_g , a_d = decoupe arb element compare  in
				Noeud(a_g ,element , a_d);; 

insere_racine ex_1 14 compare_int ;;		

let rec construction_feuille liste compare =
	match liste with
		| [] -> Vide
		| a::reste -> 
			insere_feuille (construction_feuille reste compare) a compare;;

construction_feuille [1;2;3;4;5;6;7;8;9] compare_int;;

let rec construction_racine liste compare =
	match liste with
		| [] -> Vide
		| a::reste -> 
			insere_racine (construction_racine reste compare) a compare;;


construction_racine	[1;2;3;4;5;6;7;8;9] compare_int;;