Ampliación de árboles binarios
Representamos los árboles binarios mediante el tipo de dato
|
1 2 3 |
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:
|
1 2 3 4 5 6 7 |
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
|
1 |
ampliaArbol:: Num a => Arbol a -> Arbol a |
tal que (ampliaArbol a) es el árbol a ampliado en un nivel. Por
ejemplo,
|
1 2 3 4 5 6 7 8 |
λ> 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
|
1 2 3 4 5 6 7 8 |
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) |
Un comentario