Jump to content
  • 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

Recommended Posts

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) = ... 

Share this post


Link to post
Share on other 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).

Share this post


Link to post
Share on other 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

Share this post


Link to post
Share on other 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:

Share this post


Link to post
Share on other 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.

Share this post


Link to post
Share on other 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.

Share this post


Link to post
Share on other 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

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.