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
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)
