Subárboles monovalorados

PorJosé A. Alonso 19-noviembre-201525-abril-2021

Los árboles binarios con valores enteros se pueden representar mediante el tipo Arbol definido por

   data Arbol = H Int 
              | N Int Arbol Arbol
              deriving Show

data Arbol = H Int

| N Int Arbol Arbol

deriving Show

Por ejemplo, el árbol

         7
        / \ 
       /   \
      /     \
     4       9
    / \     / \
   1   3   5   6

/ \

4 9

/ \ / \

1 3 5 6

se puede representar por

   N 7 (N 4 (H 1) (H 3)) (N 9 (H 5) (H 6))

1	N 7 (N 4 (H 1) (H 3)) (N 9 (H 5) (H 6))

Un árbol es monovalorado si todos sus elementos son iguales. Por ejemplo, de los siguientes árboles sólo son monovalorados los dos primeros

    5          9           5          9    
   / \        / \         / \        / \   
  5   5      9   9       5   6      9   7  
                / \                    / \ 
               9   9                  9   9

5 9 5 9

/ \ / \ / \ / \

5 5 9 9 5 6 9 7

/ \ / \

9 9 9 9

Definir la función

   monovalorados :: Arbol -> [Arbol]

1	monovalorados :: Arbol -> [Arbol]

tal que (monovalorados a) es la lista de los subárboles monovalorados de a. Por ejemplo,

   λ> monovalorados (N 5 (H 5) (H 5))
   [N 5 (H 5) (H 5),H 5,H 5]
   λ> monovalorados (N 5 (H 5) (H 6))
   [H 5,H 6]
   λ> monovalorados (N 9 (H 9) (N 9 (H 9) (H 9)))
   [N 9 (H 9) (N 9 (H 9) (H 9)),H 9,N 9 (H 9) (H 9),H 9,H 9]
   λ> monovalorados (N 9 (H 9) (N 7 (H 9) (H 9)))
   [H 9,H 9,H 9]
   λ> monovalorados (N 9 (H 9) (N 9 (H 7) (H 9)))
   [H 9,H 7,H 9]

λ> monovalorados (N 5 (H 5) (H 5))

[N 5 (H 5) (H 5),H 5,H 5]

λ> monovalorados (N 5 (H 5) (H 6))

[H 5,H 6]

λ> monovalorados (N 9 (H 9) (N 9 (H 9) (H 9)))

[N 9 (H 9) (N 9 (H 9) (H 9)),H 9,N 9 (H 9) (H 9),H 9,H 9]

λ> monovalorados (N 9 (H 9) (N 7 (H 9) (H 9)))

[H 9,H 9,H 9]

λ> monovalorados (N 9 (H 9) (N 9 (H 7) (H 9)))

[H 9,H 7,H 9]

Soluciones

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

monovalorados :: Arbol -> [Arbol]
monovalorados (H x) = [H x]
monovalorados (N x i d) 
    | todosIguales i x && todosIguales d x =
        (N x i d) : (subarboles i ++ subarboles d)
    | otherwise = monovalorados i ++ monovalorados d

-- (todosIguales a x) se verifica si todos los valores de los nodos y
-- las hojas del árbol a son iguales a x.
todosIguales :: Arbol -> Int -> Bool
todosIguales (H y) x     = y == x
todosIguales (N y i d) x = y == x && todosIguales i x && todosIguales d x

-- (subarboles a) es la lista de los subárboles de a.
subarboles :: Arbol -> [Arbol]
subarboles (H x)     = [H x]
subarboles (N x i d) = (N x i d) : (subarboles i ++ subarboles d)

data Arbol = H Int

| N Int Arbol Arbol

deriving (Show, Eq)

monovalorados :: Arbol -> [Arbol]

monovalorados (H x) = [H x]

monovalorados (N x i d)

| todosIguales i x && todosIguales d x =

(N x i d) : (subarboles i ++ subarboles d)

| otherwise = monovalorados i ++ monovalorados d

-- (todosIguales a x) se verifica si todos los valores de los nodos y

-- las hojas del árbol a son iguales a x.

todosIguales :: Arbol -> Int -> Bool

todosIguales (H y) x = y == x

todosIguales (N y i d) x = y == x && todosIguales i x && todosIguales d x

-- (subarboles a) es la lista de los subárboles de a.

subarboles :: Arbol -> [Arbol]

subarboles (H x) = [H x]

subarboles (N x i d) = (N x i d) : (subarboles i ++ subarboles d)

5 Comentarios

data Arbol = H Int 
           | N Int Arbol Arbol
           deriving Show

monovalorados :: Arbol -> [Arbol]
monovalorados z@(H _)     = [z]
monovalorados z@(N n a b) | todosIgualA n z     = z : zs
                          | otherwise           = zs 
    where zs = monovalorados a ++ monovalorados b

todosIgualA :: Int -> Arbol -> Bool
todosIgualA k (H n)     = k == n
todosIgualA k (N n a b) = (k == n) && todosIgualA k a && todosIgualA k b

data Arbol = H Int

| N Int Arbol Arbol

deriving Show

monovalorados :: Arbol -> [Arbol]

monovalorados z@(H _) = [z]

monovalorados z@(N n a b) | todosIgualA n z = z : zs

| otherwise = zs

