Árboles

Máxima distancia en árbol

PorJosé A. Alonso 29-enero-20185-febrero-2018

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)

data Arbol a = H a

| N a (Arbol a) (Arbol a)

deriving (Eq, Show)

Por ejemplo, el árbol

         10
        /  \
       /    \
      8      1
     / \    / \
    3   9  2   6

/ \

8 1

/ \ / \

3 9 2 6

se puede representar por

   ejArbol :: Arbol Int
   ejArbol = N 10 (N 8 (H 3) (H 9))
                  (N 1 (H 2) (H 6))

ejArbol :: Arbol Int

ejArbol = N 10 (N 8 (H 3) (H 9))

(N 1 (H 2) (H 6))

La distancia entre un padre y un hijo en el árbol es el valor absoluto de la diferencia de sus valores. Por ejemplo, la distancia de 10 a 8 es 2 y de 1 a 6 es 5.

Definir la función

   maximaDistancia :: (Num a, Ord a) => Arbol a -> a

1	maximaDistancia :: (Num a, Ord a) => Arbol a -> a

tal que (maximaDistancia a) es la máxima distancia entre un padre y un hijo del árbol a. Por ejemplo,

   maximaDistancia ejArbol                                     ==  9
   maximaDistancia (N 1 (N 8 (H 3) (H 9)) (N 1  (H 2) (H 6)))  ==  7
   maximaDistancia (N 8 (N 8 (H 3) (H 9)) (N 10 (H 2) (H 6)))  ==  8

maximaDistancia ejArbol == 9

maximaDistancia (N 1 (N 8 (H 3) (H 9)) (N 1 (H 2) (H 6))) == 7

maximaDistancia (N 8 (N 8 (H 3) (H 9)) (N 10 (H 2) (H 6))) == 8

Soluciones

[schedule expon=’2018-02-05′ expat=»06:00″]

Las soluciones se pueden escribir en los comentarios hasta el 05 de febrero.
El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>

[/schedule]

[schedule on=’2018-02-05′ at=»06:00″]

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

ejArbol :: Arbol Int
ejArbol = N 10 (N 8 (H 3) (H 9))
               (N 1 (H 2) (H 6))


maximaDistancia :: (Num a, Ord a) => Arbol a -> a
maximaDistancia (H _)     = 0
maximaDistancia (N x i d) = maximum [abs (x - raiz i)
                                    , maximaDistancia i
                                    , abs (x - raiz d)
                                    , maximaDistancia d]
                             
raiz :: Arbol a -> a
raiz (H x)     = x
raiz (N x _ _) = x

data Arbol a = H a

| N a (Arbol a) (Arbol a)

deriving Show

ejArbol :: Arbol Int

ejArbol = N 10 (N 8 (H 3) (H 9))

(N 1 (H 2) (H 6))

maximaDistancia :: (Num a, Ord a) => Arbol a -> a

maximaDistancia (H _) = 0

maximaDistancia (N x i d) = maximum [abs (x - raiz i)

, maximaDistancia i

, abs (x - raiz d)

, maximaDistancia d]

raiz :: Arbol a -> a

raiz (H x) = x

raiz (N x _ _) = x

[/schedule]

Relación definida por un árbol

PorJosé A. Alonso 26-enero-20182-febrero-2018

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)

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

/ \

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

ejArbol :: Arbol Int

ejArbol = N 10 (N 8 (H 3) (H 5))

(N 2 (H 2) (H 0))

Un árbol binario define una relación binaria donde un elemento x está relacionado con y si x es el padre de y. Por ejemplo, la relación definida por el árbol anterior es [(10,8),(8,3),(8,5),(10,2),(2,2),(2,0)].

Definir la función

   relacionDelArbol :: Arbol a -> [(a,a)]

1	relacionDelArbol :: Arbol a -> [(a,a)]

tal que (relacionDelArbol a) es la relación binaria definida por el árbol a. Por ejemplo,

   λ> relacionDelArbol ejArbol
   [(10,8),(8,3),(8,5),(10,2),(2,2),(2,0)]
   λ> relacionDelArbol (N 10 (H 8) (N 2 (H 2) (H 0)))
   [(10,8),(10,2),(2,2),(2,0)]
   λ> relacionDelArbol (N 10 (N 8 (H 3) (H 5)) (H 2))
   [(10,8),(8,3),(8,5),(10,2)]
   λ> relacionDelArbol (H 10)
   []

