Info_MPSI/test2/Arbres.ml

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)))
;;