Anotación de la profundidad de los nodos

José A. Alonso

12-02-2016

Los árboles binarios con datos en los nodos y hojas se definen por

data Arbol a = H
             | N a (Arbol a) (Arbol a)
             deriving (Eq, Show)

Por ejemplo, el árbol

       3
      / \
     /   \
    4     7
   / \   / \
  5   0 0   3
 / \
2   0

se representa por

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

        3-0
        / \
       /   \
      /     \
    4-1     7-1
    / \     / \
  5-2 0-2 0-2 3-0
  / \
2-3 0-3

Definir la función

anotado :: Arbol a -> Arbol (a,Int)

tal que (anotado x) es el árbol obtenido anotando los elementos de x con su profundidad. Por ejemplo,

λ> 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

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)