Construcción del árbol a partir de los recorridos preorden e inorden
Los árboles binarios con valores en las hojas y en los nodos se pueden representar con el siguiente tipo
|
1 2 3 |
data Arbol a = H a | N a (Arbol a) (Arbol a) deriving (Show, Eq) |
Por ejemplo, el árbol
|
1 2 3 4 5 6 |
9 / \ / \ 3 7 / \ 2 4 |
se representa por
|
1 |
N 9 (N 3 (H 2) (H 4)) (H 7) |
Definir las siguientes funciones
|
1 2 3 |
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,
|
1 |
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,
|
1 |
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,
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
λ> 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
|
1 2 3 4 5 6 7 8 9 10 |
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
|
1 2 3 4 5 6 7 8 9 |
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
[schedule expon=’2016-06-02′ expat=»06:00″]
- Las soluciones se pueden escribir en los comentarios hasta el 02 de junio.
- El código se debe escribir entre una línea con <pre lang=»haskell»> y otra con </pre>
[/schedule]
[schedule on=’2016-06-02′ at=»06:00″]
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
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) |
[/schedule]