Exterior de árboles

José A. Alonso

06-02-2019

Los árboles binarios con datos en loas 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 = raiz a
             :  tail (ramaIzquierda a)
             ++ tail (hojas a)
             ++ reverse (tail (init (ramaDerecha a)))

-- (raiz a) es la raíz del árbol a. Por ejemplo,
--    raiz ejArbol1  ==  3
--    raiz (H 5)  ==  5
raiz :: Arbol -> Int
raiz (H x)      = x
raiz (N x _ _ ) = x

-- (ramaIzquierda a) es la rama izquierda del árbol a. Por ejemplo,
--    ramaIzquierda ejArbol1  ==  [3,2,5,1]
--    ramaIzquierda ejArbol3  ==  [3,2,5]
ramaIzquierda :: Arbol -> [Int]
ramaIzquierda (H x)     = [x]
ramaIzquierda (N x i _) = x : ramaIzquierda i

-- (ramaDerecha a) es la rama derecha del árbol a. Por ejemplo,
--    ramaDerecha ejArbol1  ==  [3,8,9]
--    ramaDerecha ejArbol3  ==  [3,8,9,4]
ramaDerecha :: Arbol -> [Int]
ramaDerecha (H x)     = [x]
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