(*Definição de uma árvore binária em OCaml*)
type 'a tree = Nil | Node of 'a * 'a tree * 'a tree ;;


(*Criação da árvore myTree :  1 *)
(*                           2  3*)
let myTree = Node(1, Node(2, Nil,Nil), Node(3,Nil,Nil)) ;;

(*Criação da árvore treeA :   5 *)
(*                          4   3 *)
(*                         1 -  - 1 *)
(*                        2 3   2 3 *)
let treeA = Node(5, Node(4,myTree,Nil), Node(3,Nil,myTree)) ;;

(*Criação da árvore treeB :  (1,2) *)
(*                          (3,4)  (5,6)*)
let treeB = Node((1,2), Node((3,4), Nil,Nil), Node((5,6),Nil,Nil)) ;;

(*Criação da árvore treeC :  (1,2) *)
(*                          (3,3)  (5,5)*)
let treeC = Node((1,2), Node((3,3), Nil,Nil), Node((5,5),Nil,Nil)) ;;


 (*Conta número de ocorrências do valor na árvore *)
let rec howMany v t =
	match t with 
			Nil  -> 0
		| Node (x,l,r) -> (if x=v then 1 else 0) + howMany v l + howMany v r
;; 
(*teste do howMany*)
howMany 1 myTree ;;
howMany 3 myTree ;;
howMany 1 treeA;;
howMany 3 treeA;;


(*Numa árvore de pares ordenados (x,y), verifica se exitem elementos iguais, x=y*)
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
;;
(*Teste pares iguais*)
eqPairs treeB;;
eqPairs treeC;;


(*Pelo prof. Coloca a árvore numa lista*)
let rec treeToList t =
	match t with
			Nil -> []
		| Node(x,l,r) -> x:: treeToList l @ treeToList r
;;
(*Teste da lista*)
treeToList myTree ;;
treeToList treeA;;


(*Da aula teórica. Cálculo da altura de uma árvore.*)
let rec height t =
    match t with
       Nil -> 0
     | Node(x,l,r) ->
           1 + max (height l) (height r)
;;
(*Teste da altura*)
height myTree ;;
height treeA;;