# WikiLuc

### Site Tools

dit:cours:prog1:cours05

Voir le module `itree.cma` ci-dessous.

```(* test.ml *)

(*
ocamlbuild itree.cma
rlwrap ocaml -I _build/ itree.cma test.ml
*)

open Itree

let rec generate n =
if n < 0 then empty()
else if Random.int 3 = 0
then empty ()
else make (Random.int 10) (generate (n - 1)) (generate (n - 1))
;;

exception Found of itree;;

let search t a =
let rec search_aux t =
if is_empty t then ()
else
begin
(if (get_node t) = a then raise (Found t));
if Random.int 2 = 0 (* To demonstrate that the traversal order is random *)
then
begin search_aux (get_left t); search_aux (get_right t) end
else
begin search_aux (get_right t); search_aux (get_left t) end
end
in
try
search_aux t;
print_newline ()
with
Found t ->
print_string "Found! ";
print t;
print_newline ()
;;

let _ =
for i = 1 to 3
do
let t = generate 5 in search t 8
done
;;```

```(* itree.mli *)

type itree
val empty : unit -> itree
val make : int -> itree -> itree -> itree
val get_node : itree -> int
val get_left : itree -> itree
val get_right : itree -> itree
val is_empty : itree -> bool
val print : itree -> unit```

```(* itree.ml *)

type itree = Empty | Cell of cell
and cell = {node: int; left: itree; right: itree}

let empty () = Empty;;

let make a t1 t2 = Cell {node = a; left = t1; right = t2};;

let get_node t =
match t with
| Cell c -> c.node
| _ -> failwith "get_node"

let get_left t =
match t with
| Cell c -> c.left
| _ -> failwith "get_left"

let get_right t =
match t with
| Cell c -> c.right
| _ -> failwith "get_right"

let is_empty t =
match t with
| Empty -> true
| _ -> false

let rec print t =
if is_empty t then print_string "."
else
begin
print_string "(";
print_int (get_node t);
print_string " ";
print (get_left t);
print_string " ";
print (get_right t);
print_string ")"
end```