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 |
1 / \ / \ / \ 2 3 / \ / \ 4 5 6 7 / \ 8 9 |
Los árboles binarios se puede representar mediante el siguiente tipo
|
1 2 3 |
data Arbol = H | N Int Arbol Arbol deriving (Show, Eq) |
Definir la función
|
1 |
arbolBinarioCompleto :: Int -> Arbol |
tal que (arbolBinarioCompleto n) es el árbol binario completo con n
nodos. Por ejemplo,
|
1 2 3 4 5 6 7 8 9 10 11 12 |
λ> 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
|
1 2 3 4 5 6 7 8 |
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 |
Pensamiento
– Ya se oyen palabras viejas.
– Pues aguzad las orejas.Antonio Machado