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) |
data Arbol a = H a
| N a (Arbol a) (Arbol a)
deriving (Show, Eq)
Por ejemplo, el árbol
se representa por
N 9 (N 3 (H 2) (H 4)) (H 7) |
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] |
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] |
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] |
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))] |
λ> 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 |
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) |
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) |
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)
Se puede imprimir o compartir con
Una solución de “Construcción del árbol a partir de los recorridos preorden e inorden”