type 'a avl = Empty | Node of int * 'a avl * 'a * 'a avl

let depth tree = 
    match tree with
        Node (d, _, _, _) -> d
      | Empty -> 0

let rec fold_dfs_aux f acc lar =
  match lar with
    [] -> acc
  | el::li -> 
     match el with
     Empty -> fold_dfs_aux f acc li
     | Node (alt,e,a,d) -> fold_dfs_aux f (f acc a) (e::d::li);;

let fold_dfs f acc ar = fold_dfs_aux f acc [ar];;

let rec fold_bfs_aux f acc lar =
  match lar with
    [] ->  acc
  | el::li -> 
     (match el with
       Empty -> fold_bfs_aux f acc li
     | Node (alt,e,a,d) -> (fold_bfs_aux f (f acc a) (li@[e;d])));;

let fold_bfs f acc ar = fold_bfs_aux f acc [ar];;

(*

                  1
           5            10
        7            15    11

*)
let ex = 
  Node (0,
        (Node(0,
              (Node(0,Empty,7,Empty)),
              5,
              (Empty))),
        1,
        ((Node(0,Node(0,Empty,15,Empty),
               10,
               (Node(0,(Empty),11,(Empty)))))));;


let () = (fold_bfs (fun a el -> (Printf.printf "%d\n" el); flush stdout) () ex)

let () = (fold_dfs (fun a el -> (Printf.printf "%d\n" el); flush stdout) () ex)

This document was generated using caml2html