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)

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

6 Comentarios

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 _ _ = []

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 _ _ = []

Responder

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 _ _ = []

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 _ _ = []

Responder

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

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

Responder

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)

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)

Responder

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]

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]

Responder

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]

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]

Responder

Recorrido por niveles de árboles binarios

Soluciones

6 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

6 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico