----------------------------------------------------------------
--O tipo de dados Arv e' uma arvore que possui tres sub-arvores
-- em cada no', ao inves de duas como em arvores binarias.

data Arv a = No (Arv a) (Arv a) (Arv a)
           | Folha a
           deriving (Show)

-- exemplo de Arv:
testearv :: Arv Int
testearv = No (No (Folha 2) (Folha 3) (Folha 4))
              (No (Folha 8) 
                  (No (Folha 9) (Folha 10) (Folha  11))
                  (Folha 20)
              )
              (No (Folha  90) (Folha  100) (Folha  150))


--(2.0) Faca uma funcao que retorne o elemento na folha mais a esquerda 
--de uma Arv
--leftmost :: Arv a -> a

--(2.0) Faca uma funcao que retorne, em ordem, todos os elementos de uma Arv.
--elementos :: Arv a -> [a]
-- exemplo:
-- elementos testearv = [2,3,4,8,9,10,11,20,90,100,150]

--(2.0) Faca uma funcao que retorne a imagem invertida de uma arvore,
--      i.e. com os elementos originalmente a esquerda `a direita e vice-versa
--inv :: Arv a -> Arv a
-- exemplo: inv testearv =
--           No (No (Folha  150) (Folha  100) (Folha  90))
--              (No (Folha 20) 
--                  (No (Folha 11) (Folha 10) (Folha  9))
--                  (Folha 8)
--              )
--              (No (Folha 4) (Folha 3) (Folha 2))

--(2.0) Prove que 
--      inv (inv x) = x

--(2.0) faca uma funcao que dado um caminho indicando a sub-arvore que
-- se deseja seguir, retorna aquela sub-arvore, onde L e' a sub-arvore
-- a esquerda, M a do meio e R a da direita
data Caminho = L | M | R deriving (Show)
--seguecaminho :: [Caminho] -> Arv a -> Arv a

-- exemplo: 
-- seguecaminho [M,M,R] testearv = folha 11
-- seguecaminho [M,M] testearv = (No (Folha 9) (Folha 10) (Folha  11))