Menu Close

Árboles continuos

José A. Alonso,

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

Medio
, , , , , , ,

5 soluciones de “Árboles continuos”

  1. Responder
    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. Responder
    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. Responder
    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. Responder
    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. Responder
    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.