Menu Close

Profundidad de un árbol binario

José A. Alonso, ,

El árbol binario

        9
       / \
      /   \
     3     7
    / \
   2   4

se puede representar por

   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)

Definir la función

   profundidad :: Arbol a -> Int

tal que profundidad x es la profundidad del árbol x. Por ejemplo,

   profundidad (N 9 (N 3 (H 2) (H 4)) (H 7))              ==  2
   profundidad (N 9 (N 3 (H 2) (N 1 (H 4) (H 5))) (H 7))  ==  3
   profundidad (N 4 (N 5 (H 4) (H 2)) (N 3 (H 7) (H 4)))  ==  2

Comprobar con QuickCheck que para todo árbol biario x, se tiene que

   nNodos x <= 2^(profundidad x) - 1

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)
 
profundidad :: Arbol a -> Int
profundidad (H _)     = 0
profundidad (N _ i d) = 1 + max (profundidad i) (profundidad 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_nNodosProfundidad :: Arbol Int -> Bool
prop_nNodosProfundidad x =
   nNodos x <= 2 ^ profundidad x - 1
 
-- (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
 
-- La comprobación es
--    λ> quickCheck prop_nNodosProfundidad
--    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 profundidad(a: Arbol[A]) -> int:
    match a:
        case H(_):
            return 0
        case N(_, i, d):
            return 1 + max(profundidad(i), profundidad(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))])
 
# 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
 
# La propiedad es
@given(st.integers(min_value=1, max_value=10))
def test_nHojas(n: int) -> None:
    a = arbolArbitrario(n)
    assert nNodos(a) <= 2 ** profundidad(a) - 1
 
# La comprobación es
#    src> poetry run pytest -q profundidad_de_un_arbol_binario.py
#    1 passed in 0.11s
Leer más →

Número de hojas de un árbol binario

José A. Alonso, ,

El árbol binario

        9
       / \
      /   \
     3     7
    / \
   2   4

se puede representar por

   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)

Definir las funciones

   nHojas :: Arbol a -> Int
   nNodos :: Arbol a -> Int

