Ampliación de árboles binarios
Representamos los árboles binarios mediante el tipo de dato
data Arbol a = H a | N a (Arbol a) (Arbol a) deriving Show
Una forma de ampliar un árbol binario es añadiendo un nuevo nivel donde las nuevas hojas sean iguales a la suma de los valores de los nodos desde el padre hasta llegar a la raíz (inclusives). Por ejemplo:
5 5 | 3 3
/ \ / \ | / \ / \
2 0 ==> 2 0 | 2 4 ==> 2 4
/ \ / \ | / \ / \ / \
7 7 5 5 | 0 1 0 1 7 7
/\ /\
5 5 6 6
Definir la función
ampliaArbol:: Num a => Arbol a -> Arbol a
tal que (ampliaArbol a) es el árbol a ampliado en un nivel. Por ejemplo,
λ> ampliaArbol (N 5 (H 2)(H 0)) N 5 (N 2 (H 7) (H 7)) (N 0 (H 5) (H 5)) λ> ampliaArbol (N 3 (N 2 (H 0) (H 1)) (H 4)) N 3 (N 2 (N 0 (H 5) (H 5)) (N 1 (H 6) (H 6))) (N 4 (H 7) (H 7)) λ> ampliaArbol (H 1) N 1 (H 1) (H 1) λ> ampliaArbol N 1 (H 1) (H 1) N 1 (N 1 (H 2) (H 2)) (N 1 (H 2) (H 2))
Soluciones
data Arbol a = H a | N a (Arbol a) (Arbol a) deriving Show ampliaArbol :: Num a => Arbol a -> Arbol a ampliaArbol a = aux 0 a where aux n (H x) = N x (H (n+x)) (H (n+x)) aux n (N x i d) = N x (aux (n+x) i) (aux (n+x) d)