El tipo de los árboles binarios con valores en las hojas
1. El tipo de los árboles binarios con valores en las hojas en Haskell
El árbol binario
|
1 2 3 4 5 6 |
· / \ / \ · · / \ / \ 1 4 6 9 |
se puede representar por
|
1 2 |
ejArbol = Nodo (Nodo (Hoja 1) (Hoja 4)) (Nodo (Hoja 6) (Hoja 9)) |
usando el tipo de los árboles binarios con valores en las hojas definido como se muestra a continuación.
|
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 |
data Arbol a = Hoja a | Nodo (Arbol a) (Arbol a) deriving (Eq, Show) -- (arbolArbitrario n) es un árbol aleatorio de altura n. Por ejemplo, -- λ> sample (arbolArbitrario 3 :: Gen (Arbol Int)) -- Nodo (Nodo (Nodo (Hoja 0) (Hoja 0)) (Hoja 0)) (Hoja 0) -- Nodo (Nodo (Hoja 4) (Hoja 8)) (Hoja (-4)) -- Nodo (Nodo (Nodo (Hoja 4) (Hoja 10)) (Hoja (-6))) (Hoja (-1)) -- Nodo (Nodo (Hoja 3) (Hoja 6)) (Hoja (-5)) -- Nodo (Nodo (Hoja (-11)) (Hoja (-13))) (Hoja 14) -- Nodo (Nodo (Hoja (-7)) (Hoja 15)) (Hoja (-2)) -- Nodo (Nodo (Hoja (-9)) (Hoja (-2))) (Hoja (-6)) -- Nodo (Nodo (Hoja (-15)) (Hoja (-16))) (Hoja (-20)) arbolArbitrario :: Arbitrary a => Int -> Gen (Arbol a) arbolArbitrario n | n <= 1 = Hoja <$> arbitrary | otherwise = do k <- choose (2, n - 1) Nodo <$> arbolArbitrario k <*> arbolArbitrario (n - k) -- Arbol es subclase de Arbitraria instance Arbitrary a => Arbitrary (Arbol a) where arbitrary = sized arbolArbitrario shrink (Hoja x) = Hoja <$> shrink x shrink (Nodo l r) = l : r : [Nodo l' r | l' <- shrink l] ++ [Nodo l r' | r' <- shrink r] |
2. El tipo de los árboles binarios con valores en las hojas en Python
El árbol binario
|
1 2 3 4 5 6 |
· / \ / \ · · / \ / \ 1 4 6 9 |
se puede representar por
|
1 2 |
ejArbol = Nodo(Nodo(Hoja(1), Hoja(4)), Nodo(Hoja(6), Hoja(9))) |
usando el tipo de los árboles binarios con valores en las hojas definido como se muestra a continuación.
|
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 |
from dataclasses import dataclass from typing import Generic, TypeVar from random import randint A = TypeVar("A") @dataclass class Arbol(Generic[A]): pass @dataclass class Hoja(Arbol[A]): x: A @dataclass class Nodo(Arbol[A]): i: Arbol[A] d: Arbol[A] # Generador # ========= # arbolArbitrario(n) es un árbol aleatorio de orden n. Por ejemplo, # >>> arbolArbitrario(2) # Nodo(i=Nodo(i=Hoja(x=6), d=Hoja(x=3)), d=Nodo(i=Hoja(x=4), d=Hoja(x=4))) # >>> arbolArbitrario(2) # Nodo(i=Nodo(i=Hoja(x=9), d=Hoja(x=6)), d=Nodo(i=Hoja(x=9), d=Hoja(x=8))) def arbolArbitrario(n: int) -> Arbol[int]: if n == 0: return Hoja(randint(1, 10)) if n == 1: return Nodo(arbolArbitrario(0), arbolArbitrario(0)) k = min(randint(1, n + 1), n - 1) return Nodo(arbolArbitrario(k), arbolArbitrario(n - k)) |