Menu Close

Día: 6 diciembre, 2022

Altura de un árbol binario

José A. Alonso, ,

El árbol binario

        ·
       / \
      /   \
     ·     ·
    / \   / \
   1   4 6   9

se puede representar por

   ejArbol = Nodo (Nodo (Hoja 1) (Hoja 4))
                  (Nodo (Hoja 6) (Hoja 9))

El tipo de los árboles binarios se puede definir por

data Arbol a = Hoja a
| Nodo (Arbol a) (Arbol a)

Definir la función

   altura :: Arbol a -> Int

tal que altura t es la altura del árbol t. Por ejemplo,

   λ> altura (Hoja 1)
   0
   λ> altura (Nodo (Hoja 1) (Hoja 6))
   1
   λ> altura (Nodo (Nodo (Hoja 1) (Hoja 6)) (Hoja 2))
   2
   λ> altura (Nodo (Nodo (Hoja 1) (Hoja 6)) (Nodo (Hoja 2) (Hoja 7)))
   2

Soluciones

A continuación se muestran las soluciones en Haskell y las soluciones en Python.


Soluciones en Haskell

data Arbol a = Hoja a
             | Nodo (Arbol a) (Arbol a)
 
altura :: Arbol a -> Int
altura (Hoja _)   = 0
altura (Nodo i d) = 1 + max (altura i) (altura d)


Soluciones en Python

from dataclasses import dataclass
from typing import Generic, TypeVar
 
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]
 
def altura(a: Arbol[A]) -> int:
    match a:
        case Hoja(_):
            return 0
        case Nodo(i, d):
            return 1 + max(altura(i), altura(d))
    assert False
Leer más →

El tipo de los árboles binarios con valores en las hojas

José A. Alonso, ,

1. El tipo de los árboles binarios con valores en las hojas en Haskell

El árbol binario

        ·
       / \
      /   \
     ·     ·
    / \   / \
   1   4 6   9

se puede representar por

   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.

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   4 6   9

se puede representar por

   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.

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))
Leer más →