(* 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