where zs = monovalorados a ++ monovalorados b

todosIgualA :: Int -> Arbol -> Bool

todosIgualA k (H n) = k == n

todosIgualA k (N n a b) = (k == n) && todosIgualA k a && todosIgualA k b

Responder

-- Convierte un arbol en una lista de números
arbToInt :: Arbol -> [Int]
arbToInt (H n) = [n]
arbToInt (N n ai ad) = n:(arbToInt ai) ++ (arbToInt ad) 

-- Comprueba si todos los enteros de un arbol son iguales, y los añade o
-- no al resultado de la función.
monovalorados :: Arbol -> [Arbol]
monovalorados (H n) = [H n]
monovalorados (N n ai ad) 
          | all (head arbInt ==) arbInt = [arbArb] ++ monovalorados ai
                                         ++ monovalorados ad
          | otherwise                   = monovalorados ai 
                                         ++ monovalorados ad
         where arbInt = arbToInt arbArb
               arbArb = (N n ai ad)

-- Convierte un arbol en una lista de números

arbToInt :: Arbol -> [Int]

arbToInt (H n) = [n]

arbToInt (N n ai ad) = n:(arbToInt ai) ++ (arbToInt ad)

-- Comprueba si todos los enteros de un arbol son iguales, y los añade o

-- no al resultado de la función.

monovalorados :: Arbol -> [Arbol]

monovalorados (H n) = [H n]

monovalorados (N n ai ad)

| all (head arbInt ==) arbInt = [arbArb] ++ monovalorados ai

++ monovalorados ad

| otherwise = monovalorados ai

++ monovalorados ad

where arbInt = arbToInt arbArb

arbArb = (N n ai ad)

Responder

-- Mejora de la eficiencia, introduciendo el hecho de que una vez que un
-- arbol sea completamente monovalorado, no se compruebe más si los 
-- subarboles lo son.
monovalorados :: Arbol -> [Arbol]
monovalorados arb = aux False arb
 where aux :: Bool -> Arbol -> [Arbol]
       aux True (H n) = [H n]
       aux True arbArb@(N n ai ad) = arbArb : aux True ai ++ aux True ad
       aux False (H n) = [H n]
       aux False arbArb@(N n ai ad) 
         | all (n ==) (arbToInt arbArb) = arbArb : aux True ai ++ aux True ad
         | otherwise                    = aux False ai ++ aux False ad

-- Mejora de la eficiencia, introduciendo el hecho de que una vez que un

-- arbol sea completamente monovalorado, no se compruebe más si los

-- subarboles lo son.

monovalorados :: Arbol -> [Arbol]

monovalorados arb = aux False arb

where aux :: Bool -> Arbol -> [Arbol]

aux True (H n) = [H n]

aux True arbArb@(N n ai ad) = arbArb : aux True ai ++ aux True ad

aux False (H n) = [H n]

aux False arbArb@(N n ai ad)

| all (n ==) (arbToInt arbArb) = arbArb : aux True ai ++ aux True ad

| otherwise = aux False ai ++ aux False ad

Responder

-- La primera y la tercera ecuación son simplificables
monovalorados :: Arbol -> [Arbol]
monovalorados arb = aux False arb
 where aux :: Bool -> Arbol -> [Arbol]
       aux _ (H n) = [H n]
       aux True arbArb@(N n ai ad) = arbArb : aux True ai ++ aux True ad
       aux False arbArb@(N n ai ad) 
         | all (n ==) (arbToInt arbArb) = arbArb : aux True ai ++ aux True ad
         | otherwise                    = aux False ai ++ aux False ad

-- La primera y la tercera ecuación son simplificables

monovalorados :: Arbol -> [Arbol]

monovalorados arb = aux False arb

where aux :: Bool -> Arbol -> [Arbol]

aux _ (H n) = [H n]

aux True arbArb@(N n ai ad) = arbArb : aux True ai ++ aux True ad

aux False arbArb@(N n ai ad)

| all (n ==) (arbToInt arbArb) = arbArb : aux True ai ++ aux True ad

| otherwise = aux False ai ++ aux False ad

Responder

-- Devuelve el valor del nodo raíz de un árbol
valor :: Arbol -> Int
valor (N x _ _) = x
valor (H x    ) = x

-- Itera todos los subárboles de un árbol
iterarArbol :: (Arbol -> a) -> Arbol -> [a]
iterarArbol f n@(N _ a b) =  f n: iterarArbol f a ++ iterarArbol f b
iterarArbol f h           = [f h]

-- La función solicitada
monovalorados :: Arbol -> [Arbol]
monovalorados = filter (null.drop 1.nub.iterarArbol valor) . iterarArbol id

-- Devuelve el valor del nodo raíz de un árbol

valor :: Arbol -> Int

valor (N x _ _) = x

valor (H x ) = x

-- Itera todos los subárboles de un árbol

iterarArbol :: (Arbol -> a) -> Arbol -> [a]

iterarArbol f n@(N _ a b) = f n: iterarArbol f a ++ iterarArbol f b

iterarArbol f h = [f h]

-- La función solicitada

monovalorados :: Arbol -> [Arbol]

monovalorados = filter (null.drop 1.nub.iterarArbol valor) . iterarArbol id

Responder

Subárboles monovalorados

Soluciones

5 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

5 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico