WikiLuc

Guest connection: login: Guest, password: anonymous

User Tools

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
*)
 
#load "itree.cma"
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_string "Not Found...";
    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

dit/cours/prog1/cours05.txt · Last modified: 2018/10/03 18:18 by luc.bouge