Anotación de la profundidad de los nodos
Los árboles binarios con datos en los nodos y hojas se definen por
1 2 3 |
data Arbol a = H | N a (Arbol a) (Arbol a) deriving (Eq, Show) |
Por ejemplo, el árbol
1 2 3 4 5 6 7 8 |
3 / \ / \ 4 7 / \ / \ 5 0 0 3 / \ 2 0 |
se representa por
1 2 |
ejArbol :: Arbol Integer ejArbol = N 3 (N 4 (N 5 (H 2)(H 0)) (H 0)) (N 7 (H 0) (H 3)) |
Anotando cada elemento del árbol anterior con su profundidad, se obtiene el árbol siguiente
1 2 3 4 5 6 7 8 9 |
3-0 / \ / \ / \ 4-1 7-1 / \ / \ 5-2 0-2 0-2 3-0 / \ 2-3 0-3 |
Definir la función
1 |
anotado :: Arbol a -> Arbol (a,Int) |
tal que (anotado x) es el árbol obtenido anotando los elementos de x con su profundidad. Por ejemplo,
1 2 3 4 5 6 |
λ> anotado ejArbol N (3,0) (N (4,1) (N (5,2) (H (2,3)) (H (0,3))) (H (0,2))) (N (7,1) (H (0,2)) (H (3,2))) |
Soluciones
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
data Arbol a = H a | N a (Arbol a) (Arbol a) deriving (Eq, Show) ejArbol :: Arbol Integer ejArbol = N 3 (N 4 (N 5 (H 2)(H 0)) (H 0)) (N 7 (H 0) (H 3)) -- 1ª solución -- =========== anotado1 :: Arbol a -> Arbol (a,Int) anotado1 (H x) = H (x,0) anotado1 (N x i d) = aux (N x i d) 0 where aux (H x) n = H (x,n) aux (N x i d) n = N (x,n) (aux i (n+1)) (aux d (n+1)) -- 2ª solución anotado2 :: Arbol a -> Arbol (a, Int) anotado2 a = aux a [0..] where aux (H a) (n:_ ) = H (a,n) aux (N a i d) (n:ns) = N (a,n) (aux i ns) (aux d ns) |
4 Comentarios