Ir para o conteúdo
aalex

Varrer BTree não ordenada?

Mensagens Recomendadas

aalex    0
aalex

Viva, como consigo varrer uma uma BTree não ordenada a procura de um elemento?

se for ordenada é fácil, pois só faço uma chamada recursiva para a "esq" ou para a "dir". Mas se não for ordenada como a consigo agrupar essas 2 chamas recursivas?

lookupBT::(Eq a)=>(BTree (a,b))->a->Maybe b
lookupBT Vazia _ = Nothing
lookupBT (Nodo (a,b) esq dir) n | a==n = Just b
			| otherwise = (lookupBT esq n) (lookupBT dir n)

o problema esta no otherwise, como consigo "agrupar" essas duas chamas recursivas?

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
aalex    0
aalex

não testei mas parece-me que isso não vai funcionar

repara primeiro vou para a esquerda e depois para a direita

Fazes primeiro para um dos lados. Se o resultado for Nothing então fazes para o outro lado.

isso parece-me que não vai funcionar, pois só encontra se estiver sempre na esquerda ou sempre na direita

lookupBT::(Eq a)=>(BTree (a,b))->a->Maybe b
lookupBT Vazia _ = Nothing
lookupBT (Nodo (a,b) esq dir) n | a==n = Just b
			| x==Nothing = lookupBT dir n
			| otherwise = lookupBT esq n
				where
					x = case esq of
						Vazia -> Nothing
						Nodo (ea,ed) _ _ -> Just ea

esse é o código que desenvolvi, mas não varre toda a árvore...

sugestões?

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Betovsky    2
Betovsky
Em 1/7/2012 às 22:47, aalex disse:

isso parece-me que não vai funcionar, pois só encontra se estiver sempre na esquerda ou sempre na direita


lookupBT::(Eq a)=>(BTree (a,b))->a->Maybe b
lookupBT Vazia _ = Nothing
lookupBT (Nodo (a,b) esq dir) n | a==n = Just b
			| x==Nothing = lookupBT dir n
			| otherwise = lookupBT esq n
				where
					x = case esq of
						Vazia -> Nothing
						Nodo (ea,ed) _ _ -> Just ea
 

Se usares o let fica mais simples.

lookupBT::(Eq a)=>(BTree (a,b))->a->Maybe b
lookupBT Vazia _ = Nothing
lookupBT (Nodo (a,b) esq dir) n | a==n = Just b
			| otherwise = let resultEsq = lookupBT esq n
                                                          resultDir = lookupBT dir n
                                                     in . . . . a preencher o resto

Ou então podes usar uma função auxiliar para agregar os 2 Maybes. Possibilidades não faltam ;p

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
aalex    0
aalex

e se passares a árvore para uma lista? e depois percorres a lista

sim fiz isso e funcionou

Se usares o let fica mais simples.

lookupBT::(Eq a)=>(BTree (a,b))->a->Maybe b
lookupBT Vazia _ = Nothing
lookupBT (Nodo (a,b) esq dir) n | a==n = Just b
			| otherwise = let resultEsq = lookupBT esq n
                                                          resultDir = lookupBT dir n
                                                     in . . . . a preencher o resto

Ou então podes usar uma função auxiliar para agregar os 2 Maybes. Possibilidades não faltam ;p

Não sei porque, mas não gosto de usar o let aqui fica o código

o problema estava na falta do Eq b, pois na segunda guarda estou a testar a igualdade um b (resultado) com outra "variável"

lookupBT::(Eq a)=>(Eq b)=>(BTree (a,b))->a->Maybe b
lookupBT Vazia _ = Nothing
lookupBT (Nodo (a,b) esq dir) n | a==n = Just b
                               | resultEsq==Nothing = resultDir
			| otherwise = resultEsq
                                 where
                                    resultEsq = lookupBT esq n
                                    resultDir = lookupBT dir n

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Pedro Matos    0
Pedro Matos

Boa tarde.

O que acham desta solução?

existe :: (Eq a) => (BTree (a,b)) -> a -> Bool
existe Vazia _ = False
existe (Nodo (x,y) e d) n = (n == x) || existe e n || existe d n


lookupBT :: (Eq a) => (BTree (a,b)) -> a -> Maybe b
lookupBT Vazia _ = Nothing
lookupBT a@(Nodo (x,y) e d) n | (existe a n) = Just y
                             | otherwise = Nothing

Editado por Rui Carlos
GeSHi

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora


×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade