Menu Close

Anotación de la profundidad de los nodos

José A. Alonso,

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)
Medio
,

4 soluciones de “Anotación de la profundidad de los nodos”

  1. Responder
    carruirui3 
    data Arbol a = H a 
             | N a (Arbol a) (Arbol a) 
             deriving (Eq, Show)
 
anotado :: Arbol a -> Arbol (a,Int)
anotado = anotadoAux 0
          where anotadoAux n (H x)     = H (x,n)
                anotadoAux n (N x a b) = N (x,n)
                                           (anotadoAux (n+1) a)
                                           (anotadoAux (n+1) b)
  2. Responder
    fracruzam 
    anotado :: Arbol a -> Arbol (a,Int)
anotado = aux 0
 
aux :: Enum a => a -> Arbol b -> Arbol (b,a)
aux n (H a) = H (a,n)
aux n (N a i d) = N (a,n) (aux (succ n) i) (aux (succ n) d)
  3. Responder
    manpende 
    anotado3 :: Arbol a -> Arbol (a, Int)
anotado3 (H a) = H (a,0)
anotado3 (N a ai ad) = N (a,0)  (anotado' ai)  (anotado' ad)
 
anotado' :: Arbol t -> Arbol (t,Int)
anotado' = suma1 . anotado3
 
suma1 :: Num t1 => Arbol (t, t1) -> Arbol (t, t1)
suma1 (H (a,n)) = H (a, n+1)
suma1 (N (a,n) ai ad) = (N (a,n+1)) (suma1 ai) (suma1 ad)
  4. Responder
    josejuan 
    zip' :: Arbol a → [b] → Arbol (a, b)
zip' (H a    ) (b:_ ) = H (a, b)
zip' (N a l r) (b:bs) = N (a, b) (zip' l bs) (zip' r bs)
 
anotado :: Arbol a → Arbol (a, Int)
anotado a = zip' a [0…]

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.