Menu Close

Padres como sumas de hijos

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

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

Por ejemplo, el árbol

         10
        /  \
       /    \
      8      2
     / \    / \
    3   5  2   0

se pueden representar por

   ejArbol :: Arbol Int
   ejArbol = N 10 (N 8 (H 3) (H 5))
                  (N 2 (H 2) (H 0))

Un árbol cumple la propiedad de la suma si el valor de cada nodo es igual a la suma de los valores de sus hijos. Por ejemplo, el árbol anterior cumple la propiedad de la suma.

Definir la función

   propSuma :: Arbol Int -> Bool

tal que (propSuma a) se verifica si el árbol a cumple la propiedad de la suma. Por ejemplo,

   λ> propSuma (N 10 (N 8 (H 3) (H 5)) (N 2 (H 2) (H 0)))
   True
   λ> propSuma (N 10 (N 8 (H 4) (H 5)) (N 2 (H 2) (H 0)))
   False
   λ> propSuma (N 10 (N 8 (H 3) (H 5)) (N 2 (H 2) (H 1)))
   False

Soluciones

data Arbol a = H a
             | N a (Arbol a) (Arbol a)
  deriving Show
 
ejArbol :: Arbol Int
ejArbol = N 10 (N 8 (H 3) (H 5))
               (N 2 (H 2) (H 0))
 
propSuma :: Arbol Int -> Bool
propSuma (H _)     = True
propSuma (N x i d) = x == raiz i + raiz d && propSuma i && propSuma d
 
raiz :: Arbol Int -> Int
raiz (H x)     = x
raiz (N x _ _) = x
Medio

4 soluciones de “Padres como sumas de hijos

  1. alerodrod5
    data Arbol a = H a
                    | N a (Arbol a) (Arbol a) 
         deriving (Eq, Show)
     
    propSuma :: Arbol Int -> Bool
    propSuma (H _) = True
    propSuma (N x a1 a2) = (valor a1 + valor a2) == x && propSuma a1 && propSuma a2
      where valor (H x ) = x
            valor (N x a1 a2) = x
  2. jaibengue
    data Arbol a = H a
                 | N a (Arbol a) (Arbol a)
                 deriving (Eq, Show)
     
    propSuma :: Arbol Int -> Bool
    propSuma (N n (N p a b) (N q c d)) = (n == p+q) && (propSuma (N p a b)) && (propSuma (N q c d))
    propSuma (N n (N p a b) (H q))     = (n == p+q) && (propSuma (N p a b))
    propSuma (N n (H p) (N q c d))     = (n == p+q) && (propSuma (N q c d))
    propSuma (N n (H p) (H q))         = (n == p+q)
    propSuma (H n)                     = True
  3. luiconbel

     
    
    data Arbol a = H a
                 | N a (Arbol a) (Arbol a) 
         deriving (Eq, Show)
    
    propSuma :: Arbol Int -> Bool
    propSuma (H a )    = True
    propSuma (N a i d) = a == sumaHojas (N a i d) && propSuma i && propSuma d
    
    sumaHojas :: Arbol Int -> Int
    sumaHojas (H a) = a
    sumaHojas (N a i d) = sumaHojas i + sumaHojas d
    
    

  4. antnavoro
    propSuma :: Arbol Int -> Bool
    propSuma (H _) = True
    propSuma (N a x@(N b _ _) y@(N e _ _)) = a==b+e && propSuma x && propSuma y
    propSuma (N a (H b) (H c)) = a==b+c
    propSuma (N a (H b) y@(N c _ _)) = a==b+c && propSuma y
    propSuma (N a x@(N b _ _) (H e)) = a==b+e && propSuma x

Escribe tu solución

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