Número de hojas 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 |
data Arbol a = H a | N a (Arbol a) (Arbol a) |
Definir las funciones
|
1 2 |
nHojas :: Arbol a -> Int nNodos :: Arbol a -> Int |
tales que
- (nHojas x) es el número de hojas del árbol x. Por ejemplo,
|
1 |
nHojas (N 9 (N 3 (H 2) (H 4)) (H 7)) == 3 |
- (nNodos x) es el número de nodos del árbol x. Por ejemplo,
|
1 |
nNodos (N 9 (N 3 (H 2) (H 4)) (H 7)) == 2 |
Comprobar con QuickCheck que en todo árbol binario el número de sus hojas es igual al número de sus nodos más uno.
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 |
import Test.QuickCheck data Arbol a = H a | N a (Arbol a) (Arbol a) deriving (Show, Eq) nHojas :: Arbol a -> Int nHojas (H _) = 1 nHojas (N _ i d) = nHojas i + nHojas d nNodos :: Arbol a -> Int nNodos (H _) = 0 nNodos (N _ i d) = 1 + nNodos i + nNodos d -- Comprobación de equivalencia -- ============================ -- (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_nHojas :: Arbol Int -> Bool prop_nHojas x = nHojas x == nNodos x + 1 -- La comprobación es -- λ> quickCheck prop_nHojas -- 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 |
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 nHojas(a: Arbol[A]) -> int: match a: case H(_): return 1 case N(_, i, d): return nHojas(i) + nHojas(d) assert False def nNodos(a: Arbol[A]) -> int: match a: case H(_): return 0 case N(_, i, d): return 1 + nNodos(i) + nNodos(d) assert False # Comprobación de equivalencia # ============================ # (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))]) # La propiedad es @given(st.integers(min_value=1, max_value=10)) def test_nHojas(n: int) -> None: a = arbolArbitrario(n) assert nHojas(a) == nNodos(a) + 1 # La comprobación es # src> poetry run pytest -q numero_de_hojas_de_un_arbol_binario.py # 1 passed in 0.10s |