(* prelucrări pe diverse tipuri de arbori *)

open Printf
   
(* arbore oarecare *)
type 'a tree = T of 'a * 'a tree list
let arb = T (7, [T(2, []);
               T(6, [T (5, []);
                     T(11, [])])])
                  
(* arbore binar *)
type 'a bintree = Nil | BT of 'a bintree * 'a * 'a bintree
let ab = BT (BT(Nil, 2, Nil),
                  7,
                  BT(BT(Nil, 5, Nil), 6, BT(Nil, 11, Nil)))

(* arbore strict binar: frunză sau 2 copii *)
type 'a sbtree = L of 'a | ST of 'a sbtree * 'a * 'a sbtree

let asb = ST (L 2, 7, ST(L 5, 6, L 11))

(* numărăm nodurile *)
let rec count_bt = function
  | Nil -> 0
  | BT (left, _, right) -> 1 + count_bt left + count_bt right

let rec count_t = function
  | T (_, tlst) -> List.fold_left (fun s e -> s + count_t e) 1 tlst
     
let rec count_sbt = function
  | L _ -> 1
  | ST (left, _, right) -> 1 + count_sbt left + count_sbt right

let printd =                         
  let rec _printd d = function
    | Nil -> ()
    | BT (left, v, right) -> printf "nodul %d la adancimea %d\n" v d;
                             _printd (d+1) left; _printd (d+1) right
  in _printd 0

let height =
  let rec h2 = function
    | Nil -> -1                (* la 1 nivel sub nodul părinte *)
    | BT (left, _, right) -> 1 + max (h2 left) (h2 right)
  in function
  | Nil -> 0        (* vrem tot 0 pentru arborele vid *)
  | t -> h2 t

let rec height2 = function
  | Nil | BT (Nil, _, Nil) -> 0        (* nu avem muchie *)
  | BT (left, _, right) -> 1 + max (height2 left) (height2 right)
                           
let combine (v1, d1) (v2, d2) = if d1 > d2 then (v1, d1) else (v2, d2)

let deepest t = 
  let rec _deepest d = function        (* una din valorile de pe ultimul nivel *)
  | Nil -> failwith "no value"
  | BT (Nil, v, Nil) -> (v, d)
  | BT (left, v, right) -> combine (_deepest (d+1) left) (_deepest (d+1) right)
  in _deepest 0 t

(* afisează în preordine cu numărul nodului *)
(* toate funcțiile returnează numărul ultimului nod *)
let preorder =
  let rec countpre n = function        (* n: ultimul număr folosit *)
    | L v -> let n1 = n + 1 in printf "%d: %d\n" n1 v; n1
    | ST (left, v, right) ->
       let n1 = n + 1 in printf "%d: %d\n" n1 v;
                         countpre (countpre n1 left) right
  in countpre 0

let preorder2 t =
  let rec countpre t n = match t with (* arg: întâi arbore apoi număr *)
    | L v -> let n1 = n + 1 in printf "%d: %d\n" n1 v; n1
    | ST (left, v, right) ->
       let n1 = n + 1 in printf "%d: %d\n" n1 v;
                         n1 |> countpre left |> countpre right
  in countpre t 0
   
let inorder = 
  let rec countin n = function
    | L v -> let n1 = n + 1 in printf "%d: %d\n" n1 v; n1
    | ST (left, v, right) ->
       let n1 = 1 + countin n left in
       printf "%d: %d\n" n1 v;
       countin n1 right
  in countin 0

let postorder = 
  let rec countpost n = function
    | L v -> let n1 = n + 1 in printf "%d: %d\n" n1 v; n1
    | ST (left, v, right) ->
       let n1 = 1 + countpost (countpost n left) right in
       printf "%d: %d\n" n1 v; n1
  in countpost 0

This document was generated using caml2html