Menu Close

Árboles continuos

Los árboles binarios se pueden representar con el de tipo de dato algebraico

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

Por ejemplo, los árboles

       3                7     
      / \              / \    
     2   4            5   8   
    / \   \          / \   \  
   1   3   5        6   4   10

se representan por

   ej1, ej2 :: Arbol Int
   ej1 = N 3 (N 2 (N 1 H H) (N 3 H H)) (N 4 H (N 5 H H))
   ej2 = N 7 (N 5 (N 6 H H) (N 4 H H)) (N 8 H (N 10 H H))

Un árbol binario es continuo si el valor absoluto de la diferencia de los elementos adyacentes es 1. Por ejemplo, el árbol ej1 es continuo ya que el valor absoluto de sus pares de elementos adyacentes son

   |3-2| = |2-1| = |2-3| = |3-4| = |4-5| = 1

En cambio, el ej2 no lo es ya que |8-10| ≠ 1.

Definir la función

   esContinuo :: (Num a, Eq a) => Arbol a -> Bool

tal que (esContinuo x) se verifica si el árbol x es continuo. Por ejemplo,

   esContinuo ej1  ==  True
   esContinuo ej2  ==  False

Soluciones

data Arbol a = H
             | N a (Arbol a) (Arbol a)
  deriving Show
 
ej1, ej2 :: Arbol Int
ej1 = N 3 (N 2 (N 1 H H) (N 3 H H)) (N 4 H (N 5 H H))
ej2 = N 7 (N 5 (N 6 H H) (N 4 H H)) (N 8 H (N 10 H H))
 
-- 1ª solución
-- ===========
 
esContinuo :: (Num a, Eq a) => Arbol a -> Bool
esContinuo H         = True
esContinuo (N _ H H) = True
esContinuo (N x i@(N y _ _) H) =
  abs (x - y) == 1 && esContinuo i
esContinuo (N x H d@(N y _ _)) =
  abs (x - y) == 1 && esContinuo d
esContinuo (N x i@(N y _ _) d@(N z _ _)) =
  abs (x - y) == 1 && esContinuo i && abs (x - z) == 1 && esContinuo d 
 
-- 2ª solución
-- ===========
 
esContinuo2 :: (Num a, Eq a) => Arbol a -> Bool
esContinuo2 x =
  all esContinua (ramas x)
 
-- (ramas x) es la lista de las ramas del árbol x. Por ejemplo,
--    ramas ej1  ==  [[3,2,1],[3,2,3],[3,4,5]]
--    ramas ej2  ==  [[7,5,6],[7,5,4],[7,8,10]]
ramas :: Arbol a -> [[a]]
ramas H         = []
ramas (N x H H) = [[x]]
ramas (N x i d) = [x : xs | xs <- ramas i ++ ramas d]
 
-- (esContinua xs) se verifica si el valor absoluto de la diferencia de
-- los elementos adyacentes de xs es 1. Por ejemplo, 
--    esContinua [3,2,3]   ==  True
--    esContinua [7,8,10]  ==  False
esContinua :: (Num a, Eq a) => [a] -> Bool
esContinua xs =
  and [abs (x - y) == 1 | (x, y) <- zip xs (tail xs)]

Referencias

5 soluciones de “Árboles continuos

  1. Fran Cruz
    esContinuo :: (Num a, Eq a) => Arbol a -> Bool
    esContinuo (N x a1@(N y _ _) a2@(N z _ _)) =
      abs (x-y) == 1 && abs (x-z) == 1 && esContinuo a1 && esContinuo a2
    esContinuo (N x a1@(N y _ _) _           ) =
      abs (x-y) == 1 && esContinuo a1
    esContinuo (N x _            a2@(N z _ _)) =
      abs (x-z) == 1 && esContinuo a2
    esContinuo  _ = True
  2. enrnarbej
    esContinuo :: (Num a, Eq a) => Arbol a -> Bool
    esContinuo (N a (N b x1 x2) (N c y1 y2)) =
      abs (a-b) == 1 && abs (a-c) == 1 &&
      esContinuo (N b x1 x2) && esContinuo (N c y1 y2)
    esContinuo (N a  H (N c y1 y2)) =
      abs (a-c) == 1 && esContinuo (N c y1 y2)
    esContinuo (N a (N b x1 x2)  H) =
      abs (a-b) == 1 && esContinuo (N b x1 x2)
    esContinuo _ = True
  3. eliguivil
    esContinuo :: (Num a, Eq a) => Arbol a -> Bool
    esContinuo (N x i d) = aux x i && aux x d
      where
        aux _ H         = True
        aux x (N y i d) = 1 == abs (x-y) && aux y i && aux y d
  4. albcercid
    esContinuo :: (Num a, Eq a) => Arbol a -> Bool                                
    esContinuo H = True
    esContinuo (N a x y) = r a x && r a y && esContinuo x && esContinuo y
      where r a H         = True
            r a (N b x y) = abs (a-b) == 1
  5. Chema Cortés
    data Arbol a = H
                 | N a (Arbol a) (Arbol a)
                 deriving Show
     
    esContinuo :: (Num a, Eq a) => Arbol a -> Bool
    esContinuo H          = True
    esContinuo (N x i d)  = and $ [f x, esContinuo] <*> [i,d]
      where
        f _ H         = True
        f y (N z _ _) = abs (y-z) == 1

Escribe tu solución

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