Numeración de los árboles binarios completos
Un árbol binario completo es un árbol binario que tiene todos los nodos posibles hasta el penúltimo nivel, y donde los elementos del último nivel están colocados de izquierda a derecha sin dejar huecos entre ellos.
La numeración de los árboles binarios completos se realiza a partir de la raíz, recorriendo los niveles de izquierda a derecha. Por ejemplo,
1
/ \
/ \
/ \
2 3
/ \ / \
4 5 6 7
/ \
8 9
Los árboles binarios se puede representar mediante el siguiente tipo
data Arbol = H | N Int Arbol Arbol deriving (Show, Eq)
Definir la función
arbolBinarioCompleto :: Int -> Arbol
tal que (arbolBinarioCompleto n) es el árbol binario completo con n nodos. Por ejemplo,
λ> arbolBinarioCompleto 4 N 1 (N 2 (N 4 H H) H) (N 3 H H) λ> arbolBinarioCompleto 9 N 1 (N 2 (N 4 (N 8 H H) (N 9 H H)) (N 5 H H)) (N 3 (N 6 H H) (N 7 H H))
Soluciones
data Arbol = H | N Int Arbol Arbol deriving (Eq, Show) arbolBinarioCompleto :: Int -> Arbol arbolBinarioCompleto n = aux 1 where aux i | i <= n = N i (aux (2*i)) (aux (2*i+1)) | otherwise = H