PFH: La semana en Exercitium (24 de diciembre de 2022)
Esta semana he publicado en Exercitium las soluciones de los siguientes problemas:
- 1. Recorrido de árboles binarios
- 2. Imagen especular de un árbol binario
- 3. Subárbol de profundidad dada
- 4. Árbol de profundidad n con nodos iguales
- 5. Suma de un árbol
A continuación se muestran las soluciones.
1. Recorrido de árboles binarios
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 las funciones
|
1 2 |
preorden :: Arbol a -> [a] postorden :: Arbol a -> [a] |
tales que
preordenes la lista correspondiente al recorrido preorden del árbolx; 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] |
postorden xes la lista correspondiente al recorrido postorden del árbolx; es decir, primero recorre el subárbol izquierdo, a continuación el subárbol derecho y, finalmente, la raíz del árbol. Por ejemplo,
|
1 |
postorden (N 9 (N 3 (H 2) (H 4)) (H 7)) == [2,4,3,7,9] |
Comprobar con QuickCheck que la longitud de la lista obtenida recorriendo un árbol en cualquiera de los sentidos es igual al número de nodos del árbol más el número de hojas.
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 |
import Test.QuickCheck 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 postorden :: Arbol a -> [a] postorden (H x) = [x] postorden (N x i d) = postorden i ++ postorden d ++ [x] -- Comprobación de la propiedad -- ============================ -- (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 -- La propiedad es prop_longitud_recorrido :: Arbol Int -> Bool prop_longitud_recorrido x = length (preorden x) == n && length (postorden x) == n where n = nNodos x + nHojas x -- (nNodos x) es el número de nodos del árbol x. Por ejemplo, -- nNodos (N 9 (N 3 (H 2) (H 4)) (H 7)) == 2 nNodos :: Arbol a -> Int nNodos (H _) = 0 nNodos (N _ i d) = 1 + nNodos i + nNodos d -- (nHojas x) es el número de hojas del árbol x. Por ejemplo, -- nHojas (N 9 (N 3 (H 2) (H 4)) (H 7)) == 3 nHojas :: Arbol a -> Int nHojas (H _) = 1 nHojas (N _ i d) = nHojas i + nHojas d -- La comprobación es -- λ> quickCheck prop_longitud_recorrido -- 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 |
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 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 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 la propiedad # ============================ # (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))]) # nNodos(x) es el número de nodos del árbol x. Por ejemplo, # nNodos(N(9, N(3, H(2), H(4)), H(7))) == 2 def nNodos(a: Arbol[A]) -> int: match a: case H(_): return 0 case N(_, i, d): return 1 + nNodos(i) + nNodos(d) assert False # (nHojas x) es el número de hojas del árbol x. Por ejemplo, # nHojas (N 9 (N 3 (H 2) (H 4)) (H 7)) == 3 def nHojas(a: Arbol[A]) -> int: match a: case H(_): return 1 case N(_, i, d): return nHojas(i) + nHojas(d) assert False # La propiedad es @given(st.integers(min_value=1, max_value=10)) def test_recorrido(n: int) -> None: a = arbolArbitrario(n) m = nNodos(a) + nHojas(a) assert len(preorden(a)) == m assert len(postorden(a)) == m # La comprobación es # src> poetry run pytest -q recorrido_de_arboles_binarios.py # 1 passed in 0.16s |
2. 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 |
3. Subárbol de profundidad dada
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) |
La función take está definida por
|
1 2 3 4 |
take :: Int -> [a] -> [a] take 0 = [] take (n+1) [] = [] take (n+1) (x:xs) = x : take n xs |
Definir la función
|
1 |
takeArbol :: Int -> Arbol a -> Arbol a |
tal que takeArbol n t es el subárbol de t de profundidad n. Por ejemplo,
|
1 2 3 4 |
takeArbol 0 (N 9 (N 3 (H 2) (H 4)) (H 7)) == H 9 takeArbol 1 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (H 3) (H 7) takeArbol 2 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (N 3 (H 2) (H 4)) (H 7) takeArbol 3 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (N 3 (H 2) (H 4)) (H 7) |
Comprobar con QuickCheck que la profundidad de takeArbol n x es menor o igual que n, para todo número natural n y todo árbol 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 |
import Test.QuickCheck data Arbol a = H a | N a (Arbol a) (Arbol a) deriving (Show, Eq) takeArbol :: Int -> Arbol a -> Arbol a takeArbol _ (H x) = H x takeArbol 0 (N x _ _) = H x takeArbol n (N x i d) = N x (takeArbol (n-1) i) (takeArbol (n-1) d) -- 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 -- Función auxiliar para la comprobación -- ===================================== -- (profundidad x) es la profundidad del árbol x. Por ejemplo, -- profundidad (N 9 (N 3 (H 2) (H 4)) (H 7)) == 2 -- profundidad (N 9 (N 3 (H 2) (N 1 (H 4) (H 5))) (H 7)) == 3 -- profundidad (N 4 (N 5 (H 4) (H 2)) (N 3 (H 7) (H 4))) == 2 profundidad :: Arbol a -> Int profundidad (H _) = 0 profundidad (N _ i d) = 1 + max (profundidad i) (profundidad d) -- Comprobación de la propiedad -- ============================ -- La propiedad es prop_takeArbol :: Int -> Arbol Int -> Property prop_takeArbol n x = n >= 0 ==> profundidad (takeArbol n x) <= n -- La comprobación es -- λ> quickCheck prop_takeArbol -- +++ 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 |
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 takeArbol(n: int, a: Arbol[A]) -> Arbol[A]: match (n, a): case (_, H(x)): return H(x) case (0, N(x, _, _)): return H(x) case (n, N(x, i, d)): return N(x, takeArbol(n - 1, i), takeArbol(n - 1, d)) 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))]) # Función auxiliar para la comprobación # ===================================== # profundidad(x) es la profundidad del árbol x. Por ejemplo, # profundidad(N(9, N(3, H(2), H(4)), H(7))) == 2 # profundidad(N(9, N(3, H(2), N(1, H(4), H(5))), H(7))) == 3 # profundidad(N(4, N(5, H(4), H(2)), N(3, H(7), H(4)))) == 2 def profundidad(a: Arbol[A]) -> int: match a: case H(_): return 0 case N(_, i, d): return 1 + max(profundidad(i), profundidad(d)) assert False # Comprobación de la propiedad # ============================ # La propiedad es @given(st.integers(min_value=0, max_value=12), st.integers(min_value=1, max_value=10)) def test_takeArbol(n: int, m: int) -> None: x = arbolArbitrario(m) assert profundidad(takeArbol(n, x)) <= n # La comprobación es # src> poetry run pytest -q subarbol_de_profundidad_dada.py # 1 passed in 0.23s |
4. Árbol de profundidad n con nodos iguales
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 las funciones
|
1 2 |
repeatArbol :: a -> Arbol a replicateArbol :: Int -> a -> Arbol a |
tales que
repeatArbol xes es árbol con infinitos nodosx. Por ejemplo,
|
1 2 3 |
takeArbol 0 (repeatArbol 3) == H 3 takeArbol 1 (repeatArbol 3) == N 3 (H 3) (H 3) takeArbol 2 (repeatArbol 3) == N 3 (N 3 (H 3) (H 3)) (N 3 (H 3) (H 3)) |
replicate n xes el árbol de profundidadncuyos nodos sonx. Por ejemplo,
|
1 2 3 |
replicateArbol 0 5 == H 5 replicateArbol 1 5 == N 5 (H 5) (H 5) replicateArbol 2 5 == N 5 (N 5 (H 5) (H 5)) (N 5 (H 5) (H 5)) |
Comprobar con QuickCheck que el número de hojas de replicateArbol n x es 2^n, para todo número natural n.
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 |
import Test.QuickCheck data Arbol a = H a | N a (Arbol a) (Arbol a) deriving (Show, Eq) repeatArbol :: a -> Arbol a repeatArbol x = N x t t where t = repeatArbol x replicateArbol :: Int -> a -> Arbol a replicateArbol n = takeArbol n . repeatArbol -- (takeArbol n t) es el subárbol de t de profundidad n. Por ejemplo, -- takeArbol 0 (N 9 (N 3 (H 2) (H 4)) (H 7)) == H 9 -- takeArbol 1 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (H 3) (H 7) -- takeArbol 2 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (N 3 (H 2) (H 4)) (H 7) -- takeArbol 3 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (N 3 (H 2) (H 4)) (H 7) takeArbol :: Int -> Arbol a -> Arbol a takeArbol _ (H x) = H x takeArbol 0 (N x _ _) = H x takeArbol n (N x i d) = N x (takeArbol (n-1) i) (takeArbol (n-1) d) -- 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 -- Función auxiliar para la comprobación -- ===================================== -- (nHojas x) es el número de hojas del árbol x. Por ejemplo, -- nHojas (N 9 (N 3 (H 2) (H 4)) (H 7)) == 3 nHojas :: Arbol a -> Int nHojas (H _) = 1 nHojas (N _ i d) = nHojas i + nHojas d -- Comprobación de la propiedad -- ============================ -- La propiedad es prop_replicateArbol :: Int -> Int -> Property prop_replicateArbol n x = n >= 0 ==> nHojas (replicateArbol n x) == 2^n -- La comprobación es -- λ> quickCheckWith (stdArgs {maxSize=7}) prop_replicateArbol -- +++ 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 |
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 replicateArbol(n: int, x: A) -> Arbol[A]: match n: case 0: return H(x) case n: t = replicateArbol(n - 1, x) return N(x, t, t) 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))]) # Función auxiliar para la comprobación # ===================================== # nHojas(x) es el número de hojas del árbol x. Por ejemplo, # nHojas(N(9, N(3, H(2), H(4)), H(7))) == 3 def nHojas(a: Arbol[A]) -> int: match a: case H(_): return 1 case N(_, i, d): return nHojas(i) + nHojas(d) assert False # Comprobación de la propiedad # ============================ # La propiedad es @given(st.integers(min_value=1, max_value=10), st.integers(min_value=1, max_value=10)) def test_nHojas(n: int, x: int) -> None: assert nHojas(replicateArbol(n, x)) == 2**n # La comprobación es # src> poetry run pytest -q arbol_de_profundidad_n_con_nodos_iguales.py # 1 passed in 0.20s |
5. Suma de un árbol
Los árboles binarios con valores en los nodos se pueden definir por
|
1 2 3 |
data Arbol a = H | N a (Arbol1 a) (Arbol1 a) deriving (Show, Eq) |
Por ejemplo, el árbol
|
1 2 3 4 5 6 |
9 / \ / \ 8 6 / \ / \ 3 2 4 5 |
se puede representar por
|
1 |
N 9 (N 8 (N 3 H H) (N 2 H H)) (N 6 (N 4 H H) (N 5 H H)) |
Definir por recursión la función
|
1 |
sumaArbol :: Num a => Arbol1 a -> a |
tal sumaArbol x es la suma de los valores que hay en el árbol x. Por ejemplo,
|
1 |
sumaArbol (N 2 (N 5 (N 3 H H) (N 7 H H)) (N 4 H H)) == 21 |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
|
1 2 3 4 5 6 7 |
data Arbol1 a = H | N a (Arbol1 a) (Arbol1 a) deriving (Show, Eq) sumaArbol :: Num a => Arbol1 a -> a sumaArbol H = 0 sumaArbol (N x i d) = x + sumaArbol i + sumaArbol d |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
from dataclasses import dataclass @dataclass class Arbol: pass @dataclass class H(Arbol): pass @dataclass class N(Arbol): x: int i: Arbol d: Arbol def sumaArbol(a: Arbol) -> int: match a: case H(): return 0 case N(x, i, d): return x + sumaArbol(i) + sumaArbol(d) assert False |