Exercício sobre árvores

[Anne Bathory 0]

Olá, tenho uma lista para entregar em Janeiro e travei nesse exercício, se alguém puder me ajudar, ficarei muito grata!!

 

3. Seja a definição abaixo para uma estrutura de dados em árvore binária de busca.

data ArvBinInt = Nil | NoInt Int ArvBinInt ArvBinInt deriving Show
arvDados::ArvBinInt
arvDados = NoInt 7 (NoInt 5 (NoInt 2 Nil Nil) (NoInt 6 Nil Nil))
(NoInt 13 (NoInt 9 Nil Nil) (NoInt 20 Nil (NoInt 23 Nil Nil)))

Faça funções para:

a1) verificar se uma árvore é vazia

a2) retornar a sub-árvore à esquerda de um nó (raiz da árvore)

a3) inserir ordenadamente um novo elemento (repetições devem ser evitadas)

 

b ) Seja a função abaixo de retorno e remoção do maior elemento. Verifique se está correta e caso necessário faça as devidas correções. Explique a estratégia a ser utilizada na remoção de um elemento qualquer em árvore binária de busca.

deletemax :: ArvBinInt -> (Int,ArvBinInt)
deletemax (NoInt y t1 Nil) = (y,t1)
deletemax (NoInt y t1 t2) = (z, NoInt y t1 tz)
                             where (z,tz) = deletemax t2

[VictorCacciari 42]

a1) verificar se uma árvore é vazia

Ahh, essa é fácil, aposto que você consegue fazer!

Uma arvore é vazia quando é um "Nil", não é?

Então:

arvVazia :: ArvBinInt -> Bool
arvVazia Nil = True
arvVazia _ = False

a2) retornar a sub-árvore à esquerda de um nó (raiz da árvore)

A sua estrutura da dados denominada "ArvBinInt" organiza três parâmetros.

O valor do nó, a árvore da esquerda e a árvora da direita...

Se você receber uma árvore vazia, retorne uma árvore vazia.

Se você receber uma árvore que não é vazia, apenas retorne a sub-árvore da esquerda.

 

a3) inserir ordenadamente um novo elemento (repetições devem ser evitadas)

Aconselho ler: http://pt.wikipedia.org/wiki/%C3%81rvore_bin%C3%A1ria

Após uma leitura, tente novamente.

Tenho certeza que conseguirá! http://forum.imasters.com.br/public/style_emoticons/default/natal_noel.gif http://forum.imasters.com.br/public/style_emoticons/default/natal_biggrin.gif