type 'a arbre1 =
  | Vide
  | N of 'a * 'a arbre1 * 'a arbre1
;;

let test1 = N(2,N(1,Vide, Vide), N(4,N(6,Vide,Vide), Vide));;

let rec nb_sommet f = match f with
| Vide -> 0
| N(_,b,c) -> 1 + nb_sommet b + nb_sommet c
;;

let rec nb_noeud f = match f with
| Vide -> 0
| N(n,Vide,Vide) -> 0
| N(_,g,d) -> 1 + nb_noeud g + nb_noeud d
;;

let rec nb_feuille f = match f with
| Vide -> 0
| N(n,Vide,Vide) -> 1
| N(_,g,d) -> nb_feuille g + nb_feuille d
;;


let rec hauteur f = match f with
| Vide -> -1
| N(n,a,b) -> if hauteur a > hauteur b then 1 + hauteur a
else 1 + hauteur b
;;

let rec etiquette f = match f with
| Vide -> failwith "stop"
| N(r,Vide,Vide) -> r
| N(r,g,Vide)-> max r (etiquette g)
| N(r,Vide,d) -> max r (etiquette d)
| N(r,g,d) -> max r (max (etiquette g) (etiquette g))
;;
(* Pas sur de celui au dessus *)
let rec entier a = match a with
| Vide -> true
| N(_,Vide,Vide) -> true
| N(_,g,Vide) ->false
| N(_,Vide,d) ->false
| N(_,g,d) ->entier g && entier d
;;


type 'a arbre2 =
| F of 'a
| N of 'a * 'a arbre2 * 'a arbre2
;;

let test2 = N(2,F(1),N(4,F(7), F(8)));;

type ('f, 'n) arbre3 =
| F of 'f
| N of 'n * (('f, 'n) arbre3) * (('f,'n) arbre3)
;;

let test3 = N((+), N(( * ), F 7, N((-), F 4, F 2)), N(( * ), F 3, F 1))

type 'a arbre4 = N of 'a * ('a arbre4 list);;

let test4 = N(2, [N(3,[N(5, [])]); N(6,[N(8, []); N(4,[])]); N(7,[])]);;

let rec nb_sommet2 f = match f with
| N(_,[]) -> 0
| N(r,b::q) -> 1 + (nb_sommet2 b) + (nb_sommet2 (N(r,q)))
;;

let rec hauteur2 f = match f with
| N(_,[]) -> 0
| N(r,b::q) -> max (1+ hauteur2 b) (1+hauteur2 (N(r,q)))
;;

type 'a arbre5 =
  |Vide
  | N of 'a * 'a arbre5 * 'a arbre5
;;

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

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

let rec infixe f = match f with
| Vide -> []
|N(r,Vide,Vide)-> [r]
|N(r,g,d)->((infixe g)@[r])@(infixe d)
;;

type 'a sommet6 =
|SF of 'a
|SN of 'a
;;

type 'a arbre6 = 
|F of 'a
|N of 'a * 'a arbre6 * 'a arbre6
;;

let rec postfixe_aux l_arbre l = match l_arbre,l with
| [a],[] -> a
|_,(SF x)::q -> postfixe_aux ( F x::l_arbre) q
| d::g::r, (SN x)::q -> postfixe_aux (N(x,g,d)::r) q
;;

let postfixe6 l = postfixe_aux [] l;;

let rec prefixe_aux l = match l with
| []-> failwith "suce, liste vide"
| (SF x)::q-> F x,q
| (SN x)::q->let g,qg = prefixe_aux q in
  let d,qd = prefixe_aux qg in
  N(x,g,d),qd

;;

let prefixe l = fst (prefixe_aux l);;

let ex6 = [SF(4); SF(5); SN(6)];;

type 'a arbre7 =
| Vide
| N of 'a * 'a arbre7 * 'a arbre7
;;

let rec liste_racines l_arbres = match l_arbres with
| [] -> []
| N(n,_,_)::q-> n::liste_racines q
;;

let rec branches l = match l with
| [] -> []
| N(x,Vide,Vide)::q-> branches q
| N(x,g,d)::q-> g::(d::branches q)
;;

let rec parcours_largeur_aux l = match l with
| [] -> []
| _ -> (liste_racines l)@(parcours_largeur_aux (branches l))
;;

let parcours_largeur a = parcours_largeur_aux [a];;

type 'a arbre8 = Vide | N of 'a * 'a arbre8 * 'a arbre8;;

let ex8 = N(1,
  N(6,
  N(8,N(3,N(5,Vide,Vide),Vide),Vide),
  N(4,Vide,Vide)
  ),
  N(7,
  N(2,
  N(9,Vide,Vide),
  N(10,Vide,Vide)), Vide)
)

let rec branchedroite arbre = match arbre with
| Vide -> []
| N(x,Vide,Vide)->[x]
| N(x,g,Vide)->x::branchedroite g
| N(x,g,d)->x::branchedroite d
;;

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

let rec feuilles_prof arbre = match arbre with
| Vide -> []
| N(x,g,Vide)->x ::branchedroite g
| N(x,g,d)-> x::branchedroite d
;;
let rec feuilles_aux arbre acc = match arbre with
| Vide -> acc
| N(x,Vide,Vide)->acc@[x]
| N(_,g,d)-> feuilles_aux g (feuilles_aux d acc)
;;

let feuilles_term arbre = feuilles_aux arbre [];;

let rec squelette arbre1 arbre2 = match arbre1,arbre2 with
| Vide,Vide -> true
| N(n1,g1,d1),N(n2,g2,d2)-> squelette g1 g2 && squelette d1 d2
| _ -> false
;;

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

let rec sosa a = match a with
| Vide -> Vide
| N(x,g,d)->