(*********************************)
(*    Arbres binaires en caml    *)
(*********************************)

(* Un arbre binaire est soit vide : Lambda, soit un noeud et deux sous arbres :
 * Node(e, arbregauche, arbredroit)
 *)
type 'a tree =  Lambda | Node of 'a * 'a tree * 'a tree;;

let bonsai = Node(7, Node(3, Node(8, Lambda, Lambda), Node(12, Node(1, Lambda,
Lambda), Lambda)), Node(4, Lambda, Node(2, Lambda, Lambda)));;


let rec profondeur t = match t with
| Lambda -> 0
| Node(_, t1, t2) -> 1 + max (profondeur t1) (profondeur t2)
;;

let rec taille t = match t with
| Lambda -> 0
| Node(_, t1, t2) -> 1 + (taille t1) + (taille t2)
;;

profondeur bonsai;;
taille bonsai;;

(* Recherche dans un arbre binaire quelconque *)

let rec estDans x t = match t with
| Lambda -> false
| Node(a, _, _) when x=a -> true
| Node(_, t1, t2) -> (estDans x t1) or (estDans x t2)
;;

estDans 7 bonsai;;
estDans 9 bonsai;;

let rec prefixe t = match t with
| Lambda -> ()
| Node(x, t1, t2) -> print_int x; print_string " "; prefixe t1; prefixe t2
;;

let rec infixe t = match t with
| Lambda -> ()
| Node(x, t1, t2) -> infixe t1; print_int x; print_string " "; infixe t2
;;

let rec postfixe t = match t with
| Lambda -> ()
| Node(x, t1, t2) -> postfixe t1; postfixe t2; print_int x; print_string " "
;;

prefixe bonsai;;
(* 7 3 8 12 1 4 2 - : unit = () *)

infixe bonsai;;
(* 8 3 1 12 7 4 2 - : unit = () *)

postfixe bonsai;;
(* 8 1 12 3 2 4 7 - : unit = () *)

(* Pour le parcours en largeur, on va utiliser une file *)
type 'a file = Vide | F of 'a * 'a file;;
let rec enfiler x f = match f with
| Vide -> F(x, Vide)
| F(t, q) -> F(t, enfiler x q)
;;
let defiler f = match f with
| F(t, q) -> q
;;
let premier = function
    | F(t, q) -> t
;;

(* largeur_aux prend une file des arbres à parcourir :
    * je prends le premier arbre, j'affiche son noeud et j'enfile le sous arbre
    * gauche et le sous arbre droit dans la file d'arbres à traiter.*)
let rec largeur_aux l = match l with
| Vide -> ()
| F(t, q) -> match t with
            | Lambda -> largeur_aux q
            | Node(x, g, d) -> print_int x; print_string " "; 
                    largeur_aux (enfiler d (enfiler g q))
;;

let largeur t = largeur_aux (F(t, Vide));;

largeur bonsai;;
(* 7 3 4 8 12 2 1 - : unit = ()*)