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

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 a_bin = 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 a_strictbin = ST (L 2,
                      7,
                      ST(L 5, 6, L 11))
                               
(* numărare de noduri, pentru cele 3 tipuri de arbori *)
let rec cntbin = function
  | Nil -> 0
  | BT (left, _, right) -> 1 + cntbin left + cntbin right

let rec cnt = function
  | T (_, tl) -> 1 + List.fold_left (fun acc e -> acc + cnt e) 0 tl

let rec cntsb = function
  | L _ -> 1
  | ST (left, _, right) -> 1 + cntsb left + cntsb right

(* înălțime = număr de nivele *)
let rec binheight = function
  | Nil -> 0
  | BT (left, _, right) -> 1 + max (binheight left) (binheight right)

let maxlist lst = List.fold_left max 0 lst (* max din listă de nr. naturale *)
            
(* aplică max de o funcție pe o listă *)
let maxf f list = List.fold_left (fun acc el -> max acc (f el)) 0 list

(* similar pentru înălțimea unui arbore oarecare *)
let rec height = function
  | T(_, tl) -> 1 + List.fold_left (fun acc el -> max acc (height el)) 0 tl

(* o funcție care folosește un parametru trimis în jos *)
let rec afis_nivel nivel = function (* tipărește noduri de pe un nivel dat *)
  | Nil -> ()
  | BT (arbstg, valnod, arbdr) -> if nivel = 0 then printf "%d " valnod
                                  else let n1 = nivel - 1 in
                                       afis_nivel n1 arbstg; afis_nivel n1 arbdr

let _ = print_string "nivel 1: "; afis_nivel 1 a_bin; print_newline()

(* o funcție care acumulează calea până la un nod *)
let rec printpath cale = function  (* tipărește fiecare frunză cu calea de la radacina *)
  | L valnod -> List.iter (printf "%d ") (List.rev cale); printf "%d\n" valnod
  | ST (arbstg, valnod, arbdr) -> let cale1 =  valnod :: cale in
                                  printpath cale1 arbstg; printpath cale1 arbdr

let _ = printpath [] a_strictbin
                                 
(* funcție care combină rezultatele de la subarbori *)
let rec mem x = function (* se afla in arbore ? *)
  | Nil -> false
  | BT (arbstg, valnod, arbdr) -> x = valnod || mem x arbstg || mem x arbdr

(* arbore binar de căutare: toate nodurile din stâng < rădăcină;
 * toate nodurile din drept > rădăcina *)
let insert t vnou = 
  let rec ins = function        (* inserează vnou în arborele argument *)
    | Nil -> BT (Nil, vnou, Nil)        (* o nouă frunză în locul liber (Nil) potrivit *)
    | BT (arbst, rad, arbdr) as t -> if vnou = rad then t (* nu insera duplicate *)
                                     else if vnou < rad then BT(ins arbst, rad, arbdr)
                                     else BT(arbst, rad, ins arbdr)
  in ins t

let tree_of_list lst = List.fold_left insert Nil lst
let bst = tree_of_list [4;5;3;2;0;6;7;8;4;5;6;2;5];;

This document was generated using caml2html