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
preorden
es 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 x
es 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 |