Menu Close

Construcción del árbol a partir de los recorridos preorden e inorden

José A. Alonso,

Los árboles binarios con valores en las hojas y en los nodos se pueden representar con el siguiente tipo

   data Arbol a = H a
                | N a (Arbol a) (Arbol a)
                deriving (Show, Eq)

Por ejemplo, el árbol

        9 
       / \
      /   \
     3     7
    / \  
   2   4

se representa por

   N 9 (N 3 (H 2) (H 4)) (H 7)

Definir las siguientes funciones

   preorden :: Arbol a -> [a]
   inorden  :: Arbol a -> [a]
   arboles  :: Eq a => [a] -> [a] -> [Arbol a]

tales que

  • (preorden x) es la lista correspondiente al recorrido preorden del árbol x; es decir, primero visita la raíz del árbol, a continuación recorre el subárbol izquierdo y, finalmente, recorre el subárbol derecho. Por ejemplo, 
     preorden (N 9 (N 3 (H 2) (H 4)) (H 7))  ==  [9,3,2,4,7]
  • (inorden x) es la lista correspondiente al recorrido inorden del árbol x; es decir, primero recorre el subárbol izquierdo, a continuación visita la raíz del árbol y, finalmente, recorre el subárbol derecho. Por ejemplo, 
     inorden (N 9 (N 3 (H 2) (H 4)) (H 7))  ==  [2,3,4,9,7]
  • (arboles xs ys) es la lista de los árboles con recorrido preorden xs y recorrido inorden de ys. Por ejemplo,
      λ> arboles [9,3,2,4,7] [2,3,4,9,7]
      [N 9 (N 3 (H 2) (H 4)) (H 7)]
      λ> arboles [9,3,2,4,7] [2,4,3,9,7]
      []
      λ> arboles [1,1,1,2,3] [1,1,2,1,3]
      [N 1 (H 1) (N 1 (H 2) (H 3)),
       N 1 (N 1 (H 1) (H 2)) (H 3)]
      λ> let x = N 1 (N 1 (H 1) (H 3)) (N 1 (N 1 (H 1) (H 2)) (H 3))
      λ> arboles (preorden x) (inorden x)
      [N 1 (H 1) (N 1 (H 3) (N 1 (H 1) (N 1 (H 2) (H 3)))),
       N 1 (H 1) (N 1 (H 3) (N 1 (N 1 (H 1) (H 2)) (H 3))),
       N 1 (N 1 (H 1) (H 3)) (N 1 (H 1) (N 1 (H 2) (H 3))),
       N 1 (N 1 (H 1) (H 3)) (N 1 (N 1 (H 1) (H 2)) (H 3))]

Comprobar con QuickCheck, que para todo árbol x se verifican las siguientes propiedades

    prop_arboles1 :: Arbol Int -> Bool
    prop_arboles1 x =
        x `elem` arboles (preorden x) (inorden x)
 
    prop_arboles2 :: Arbol Int -> Bool
    prop_arboles2 x =
        and [preorden a == xs && inorden a == ys | a < - as] 
        where xs = preorden x
              ys = inorden x
              as = arboles xs ys

Nota: Para la comprobación, se usa el siguiente generador

   import Control.Monad 
 
   instance Arbitrary a => Arbitrary (Arbol a) where
     arbitrary = sized arbol
       where
         arbol 0       = liftM H arbitrary 
         arbol n | n>0 = oneof [liftM H arbitrary,
                                liftM3 N arbitrary subarbol subarbol]
                         where subarbol = arbol (div n 2)

Soluciones

import Data.List (elemIndex, elemIndices)
import Data.Maybe (isJust, fromJust)
import Test.QuickCheck
import Control.Monad 
 
data Arbol a = H a
             | N a (Arbol a) (Arbol a)
             deriving (Show, Eq)
 
preorden :: Arbol a -> [a]
preorden (H x)     = [x]
preorden (N x i d) = x : (preorden i ++ preorden d)
 
inorden :: Arbol a -> [a]
inorden (H x)     = [x]
inorden (N x i d) = inorden i ++ (x : inorden d)
 
arboles :: Eq a => [a] -> [a] -> [Arbol a]
arboles [] _      = []
arboles [x] ys | ys == [x] = [H x]
               | otherwise = []
arboles (x:xs) ys =
    [N x i d | k <- elemIndices x ys 
             , let (ys1,_:ys2) = splitAt k ys
             , let (xs1,xs2)   = splitAt k xs
             , i <- arboles xs1 ys1
             , d <- arboles xs2 ys2]
 
prop_arboles1 :: Arbol Int -> Bool
prop_arboles1 x =
    x `elem` arboles (preorden x) (inorden x)
 
prop_arboles2 :: Arbol Int -> Bool
prop_arboles2 x =
    and [preorden a == xs && inorden a == ys | a <- as] 
    where xs = preorden x
          ys = inorden x
          as = arboles xs ys
 
instance Arbitrary a => Arbitrary (Arbol a) where
  arbitrary = sized arbol
    where
      arbol 0       = liftM H arbitrary 
      arbol n | n>0 = oneof [liftM H arbitrary,
                             liftM3 N arbitrary subarbol subarbol]
                      where subarbol = arbol (div n 2)
Ejercicio

Una solución de “Construcción del árbol a partir de los recorridos preorden e inorden”

  1. Responder
    abrdelrod 
    preorden :: Arbol a -> [a]
preorden (H a)     = [a]
preorden (N a i d) = a:preorden i ++ preorden d
 
inorden :: Arbol a -> [a]
inorden (H a)     = [a]
inorden (N a i d) = inorden i ++ a:inorden d
 
arboles :: Eq a => [a] -> [a] -> [Arbol a]
arboles xs ys = 
    filter (a -> inorden a == ys) (listaArbolesP xs)
 
-- (listaArbolesP xs) es la lista de todos los árboles "a" tales que
-- preorden a == xs 
listaArbolesP :: [a] -> [Arbol a]
listaArbolesP [x] = [H x]
listaArbolesP (x:xs) = 
    concatMap ((i,d) -> [N x a b | a <- listaArbolesP i, 
                                    b <- listaArbolesP d]) 
              (divide xs)
     where divide xs = [splitAt n xs | n <- [1,3..length xs]]

Escribe tu solución

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