(*********************************)
(* 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 = ()*)