λ> relacionDelArbol ejArbol

[(10,8),(8,3),(8,5),(10,2),(2,2),(2,0)]

λ> relacionDelArbol (N 10 (H 8) (N 2 (H 2) (H 0)))

[(10,8),(10,2),(2,2),(2,0)]

λ> relacionDelArbol (N 10 (N 8 (H 3) (H 5)) (H 2))

[(10,8),(8,3),(8,5),(10,2)]

λ> relacionDelArbol (H 10)

[]

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

relacionDelArbol :: Arbol a -> [(a,a)]
relacionDelArbol (H _)     = []
relacionDelArbol (N x i d) = ((x,raiz i) : relacionDelArbol i) ++ 
                             ((x,raiz d) : relacionDelArbol d)
                             
raiz :: Arbol a -> a
raiz (H x)     = x
raiz (N x _ _) = x

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

relacionDelArbol :: Arbol a -> [(a,a)]

relacionDelArbol (H _) = []

relacionDelArbol (N x i d) = ((x,raiz i) : relacionDelArbol i) ++

((x,raiz d) : relacionDelArbol d)

raiz :: Arbol a -> a

raiz (H x) = x

raiz (N x _ _) = x

Padres como sumas de hijos

PorJosé A. Alonso 5-enero-201819-febrero-2018

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)

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

/ \

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

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

1	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

λ> 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

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

Recorrido por niveles de árboles binarios

PorJosé A. Alonso 27-diciembre-201719-febrero-2018

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)

data Arbol a = H a

| N a (Arbol a) (Arbol a)

deriving (Eq, Show)

Por ejemplo, el árbol

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

/ \

2 3

/ \ / \

4 5 6 7

/ \

8 9

se pueden representar por

   ejArbol :: Arbol Int
   ejArbol = N 1 (N 2 (H 4)
                      (N 5 (H 8) (H 9)))
                 (N 3 (H 6) (H 7))

ejArbol :: Arbol Int

ejArbol = N 1 (N 2 (H 4)

(N 5 (H 8) (H 9)))

(N 3 (H 6) (H 7))

Definir la función

   recorrido :: Arbol t -> [t]

1	recorrido :: Arbol t -> [t]

tal que (recorrido a) es el recorrido del árbol a por niveles desde la raíz a las hojas y de izquierda a derecha. Por ejemplo,

   λ> recorrido (N 1 (N 2 (H 4) (N 5 (H 8) (H 9))) (N 3 (H 6) (H 7)))
   [1,2,3,4,5,6,7,8,9]
   λ> recorrido (N 1 (N 3 (H 6) (H 7)) (N 2 (H 4) (N 5 (H 8) (H 9))))
   [1,3,2,6,7,4,5,8,9]
   λ> recorrido (N 1 (N 3 (H 6) (H 7)) (N 2 (H 4) (H 5)))
   [1,3,2,6,7,4,5]
   λ> recorrido (N 1 (N 2 (H 4) (H 5)) (N 3 (H 6) (H 7)))
   [1,2,3,4,5,6,7]
   λ> recorrido (N 1 (N 2 (H 4) (H 5)) (H 3))
   [1,2,3,4,5]
   λ> recorrido (N 1 (H 4) (H 3))
   [1,4,3]
   λ> recorrido (H 3)
   [3]

λ> recorrido (N 1 (N 2 (H 4) (N 5 (H 8) (H 9))) (N 3 (H 6) (H 7)))

[1,2,3,4,5,6,7,8,9]

λ> recorrido (N 1 (N 3 (H 6) (H 7)) (N 2 (H 4) (N 5 (H 8) (H 9))))

[1,3,2,6,7,4,5,8,9]

λ> recorrido (N 1 (N 3 (H 6) (H 7)) (N 2 (H 4) (H 5)))

[1,3,2,6,7,4,5]

λ> recorrido (N 1 (N 2 (H 4) (H 5)) (N 3 (H 6) (H 7)))

[1,2,3,4,5,6,7]

λ> recorrido (N 1 (N 2 (H 4) (H 5)) (H 3))

