Imagen especular de un árbol binario
El árbol binario
1 2 3 4 5 6 |
9 / \ / \ 3 7 / \ 2 4 |
se puede representar por
1 |
N 9 (N 3 (H 2) (H 4)) (H 7) |
El tipo de los árboles binarios se puede definir por
1 2 3 |
data Arbol a = H a | N a (Arbol a) (Arbol a) deriving (Show, Eq) |
Definir la función
1 |
espejo :: Arbol a -> Arbol a |
tal que espejo x
es la imagen especular del árbol x
. Por ejemplo,
1 |
espejo (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (H 7) (N 3 (H 4) (H 2)) |
Comprobar con QuickCheck las siguientes propiedades, para todo árbol x
,
1 2 3 |
espejo (espejo x) = x reverse (preorden (espejo x)) = postorden x postorden (espejo x) = reverse (preorden x) |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
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 |
import Test.QuickCheck data Arbol a = H a | N a (Arbol a) (Arbol a) deriving (Show, Eq) espejo :: Arbol a -> Arbol a espejo (H x) = H x espejo (N x i d) = N x (espejo d) (espejo i) -- Generador para las comprobaciones -- ================================= -- (arbolArbitrario n) es un árbol aleatorio de altura n. Por ejemplo, -- λ> sample (arbolArbitrario 3 :: Gen (Arbol Int)) -- N 0 (H 0) (H 0) -- N 1 (N (-2) (H (-1)) (H 1)) (H 2) -- N 3 (H 1) (H 2) -- N 6 (N 0 (H 5) (H (-5))) (N (-5) (H (-5)) (H 4)) -- H 7 -- N (-8) (H (-8)) (H 9) -- H 2 -- N (-1) (H 7) (N 9 (H (-2)) (H (-8))) -- H (-3) -- N 0 (N 16 (H (-14)) (H (-18))) (H 7) -- N (-16) (H 18) (N (-19) (H (-15)) (H (-18))) arbolArbitrario :: Arbitrary a => Int -> Gen (Arbol a) arbolArbitrario 0 = H <$> arbitrary arbolArbitrario n = oneof [H <$> arbitrary, N <$> arbitrary <*> arbolArbitrario (div n 2) <*> arbolArbitrario (div n 2)] -- Arbol es subclase de Arbitrary instance Arbitrary a => Arbitrary (Arbol a) where arbitrary = sized arbolArbitrario -- Funciones auxiliares para la comprobación -- ========================================= -- (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 :: Arbol a -> [a] preorden (H x) = [x] preorden (N x i d) = x : preorden i ++ preorden d -- (postorden x) es la lista correspondiente al recorrido postorden -- del árbol x; es decir, primero recorre el subárbol izquierdo, a -- continuación el subárbol derecho y, finalmente, la raíz del -- árbol. Por ejemplo, -- postorden (N 9 (N 3 (H 2) (H 4)) (H 7)) == [2,4,3,7,9] postorden :: Arbol a -> [a] postorden (H x) = [x] postorden (N x i d) = postorden i ++ postorden d ++ [x] -- Comprobación de las propiedades -- =============================== -- Las propiedades son prop_espejo :: Arbol Int -> Bool prop_espejo x = espejo (espejo x) == x && reverse (preorden (espejo x)) == postorden x && postorden (espejo x) == reverse (preorden x) -- La comprobación es -- λ> quickCheck prop_espejo -- OK, passed 100 tests. |
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 82 83 84 85 86 87 88 89 90 91 92 93 94 95 |
from dataclasses import dataclass from random import choice, randint from typing import Generic, TypeVar from hypothesis import given from hypothesis import strategies as st A = TypeVar("A") @dataclass class Arbol(Generic[A]): pass @dataclass class H(Arbol[A]): x: A @dataclass class N(Arbol[A]): x: A i: Arbol[A] d: Arbol[A] def espejo(a: Arbol[A]) -> Arbol[A]: match a: case H(x): return H(x) case N(x, i, d): return N(x, espejo(d), espejo(i)) assert False # Generador para las comprobaciones # ================================= # (arbolArbitrario n) es un árbol aleatorio de orden n. Por ejemplo, # >>> arbolArbitrario(4) # N(x=2, i=H(x=1), d=H(x=9)) # >>> arbolArbitrario(4) # H(x=10) # >>> arbolArbitrario(4) # N(x=4, i=N(x=7, i=H(x=4), d=H(x=0)), d=H(x=6)) def arbolArbitrario(n: int) -> Arbol[int]: if n <= 1: return H(randint(0, 10)) m = n // 2 return choice([H(randint(0, 10)), N(randint(0, 10), arbolArbitrario(m), arbolArbitrario(m))]) # Funciones auxiliares para la comprobación # ========================================= # 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] def preorden(a: Arbol[A]) -> list[A]: match a: case H(x): return [x] case N(x, i, d): return [x] + preorden(i) + preorden(d) assert False # (postorden x) es la lista correspondiente al recorrido postorden # del árbol x; es decir, primero recorre el subárbol izquierdo, a # continuación el subárbol derecho y, finalmente, la raíz del # árbol. Por ejemplo, # >>> postorden(N(9, N(3, H(2), H(4)), H(7))) # [2, 4, 3, 7, 9] def postorden(a: Arbol[A]) -> list[A]: match a: case H(x): return [x] case N(x, i, d): return postorden(i) + postorden(d) + [x] assert False # Comprobación de las propiedades # =============================== # Las propiedades son @given(st.integers(min_value=1, max_value=10)) def test_espejo(n: int) -> None: x = arbolArbitrario(n) assert espejo(espejo(x)) == x assert list(reversed(preorden(espejo(x)))) == postorden(x) assert postorden(espejo(x)) == list(reversed(preorden(x))) # La comprobación es # src> poetry run pytest -q imagen_especular_de_un_arbol_binario.py # 1 passed in 0.16s |