Menu Close

Recorrido por niveles de árboles binarios

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)

Por ejemplo, el árbol

         1 
       /   \
      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))

Definir la función

   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]

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

6 soluciones de “Recorrido por niveles de árboles binarios

  1. carriomon1
     
    recorrido :: Arbol t -> [t]
    recorrido x = concat [nivelesArbol x n | n <- [1..(profundidad x)]]
     
     
    profundidad :: Arbol t -> Int
    profundidad (H _) = 1
    profundidad (N _ i d) = 1 + (max (profundidad i) (profundidad d))
     
    nivelesArbol :: Arbol t -> Int -> [t]
    nivelesArbol (H a) 1 = [a]
    nivelesArbol (N a _ _) 1 = [a]
    nivelesArbol (N a i d) n = nivelesArbol i (n-1) ++ nivelesArbol d (n-1)
    nivelesArbol _ _ = []
    • alerodrod5

      Llego a tu misma solución pero la simplifico un poco (no tanto en eficacia, pero si en la lectura)

       
      data Arbol a = H a
                   | N a (Arbol a) (Arbol a) 
           deriving (Eq, Show)
       
      recorrido :: Arbol t -> [t]
      recorrido a1 =concat [ nivel a1 x | x<-[1..profundidad a1]]
       
      profundidad :: Arbol t -> Int
      profundidad (H _ ) = 1
      profundidad (N x a1 a2) = 1 + max (profundidad a1) (profundidad a2)
       
      nivel :: Arbol t -> Int -> [t]
      nivel (H x) 1 = [x]
      nivel (N x a1 a2) 1 = [x]
      nivel (N x a1 a2) y = nivel a1 y' ++ nivel a2 y'
        where y' = pred y
      nivel _ _ = []
  2. albcarcas1
     
    import Data.List (concat)
     
    data Arbol a = H a
                    | N a (Arbol a) (Arbol a) 
         deriving (Eq, Show)
     
    recorrido :: Arbol t -> [t]
    recorrido t = concat[nivel n t | n <- [0..(prof t)]]
     
    prof :: Arbol t -> Int
    prof (H x) = 0
    prof (N _ a b) = 1 + max (prof a) (prof b)
     
    nivel :: Int -> Arbol t -> [t]
    nivel 0 (H x) = [x]
    nivel 0 (N x _ _) = [x]
    nivel k (H x) = []
    nivel k (N _ a b) = nivel (k-1) a ++ nivel (k-1) b
  3. agumaragu1
    data Arbol a = H a
                    | N a (Arbol a) (Arbol a) 
         deriving (Eq, Show)
     
    recorrido :: Arbol t -> [t]
    recorrido = concat.takeWhile (not.null).aux
      where aux (H x) = [x] : repeat []
            aux (N x y z) = [x] : zipWith (++) (aux y) (aux z)
  4. antnavoro
    data Arbol a = H a
                    | N a (Arbol a) (Arbol a) 
         deriving (Eq, Show)
     
    recorrido :: Arbol t -> [t]
    recorrido x = aux [x]
      where aux [] = []
            aux xs = map aux2 xs ++ (aux . aux3) xs
            aux2 (H a) = a
            aux2 (N a _ _) = a
            aux3 xs = concat [[a,b] | (N _ a b) <- xs]
  5. angruicam1

    Podemos emplear directamente la función levels (de Data.Tree) después de realizar las transformaciones pertinentes:

    import Data.Tree (Tree(Node),levels)
     
    data Arbol a = H a
                 | N a (Arbol a) (Arbol a) 
         deriving (Eq, Show)
     
    recorrido :: Arbol t -> [t]
    recorrido = concat . levels . toTree
     
    -- (toTree a) convierte el tipo de datos
    -- Arbol al tipo Tree (definido en Data.Tree).
    -- Por ejemplo
    --   λ> toTree (N 1 (H 2) (H 3))
    --   Node 1 [Node 2 [],Node 3 []]
     
    toTree :: Arbol t -> Tree t
    toTree (H a)     = Node a []
    toTree (N a i d) = Node a [toTree i,toTree d]

Leave a Reply

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