tales que

  • (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
  • (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

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.


Soluciones en Haskell

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.


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

El tipo de las expresiones aritméticas: Número de operaciones en una expresión

José A. Alonso, ,

Se considera el tipo de las expresiones aritméticas definido por

   data Expr = Lit Int
             | Suma Expr Expr
             | Op Expr
             | SiCero Expr Expr Expr
     deriving (Eq, Show)

formado por

  • literales (p.e. Lit 7),
  • sumas (p.e. Suma (Lit 7) (Suma (Lit 3) (Lit 5)))
  • opuestos (p.e. Op (Suma (Op (Lit 7)) (Suma (Lit 3) (Lit 5))))
  • expresiones condicionales (p.e. (SiCero (Lit 3) (Lit 4) (Lit 5))

Definir la función

   numeroOps :: Expr -> Int

tal que numeroOps e es el número de operaciones de e. Por ejemplo,

   numeroOps (Lit 3)                      ==  0
   numeroOps (Suma (Lit 7) (Op (Lit 5)))  ==  2

Soluciones

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


Soluciones en Haskell

data Expr = Lit Int
          | Suma Expr Expr
          | Op Expr
          | SiCero Expr Expr Expr
  deriving (Eq, Show)
 
numeroOps :: Expr -> Int
numeroOps (Lit _)        = 0
numeroOps (Suma x y)     = 1 + numeroOps x + numeroOps y
numeroOps (Op x)         = 1 + numeroOps x
numeroOps (SiCero x y z) = 1 + numeroOps x + numeroOps y + numeroOps z


Soluciones en Python

from dataclasses import dataclass
 
 
@dataclass
class Expr:
    pass
 
@dataclass
class Lit(Expr):
    x: int
 
@dataclass
class Suma(Expr):
    x: Expr
    y: Expr
 
@dataclass
class Op(Expr):
    x: Expr
 
@dataclass
class SiCero(Expr):
    x: Expr
    y: Expr
    z: Expr
 
def numeroOps(e: Expr) -> int:
    match e:
        case Lit(n):
            return 0
        case Suma(x, y):
            return 1 + numeroOps(x) + numeroOps(y)
        case Op(x):
            return 1 + numeroOps(x)
        case SiCero(x, y, z):
            return 1 + numeroOps(x) + numeroOps(y) + numeroOps(z)
    assert False
Leer más →

El tipo de las expresiones aritméticas: Valor de la resta

José A. Alonso, ,

Se considera el tipo de las expresiones aritméticas definido por

   data Expr = Lit Int
             | Suma Expr Expr
             | Op Expr
             | SiCero Expr Expr Expr
     deriving (Eq, Show)

formado por

  • literales (p.e. Lit 7),
  • sumas (p.e. Suma (Lit 7) (Suma (Lit 3) (Lit 5)))
  • opuestos (p.e. Op (Suma (Op (Lit 7)) (Suma (Lit 3) (Lit 5))))
  • expresiones condicionales (p.e. (SiCero (Lit 3) (Lit 4) (Lit 5))

La función para calcular el valor de una expresión es

   valor :: Expr -> Int
   valor (Lit n)        = n
   valor (Suma x y)     = valor x + valor y
   valor (Op x)         = - valor x
   valor (SiCero x y z) | valor x == 0 = valor y
                        | otherwise    = valor z

Definir la función

   resta :: Expr -> Expr -> Expr

tal que resta e1 e2 es la expresión correspondiente a la diferencia de e1 y e2. Por ejemplo,

   resta (Lit 42) (Lit 2)  ==  Suma (Lit 42) (Op (Lit 2))

Comprobar con QuickCheck que

   valor (resta x y) == valor x - valor y

Soluciones

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


Soluciones en Haskell

module Valor_de_la_resta where
 
import Test.QuickCheck
 
data Expr = Lit Int
          | Suma Expr Expr
          | Op Expr
          | SiCero Expr Expr Expr
  deriving (Eq, Show)
 
valor :: Expr -> Int
valor (Lit n)        = n
valor (Suma x y)     = valor x + valor y
valor (Op x)         = - valor x
valor (SiCero x y z) | valor x == 0 = valor y
                     | otherwise    = valor z
 
resta :: Expr -> Expr -> Expr
resta x y = Suma x (Op y)
 
-- Comprobación de la propiedad
-- ============================
 
-- (exprArbitraria n) es una expresión aleatoria de tamaño n. Por
-- ejemplo,
--    λ> sample (exprArbitraria 3)
--    Op (Op (Lit 0))
--    SiCero (Lit 0) (Lit (-2)) (Lit (-1))
--    Op (Suma (Lit 3) (Lit 0))
--    Op (Lit 5)
--    Op (Lit (-1))
--    Op (Op (Lit 9))
--    Suma (Lit (-12)) (Lit (-12))
--    Suma (Lit (-9)) (Lit 10)
--    Op (Suma (Lit 8) (Lit 15))
--    SiCero (Lit 16) (Lit 9) (Lit (-5))
--    Suma (Lit (-3)) (Lit 1)
exprArbitraria :: Int -> Gen Expr
exprArbitraria n
  | n <= 1 = Lit <$> arbitrary
  | otherwise = oneof
                [ Lit <$> arbitrary
                , let m = div n 2
                  in Suma <$> exprArbitraria m <*> exprArbitraria m
                , Op <$> exprArbitraria (n - 1)
                , let m = div n 3
                  in SiCero <$> exprArbitraria m
                            <*> exprArbitraria m
                            <*> exprArbitraria m ]
 
-- Expr es subclase de Arbitrary
instance Arbitrary Expr where
  arbitrary = sized exprArbitraria
 
 
-- La propiedad es
prop_resta :: Expr -> Expr -> Property
prop_resta x y =
  valor (resta x y) === valor x - valor y
 
-- La comprobación es
--    λ> quickCheck prop_resta
--    +++ OK, passed 100 tests.


Soluciones en Python

from dataclasses import dataclass
from random import choice, randint
 
from hypothesis import given
from hypothesis import strategies as st
 
 
@dataclass
class Expr:
    pass
 
@dataclass
class Lit(Expr):
    x: int
 
@dataclass
class Suma(Expr):
    x: Expr
    y: Expr
 
@dataclass
class Op(Expr):
    x: Expr
 
@dataclass
class SiCero(Expr):
    x: Expr
    y: Expr
    z: Expr
 
def valor(e: Expr) -> int:
    match e:
        case Lit(n):
            return n
        case Suma(x, y):
            return valor(x) + valor(y)
        case Op(x):
            return -valor(x)
        case SiCero(x, y, z):
            return valor(y) if valor(x) == 0 else valor(z)
    assert False
 
def resta(x: Expr, y: Expr) -> Expr:
    return Suma(x, Op(y))
 
# -- Comprobación de la propiedad
# -- ============================
 
# exprArbitraria(n) es una expresión aleatoria de tamaño n. Por
# ejemplo,
#    >>> exprArbitraria(3)
#    Op(x=Op(x=Lit(x=9)))
#    >>> exprArbitraria(3)
#    Op(x=SiCero(x=Lit(x=6), y=Lit(x=2), z=Lit(x=6)))
#    >>> exprArbitraria(3)
#    Suma(x=Lit(x=8), y=Lit(x=2))
def exprArbitraria(n: int) -> Expr:
    if n <= 1:
        return Lit(randint(0, 10))
    m = n // 2
    return choice([Lit(randint(0, 10)),
                   Suma(exprArbitraria(m), exprArbitraria(m)),
                   Op(exprArbitraria(n - 1)),
                   SiCero(exprArbitraria(m),
                          exprArbitraria(m),
                          exprArbitraria(m))])
 
# La propiedad es
@given(st.integers(min_value=1, max_value=10),
       st.integers(min_value=1, max_value=10))
def test_mismaForma(n1: int, n2: int) -> None:
    x = exprArbitraria(n1)
    y = exprArbitraria(n2)
    assert valor(resta(x, y)) == valor(x) - valor(y)
 
# La comprobación es
#    src> poetry run pytest -q valor_de_la_resta.py
#    1 passed in 0.21s
Leer más →

El tipo de las expresiones aritméticas: Valor de una expresión

José A. Alonso, ,

Se considera el tipo de las expresiones aritméticas definido por

   data Expr =
       Lit Int
     | Suma Expr Expr
     | Op Expr
     | SiCero Expr Expr Expr
     deriving (Eq, Show)

formado por

  • literales (p.e. Lit 7),
  • sumas (p.e. Suma (Lit 7) (Suma (Lit 3) (Lit 5)))
  • opuestos (p.e. Op (Suma (Op (Lit 7)) (Suma (Lit 3) (Lit 5))))
  • expresiones condicionales (p.e. (SiCero (Lit 3) (Lit 4) (Lit 5))

Definir la función

   valor :: Expr -> Int

tal que valor e es el valor de la expresión e (donde el valor de SiCero e e1 e2 es el valor de e1 si el valor de e es cero y el es el valor de e2, en caso contrario). Por ejemplo,

   valor (Op (Suma (Lit 3) (Lit 5)))      ==  -8
   valor (SiCero (Lit 0) (Lit 4) (Lit 5)) == 4
   valor (SiCero (Lit 1) (Lit 4) (Lit 5)) == 5

Soluciones

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


Soluciones en Haskell

data Expr =
    Lit Int
  | Suma Expr Expr
  | Op Expr
  | SiCero Expr Expr Expr
  deriving (Eq, Show)
 
valor :: Expr -> Int
valor (Lit n)        = n
valor (Suma x y)     = valor x + valor y
valor (Op x)         = - valor x
valor (SiCero x y z) | valor x == 0 = valor y
                     | otherwise    = valor z


Soluciones en Python

from dataclasses import dataclass
 
 
@dataclass
class Expr:
    pass
 
@dataclass
class Lit(Expr):
    x: int
 
@dataclass
class Suma(Expr):
    x: Expr
    y: Expr
 
@dataclass
class Op(Expr):
    x: Expr
 
@dataclass
class SiCero(Expr):
    x: Expr
    y: Expr
    z: Expr
 
def valor(e: Expr) -> int:
    match e:
        case Lit(n):
            return n
        case Suma(x, y):
            return valor(x) + valor(y)
        case Op(x):
            return -valor(x)
        case SiCero(x, y, z):
            return valor(y) if valor(x) == 0 else valor(z)
    assert False
Leer más →