El árbol binario
se puede representar por
N 9 (N 3 (H 2) (H 4)) (H 7) |
N 9 (N 3 (H 2) (H 4)) (H 7)
El tipo de los árboles binarios se puede definir por
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)
Definir las funciones
preorden :: Arbol a -> [a]
postorden :: Arbol a -> [a] |
preorden :: Arbol a -> [a]
postorden :: Arbol a -> [a]
tales que
preorden
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]
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 (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.
Soluciones en Haskell
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. |
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.
Soluciones en Python
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 |
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