[1,2,3,4,5]

λ> recorrido (N 1 (H 4) (H 3))

[1,4,3]

λ> recorrido (H 3)

[3]

Soluciones

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

ejArbol :: Arbol Int
ejArbol = N 1 (N 2 (H 4)
                   (N 5 (H 8) (H 9)))
              (N 3 (H 6) (H 7))

-- 1ª definición
-- =============

recorrido :: Arbol t -> [t]
recorrido = concat . niveles

-- (niveles a) es la lista de los niveles del árbol a. Por ejemplo,
--    λ> niveles (N 1 (N 2 (H 4) (N 5 (H 8) (H 9))) (N 3 (H 6) (H 7)))
--    [[1],[2,3],[4,5,6,7],[8,9]]
niveles :: Arbol t -> [[t]]
niveles (H x)     = [[x]]
niveles (N x i d) = [x] : mezcla (niveles i) (niveles d)

-- (mezcla xss yss) es la lista obtenida concatenando los
-- correspondientes elementos de xss e yss. Por ejemplo,
--    λ> mezcla [[1,3],[2,5,7]] [[4],[1,9],[0,14]]
--    [[1,3,4],[2,5,7,1,9],[0,14]]
--    λ> mezcla [[1,3],[2,5,7]] [[4]]
--    [[1,3,4],[2,5,7]]
mezcla :: [[a]] -> [[a]] -> [[a]]
mezcla [] yss            = yss
mezcla xss []            = xss
mezcla (xs:xss) (ys:yss) = (xs ++ ys) : mezcla xss yss

-- 2ª definición
-- =============

recorrido2 :: Arbol t -> [t]
recorrido2 = concat . niveles2

-- (niveles2 a) es la lista de los niveles del árbol a. Por ejemplo,
--    λ> niveles2 (N 1 (N 2 (H 4) (N 5 (H 8) (H 9))) (N 3 (H 6) (H 7)))
--    [[1],[2,3],[4,5,6,7],[8,9]]
niveles2 :: Arbol t -> [[t]]
niveles2 a = takeWhile (not . null) [nivel n a | n <- [0..]]

-- (nivel n a) es el nivel iésimo del árbol a. Por ejemplo,
--    λ> nivel 2 (N 1 (N 2 (H 4) (N 5 (H 8) (H 9))) (N 3 (H 6) (H 7)))
--    [4,5,6,7]
--    λ> nivel 5 (N 1 (N 2 (H 4) (N 5 (H 8) (H 9))) (N 3 (H 6) (H 7)))
--    []
nivel :: Int -> Arbol t -> [t]
nivel 0 (H x)      = [x]
nivel n (H _)      = []
nivel 0 (N x _ _)  = [x]
nivel n (N x i d)  = nivel (n-1) i ++ nivel (n-1) d

data Arbol a = H a

| N a (Arbol a) (Arbol a)

deriving (Eq, Show)

ejArbol :: Arbol Int

ejArbol = N 1 (N 2 (H 4)

(N 5 (H 8) (H 9)))

(N 3 (H 6) (H 7))

-- 1ª definición

-- =============

recorrido :: Arbol t -> [t]

recorrido = concat . niveles

-- (niveles a) es la lista de los niveles del árbol a. Por ejemplo,

-- λ> niveles (N 1 (N 2 (H 4) (N 5 (H 8) (H 9))) (N 3 (H 6) (H 7)))

-- [[1],[2,3],[4,5,6,7],[8,9]]

niveles :: Arbol t -> [[t]]

niveles (H x) = [[x]]

niveles (N x i d) = [x] : mezcla (niveles i) (niveles d)

-- (mezcla xss yss) es la lista obtenida concatenando los

-- correspondientes elementos de xss e yss. Por ejemplo,

-- λ> mezcla [[1,3],[2,5,7]] [[4],[1,9],[0,14]]

-- [[1,3,4],[2,5,7,1,9],[0,14]]

-- λ> mezcla [[1,3],[2,5,7]] [[4]]

-- [[1,3,4],[2,5,7]]

mezcla :: [[a]] -> [[a]] -> [[a]]

mezcla [] yss = yss

mezcla xss [] = xss

mezcla (xs:xss) (ys:yss) = (xs ++ ys) : mezcla xss yss

-- 2ª definición

-- =============

recorrido2 :: Arbol t -> [t]

recorrido2 = concat . niveles2

-- (niveles2 a) es la lista de los niveles del árbol a. Por ejemplo,

-- λ> niveles2 (N 1 (N 2 (H 4) (N 5 (H 8) (H 9))) (N 3 (H 6) (H 7)))

-- [[1],[2,3],[4,5,6,7],[8,9]]

niveles2 :: Arbol t -> [[t]]

niveles2 a = takeWhile (not . null) [nivel n a | n <- [0..]]

-- (nivel n a) es el nivel iésimo del árbol a. Por ejemplo,

-- λ> nivel 2 (N 1 (N 2 (H 4) (N 5 (H 8) (H 9))) (N 3 (H 6) (H 7)))

-- [4,5,6,7]

-- λ> nivel 5 (N 1 (N 2 (H 4) (N 5 (H 8) (H 9))) (N 3 (H 6) (H 7)))

-- []

nivel :: Int -> Arbol t -> [t]

nivel 0 (H x) = [x]

nivel n (H _) = []

nivel 0 (N x _ _) = [x]

nivel n (N x i d) = nivel (n-1) i ++ nivel (n-1) d

Suma de las hojas de mínimo nivel

PorJosé A. Alonso 20-diciembre-201727-diciembre-2017

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)

data Arbol a = H a

| N a (Arbol a) (Arbol a)

deriving (Eq, Show)

Por ejemplo, el árbol

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

/ \

2 3

/ \ / \

4 5 6 7

/ \

8 9

se pueden representar por

   ejArbol :: Arbol Int
   ejArbol = N 1 (N 2 (H 4)
                      (N 5 (H 8) (H 9)))
                 (N 3 (H 6) (H 7))

ejArbol :: Arbol Int

ejArbol = N 1 (N 2 (H 4)

(N 5 (H 8) (H 9)))

(N 3 (H 6) (H 7))

En el árbol anterior, los valores de las hojas de menor nivel son 4, 6 y 7 cuya suma es 17.

Definir la función

   suma :: Num t => Arbol t -> t

1	suma :: Num t => Arbol t -> t

tal que (suma a) es la suma de los valores de las hojas de menor nivel del árbol a. Por ejemplo,

   suma ejArbol                                    ==  17
   suma (N 1 (N 2 (H 4) (H 5)) (N 3 (H 6) (H 7)))  ==  22
   suma (N 1 (H 2) (N 3 (H 6) (H 7)))              ==  2
   suma (N 1 (H 2) (H 3))                          ==  5
   suma (H 2)                                      ==  2

suma ejArbol == 17

suma (N 1 (N 2 (H 4) (H 5)) (N 3 (H 6) (H 7))) == 22

suma (N 1 (H 2) (N 3 (H 6) (H 7))) == 2

suma (N 1 (H 2) (H 3)) == 5

suma (H 2) == 2

Soluciones

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

ejArbol :: Arbol Int
ejArbol = N 1 (N 2 (H 4)
                   (N 5 (H 8) (H 9)))
              (N 3 (H 6) (H 7))
                      
suma :: Num t => Arbol t -> t
suma a = aux [a]
  where aux as | null xs   = aux (concat [[i,d] | (N _ i d) <- as])
               | otherwise = sum xs
          where xs = [x | (H x) <- as]

data Arbol a = H a

| N a (Arbol a) (Arbol a)

deriving (Eq, Show)

ejArbol :: Arbol Int

ejArbol = N 1 (N 2 (H 4)

(N 5 (H 8) (H 9)))

(N 3 (H 6) (H 7))

suma :: Num t => Arbol t -> t

suma a = aux [a]

where aux as | null xs = aux (concat [[i,d] | (N _ i d) <- as])

| otherwise = sum xs

where xs = [x | (H x) <- as]

Máxima distancia en árbol

Soluciones

Relación definida por un árbol

Soluciones

Padres como sumas de hijos

Soluciones

Recorrido por niveles de árboles binarios

Soluciones

Suma de las hojas de mínimo nivel

Soluciones

Entradas recientes

Buscar

Correo electrónico