Menu Close

Exterior de árboles

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

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

Por ejemplo, los árboles

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

se representan por

   ejArbol1, ejArbol2, ejArbol3 :: Arbol 
   ejArbol1 = N 3
                (N 2 
                   (N 5 (H 1) (H 4))
                   (H 7))
                (N 8 (H 6) (H 9))
   ejArbol2 = N 3
                (N 2 (H 5) (H 7))
                (N 8 (N 6 (H 1) (H 4))
                     (H 9))
   ejArbol3 = N 3
                (N 2 (H 5) (H 7))
                (N 8 (H 6)
                     (N 9 (H 1) (H 4)))

Definir la función

   exterior :: Arbol -> [Int]

tal que (exterior a) es la lista de los elementos exteriores del árbol a. Por ejemplo,

   exterior ejArbol1  ==  [3,2,5,1,4,7,6,9,8]
   exterior ejArbol2  ==  [3,2,5,7,1,4,9,8]
   exterior ejArbol3  ==  [3,2,5,7,6,1,4,9,8]

El orden de los elementos es desde la raíz hasta el extremo inferior izquierdo desde él hasta el inferior derecho y desde él hasta la raíz.

Soluciones

data Arbol = H Int
           | N Int Arbol Arbol 
  deriving Show
 
ejArbol1, ejArbol2, ejArbol3 :: Arbol 
ejArbol1 = N 3
             (N 2 
                (N 5 (H 1) (H 4))
                (H 7))
             (N 8 (H 6) (H 9))
ejArbol2 = N 3
             (N 2 (H 5) (H 7))
             (N 8 (N 6 (H 1) (H 4))
                  (H 9))
ejArbol3 = N 3
             (N 2 (H 5) (H 7))
             (N 8 (H 6)
                  (N 9 (H 1) (H 4)))
 
exterior :: Arbol -> [Int]
exterior a =
  ramaIzquierda a ++ hojas a ++ reverse (tail (ramaDerecha a))
 
-- (ramaIzquierda a) es la rama izquierda del árbol a. Por ejemplo,
--    ramaIzquierda ejArbol1  ==  [3,2,5]
--    ramaIzquierda ejArbol3  ==  [3,2]
ramaIzquierda :: Arbol -> [Int]
ramaIzquierda (H _)     = []
ramaIzquierda (N x i _) = x : ramaIzquierda i
 
-- (ramaDerecha a) es la rama derecha del árbol a. Por ejemplo,
--    ramaDerecha ejArbol1  ==  [3,8]
--    ramaDerecha ejArbol3  ==  [3,8,9]
ramaDerecha :: Arbol -> [Int]
ramaDerecha (H _)     = []
ramaDerecha (N x _ d) = x : ramaDerecha d
 
-- (hojas a) es la lista de las hojas del árbol a. Por ejemplo,
--    hojas ejArbol1  ==  [1,4,7,6,9]
--    hojas ejArbol3  ==  [5,7,6,1,4]
hojas :: Arbol -> [Int]
hojas (H x)     = [x]
hojas (N _ i d) = hojas i ++ hojas d

Pensamiento

¿Dónde está la utilidad
de nuestras utilidades?
Volvamos a la verdad:
vanidad de vanidades.

Antonio Machado

4 soluciones de “Exterior de árboles

  1. frahidzam
    data Arbol = H Int
               | N Int Arbol Arbol
      deriving Show
     
    exterior :: Arbol -> [Int]
    exterior (H x) = [x]
    exterior a     = izquierda a ++ bajo a ++ reverse (tail (derecha a))
     
    izquierda :: Arbol -> [Int]
    izquierda (H h)     = []
    izquierda (N n a b) = n : izquierda a
     
    derecha :: Arbol -> [Int]
    derecha (H h)     = []
    derecha (N n a b) = n : derecha b
     
    bajo :: Arbol -> [Int]
    bajo (H h)     = [h]
    bajo (N n a b) = bajo a ++ bajo b
  2. adogargon
    exterior :: Arbol -> [Int]
    exterior (H x)     = [x]
    exterior (N x i d) =
      izquierda (N x i d) ++ hijos (N x i d) ++ reverse (derecha d)
      where izquierda (N x i d) = x : izquierda i
            izquierda (H x)     = []
            hijos (N x i d)     = hijos i ++ hijos d
            hijos (H x)         = [x]
            derecha (N x i d)   = x:derecha d
            derecha (H x)       = []
  3. luipromor
    exterior :: Arbol -> [Int]
    exterior (H x ) = [x]
    exterior cs = aux1 (tail (aux cs 0)) (head (aux cs 0)) 0 cs
      where
        aux (N x i d) n = (x,n) : aux i (n+1) ++ aux d (n+1)
        aux (H x) n      = [(x,n)]
        aux1 ((a,b): xss) (x,y) n cs
          | n == 0    = x : aux1 ((a,b): xss) (x,y) 1 cs
          | y < b     = a : aux1 xss (a,b) 1 cs
          | otherwise = a : aux2 xss cs
          where
            aux2 [] _       = []
            aux2 [(a,b)] cs = [a]
            aux2 ((a,b):(c,d):xss) cs
              | d > b =
                aux2 ((c,d):(xss ++ [(a,b)])) cs
              | esNodo a cs && not(esExtremo a cs) =
                aux2 ((c,d):xss) cs
              | esNodo a cs && d - b == 1 =
                c : aux2 ((a,b):xss) cs 
              | otherwise =
                a : aux2 ((c,d):xss) cs
            esNodo a (N x i d) | x == a    = True
                               | otherwise = esNodo a i || esNodo a d
            esNodo _ (H _)                 = False
            esExtremo a xs = elem a (f xs) || elem a (g xs)
              where  f (N x i d) = x : f i
                     f (H x)     = [x]
                     g (N x i d) = x : g d
                     g (H x)     = [x]
  4. berarcmat
    data Arbol = H Int
               | N Int Arbol Arbol 
      deriving Show
     
    exterior :: Arbol -> [Int]
    exterior (H x) = [x]
    exterior a =
      izquierda a ++ map last (ramas a) ++ init (reverse (derecha a))
     
    ramas :: Arbol -> [[Int]]
    ramas (H x)     = [[x]]
    ramas (N x i d) = [x: xs | xs <- ramas i]
                      ++ [x: ys | ys <- ramas d]
     
    izquierda :: Arbol -> [Int]
    izquierda (H h)     = []
    izquierda (N n a b) = n : izquierda a
     
    derecha :: Arbol -> [Int]
    derecha (H h)     = []
    derecha (N n a b) = n : derecha b

Escribe tu solución

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