# WikiLuc

### Site Tools

dit:cours:prog1:cours06

# Recherche dans un arbre par continuation

Voir ci-dessous pour le fichier `mitree.ml`. Voici l'arbre qui est construit dans l'exemple.

```#use "mitree.ml";;

open Mitree;;

let search a t k =
let break () = k true in
let rec search_aux t k =
begin
tick();
if is_empty t then k ();
if (get_node t) = a then break ();
let k' () = search_aux (get_right t) k
in search_aux (get_left t) k'
end
in search_aux t (fun () -> k false)

exception End_of_world;;

let cont b =
raise End_of_world
;;

let test n t =
print_endline "______________________";
reset();
print_endline ("Searching " ^ (string_of_int n) ^"..." );
try
search n t cont;
with
| End_of_world -> print_endline ("Number of explored nodes: " ^ (string_of_int (get())))
;;

let t0 = make_single 80;;
let l = [40; 120; 20; 60; 100; 140; 10; 30; 50; 70; 90; 110; 130; 150];;
List.iter (fun x -> insert x t0) l;;
print t0;;

let test_values = [40; 121; 20; 61; 100; 141; 10; 31; 50; 71; 90; 111; 130; 151];;

List.iter (fun n -> test n t0) test_values;;```

```(********* Module Milist *********)

module type Mitree =
sig
type mitree (* Opaque type *)
val empty : unit -> mitree
val make : int -> mitree -> mitree -> mitree
val get_node : mitree -> int
val get_left : mitree -> mitree
val get_right : mitree -> mitree
val is_empty : mitree -> bool
val print :  mitree -> unit
val replace_left : mitree -> mitree -> unit
val replace_right : mitree -> mitree -> unit
end
;;

module Mitree =
struct
type mitree = Empty | Node of node
and node = {item: int; left: mitree ref; right: mitree ref};;

let empty () = Empty;;

let make x t1 t2 = Node {item = x; left = (ref t1); right = (ref t2)}

let get_node t =
match t with
| Node n -> n.item
| Empty -> failwith "get_node"

let get_left t =
match t with
| Node n -> !(n.left)
| Empty -> failwith "get_left"

let get_right t =
match t with
| Node n -> !(n.right)
| Empty -> failwith "get_right"

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

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

(**************)

let replace_left t t' =
match t with
| Node n -> (n.left := t')
| _ -> failwith "replace_left"

let replace_right t t' =
match t with
| Node n -> (n.right := t')
| _ -> failwith "replace_right"

end
;;

open Mitree;;

let make_single x = let e = empty () in make x e e;;

let (reset, tick, get) =
let c = ref 0 in (
(fun () -> (c := 0)),
(fun () ->  (c := !c + 1)),
(fun () -> (!c)))
;;

let rec insert x t =
(if is_empty t then failwith "insert");
let a = get_node t in begin
(if x = a then failwith "insert");
if x < a then
let t' = get_left t in
if is_empty t' then replace_left t (make_single x)
else insert x t'
else
let t' = get_right t in
if is_empty t' then replace_right t (make_single x)
else insert x t'
end
;;```