0

É habitual definirem-se árvores em que a informação está apenas nas extermidades (leaf trees):

data LTree a = Tip a | Fork (LTree a) (LTree a)

Defina sobre este tipo a seguinte função:

ltHeight :: LTree a -> Int que calcula a altura de uma árvore.

1 Resposta 1

0

Usando recursividade, normalmente a solução passa por considerar:

  • Árvore sem nós (caso trivial)
  • Árvore com nós (caso recursivo)

O tamanho de uma árvore sem nós, ie, apenas a folha, é 0. Como calcular o tamanho de uma árvore com vários nós? Simples, é 1 mais o tamanho da sub-árvore de maior altura.

Sabendo isto, a implementação é simples:

ltHeight :: LTree a -> Int
ltHeight (Tip l)    = 0                                 -- Caso trivial
ltHeight (Fork e d) = 1 + max (ltHeight e) (ltHeight d) -- 1 + altura da maior sub-arvore

Fica aqui o link para um exemplo:

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .