Posiciones en árboles binarios
Los árboles binarios con datos en los nodos se definen por
|
1 2 3 |
data Arbol a = H | N a (Arbol a) (Arbol a) deriving (Eq, Show) |
Por ejemplo, el árbol
|
1 2 3 4 5 6 7 8 |
3 / \ / \ 0 5 / \ / \ 5 0 0 3 / \ 2 4 |
se representa por
|
1 2 3 4 5 6 7 8 9 10 |
ejArbol :: Arbol Int ejArbol = N 3 (N 0 (N 5 (N 2 H H) (N 4 H H)) (N 0 H H)) (N 5 (N 0 H H) (N 3 H H)) |
Cada posición de un elemento de un árbol es una lista de movimientos hacia la izquierda o hacia la derecha. Por ejemplo, la posición de 4 en al árbol anterior es [I,I,D].
Los tipos de los movimientos y de las posiciones se definen por
|
1 2 |
data Movimiento = I | D deriving (Show, Eq) type Posicion = [Movimiento] |
Definir la función
|
1 |
posiciones :: Eq b => b -> Arbol b -> [Posicion] |
tal que (posiciones n a) es la lista de las posiciones del elemento n en el árbol a. Por ejemplo,
|
1 2 3 4 5 6 |
posiciones 0 ejArbol == [[I],[I,D],[D,I]] posiciones 2 ejArbol == [[I,I,I]] posiciones 3 ejArbol == [[],[D,D]] posiciones 4 ejArbol == [[I,I,D]] posiciones 5 ejArbol == [[I,I],[D]] posiciones 1 ejArbol == [] |
Soluciones
|
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 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
data Arbol a = H | N a (Arbol a) (Arbol a) deriving (Eq, Show) ejArbol :: Arbol Int ejArbol = N 3 (N 0 (N 5 (N 2 H H) (N 4 H H)) (N 0 H H)) (N 5 (N 0 H H) (N 3 H H)) data Movimiento = I | D deriving (Show, Eq) type Posicion = [Movimiento] -- 1ª solución -- =========== posiciones :: Eq b => b -> Arbol b -> [Posicion] posiciones n a = aux n a [[]] where aux _ H _ = [] aux n (N x i d) cs | x == n = cs ++ [I:xs | xs <- aux n i cs] ++ [D:xs | xs <- aux n d cs] | otherwise = [I:xs | xs <- aux n i cs] ++ [D:xs | xs <- aux n d cs] -- 2ª solución -- =========== posiciones2 :: Eq b => b -> Arbol b -> [Posicion] posiciones2 n a = aux n a [[]] where aux _ H _ = [] aux n (N x i d) cs | x == n = cs ++ ps | otherwise = ps where ps = [I:xs | xs <- aux n i cs] ++ [D:xs | xs <- aux n d cs] -- 3ª solución -- =========== posiciones3 :: Eq b => b -> Arbol b -> [Posicion] posiciones3 n a = aux n a [[]] where aux _ H _ = [] aux n (N x i d) cs | x == n = cs ++ ps | otherwise = ps where ps = map (I:) (aux n i cs) ++ map (D:) (aux n d cs) -- Equivalencia -- ============ -- Generador de árboles instance Arbitrary a => Arbitrary (Arbol a) where arbitrary = sized genArbol genArbol :: (Arbitrary a, Integral a1) => a1 -> Gen (Arbol a) genArbol 0 = return H genArbol n | n > 0 = N <$> arbitrary <*> subarbol <*> subarbol where subarbol = genArbol (div n 2) -- La propiedad es prop_posiciones_equiv :: Arbol Int -> Bool prop_posiciones_equiv a = and [posiciones n a == posiciones2 n a | n <- xs] && and [posiciones n a == posiciones3 n a | n <- xs] where xs = take 3 (elementos a) -- (elementos a) son los elementos del árbol a. Por ejemplo, -- elementos ejArbol == [3,0,5,2,4] elementos :: Eq b => Arbol b -> [b] elementos H = [] elementos (N x i d) = nub (x : elementos i ++ elementos d) -- La comprobación es -- λ> quickCheck prop_posiciones_equiv -- +++ OK, passed 100 tests. |
Pensamiento
Nunca traces tu frontera,
ni cuides de tu perfil;
todo eso es cosa de fuera.Antonio Machado
2 Comentarios