Aula 3

type 'a tree = Nil | Node of 'a * 'a tree * 'a tree;;

type 'a ntree = NNil | NNode of 'a * 'a ntree list

let rec howMany v t =
    match t with
    | Nil -> 0
    | Node(x,l,r) -> (if v = x then 1 else 0)
    + howMany v l + howMany v r;;

let rec eqPairs t =
    match t with
    | Nil -> 0
    | Node((x,y),l,r) -> (if x = y then 1 else 0)
    + eqPairs l + eqPairs r;;

let rec treeToList t =
    match t with
    | Nil ->  []
    | Node(x, l, r) -> x :: (treeToList l @ treeToList r);;

let rec height t =
    match t with
        | Nil -> 0
    | Node(x,l,r) ->
           1 + max (height l) (height r);;

let rec balanced t =
    match t with
    | Nil -> true
    | Node(x, l, r) -> if (abs(height l - height r) > 1) then
        false else balanced l && balanced r;;

let rec subtrees t =
    match t with
    | Nil -> []
    | Node(x, l, r) -> Node(x, l, r) :: (subtrees l @ subtrees r);;

let rec spring v t =
    match t with
    | Nil -> Node(v, Nil, Nil)
    | Node(x, l, r) -> Node(x, spring v l, spring v r);;

spring 2 Node(3, Node(2, 4, Nil), Nil);;

let rec fall t =
    match t with
    | Nil -> Nil
    | Node(x, Nil, Nil) -> Nil
    | Node(x, l, r) -> Node(x, fall l, fall r);;

let rec spring v nt =
    match nt with
    | NNil -> NNode(v, [])
    | NNode(x, cs) -> NNode(x, lspring v cs);;


let rec lspring v l =
    match l with
    | [] -> []
    | t:ts -> spring v t :: lspring ts;;