Construir Árvore Binária de Procura a Partir de uma Lista

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

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

[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

[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:

[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.

[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.

[Baderous]

Bem visto.

[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