Menu Close

Exterior de árboles

José A. Alonso,

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

Posted in Medio
Tagged , , , ,

4 Comments

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