Ir para o conteúdo
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

luchhozito

Construir Árvore binaria de Procura a partir de uma lista

Mensagens Recomendadas

luchhozito

eu tenho uma lista ordenada por ordem crescente.

Queria construir uma árvore binária de procura.

Mas não estou a conseguir.

montarA :: [int] -> Abin Int
montarA [] = Vazia
montarA [x] = (No x Vazia Vazia)
montarA (x:xs) = ... 

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Baderous

Define uma função auxiliar que, dada uma árvore e um elemento, insere o elemento na árvore. Depois noutra função apenas tens de percorrer a lista, e inserir cada elemento numa árvore que inicialmente está Vazia, usando a função auxiliar, e vais construindo a árvore (usa o foldr/foldl).

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
luchhozito

Define uma função auxiliar que, dada uma árvore e um elemento, insere o elemento na árvore. Depois noutra função apenas tens de percorrer a lista, e inserir cada elemento numa árvore que inicialmente está Vazia, usando a função auxiliar, e vais construindo a árvore (usa o foldr/foldl).

foldr e foldl não me ageito.

vou tentar

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
luchhozito

insereAux :: Int -> ABin Int -> ABin Int
insereAux x Vazia  = (No x Vazia Vazia)
insereAux n (No x esq dir) | (n == x) = (No x esq dir)
					| (n < x) = No x (insereAux n esq) dir
					| (n > x) = No x dir (insereAux n esq)

montar :: [int] -> ABin Int -> ABin Int
montar [] Vazia = Vazia
montar [x] Vazia = No x Vazia Vazia
montar (x:xs) a@(Vazia) = insereAux x a   

Agora só não sei como a recursividade na função montar ao xs  :bored:

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Baderous

montar :: [int] -> ABin Int -> ABin Int
montar [] x = x
montar xs a = foldl (\x y -> insereAux y x) a xs

criaArvore :: [int] -> ABin Int
criaArvore lista = montar lista Vazia

O foldl é que vai construir a árvore (inicialmente Vazia, como indicado na função criaArvore) com os sucessivos valores da lista.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
Rui Carlos

Essa abordagem não é muito boa, pois não tira partido da lista já estar ordenada, e, pior do que isso, constrói uma árvore que pouco mais será do que uma lista (os elementos serão sempre inseridos na extremidade mais à direita, resultando numa árvore sem qualquer ramificação).

Em vez disso, penso que devias criar uma função que selecciona o elemento do meio da lista para raiz da árvore, e constrói as sub-árvores chamando recursivamente a função, com os elementos da direita e da esquerda como argumento.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
luchhozito

Essa abordagem não é muito boa, pois não tira partido da lista já estar ordenada, e, pior do que isso, constrói uma árvore que pouco mais será do que uma lista (os elementos serão sempre inseridos na extremidade mais à direita, resultando numa árvore sem qualquer ramificação).

Em vez disso, penso que devias criar uma função que selecciona o elemento do meio da lista para raiz da árvore, e constrói as sub-árvores chamando recursivamente a função, com os elementos da direita e da esquerda como argumento.

vou tentar fazer isso

Partilhar esta mensagem


Ligação 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. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.