diciembre 2022 – Página 3

Recorrido de árboles binarios

PorJosé A. Alonso 19-diciembre-202218-diciembre-2022

El árbol binario

/ \

3 7

/ \

2 4

se puede representar por

   N 9 (N 3 (H 2) (H 4)) (H 7)

1	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]

1 2	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]

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 á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]

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.

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

Profundidad de un árbol binario

PorJosé A. Alonso 16-diciembre-202215-diciembre-2022

El árbol binario

/ \

3 7

/ \

2 4

se puede representar por

   N 9 (N 3 (H 2) (H 4)) (H 7)

1	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 la función

   profundidad :: Arbol a -> Int

1	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

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

1	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.

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

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

Número de hojas de un árbol binario

PorJosé A. Alonso 15-diciembre-202214-diciembre-2022

El árbol binario

/ \

3 7

/ \

2 4

se puede representar por

   N 9 (N 3 (H 2) (H 4)) (H 7)

1	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)

1 2	data Arbol a = H a \| N a (Arbol a) (Arbol a)

Definir las funciones

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

1 2	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

1	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

1	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.

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

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

El tipo de los árboles binarios

PorJosé A. Alonso 15-diciembre-202222-abril-2023

1. El tipo de los árboles binarios en Haskell

El árbol binario

/ \

3 7

/ \

2 4

se puede representar por

   N 9 (N 3 (H 2) (H 4)) (H 7)

1	N 9 (N 3 (H 2) (H 4)) (H 7)

usando el tipo de los árboles binarios definido como se muestra a continuación.

import Test.QuickCheck

data Arbol a = H a
             | N a (Arbol a) (Arbol a)
  deriving (Show, Eq)

-- Generador de árboles binarios
-- =============================

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

import Test.QuickCheck

data Arbol a = H a

| N a (Arbol a) (Arbol a)

deriving (Show, Eq)

-- Generador de árboles binarios

-- =============================

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

2. El tipo de los árboles binarios en Python

El árbol binario

/ \

3 7

/ \

2 4

se puede representar por

   N(9, N(3, H(2), H(4)), H(7))

1	N(9, N(3, H(2), H(4)), H(7))

usando la definición de los árboles binarios que se muestra a continuación.

from dataclasses import dataclass
from random import choice, randint
from typing import Generic, TypeVar

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

# Generador de árboles
# ====================

# (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))])

from dataclasses import dataclass

from random import choice, randint

from typing import Generic, TypeVar

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

# Generador de árboles

# ====================

# (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))])

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

PorJosé A. Alonso 14-diciembre-202220-abril-2023

Usando el tipo de las expresiones aritméticas, definir la función

   numeroOps :: Expr -> Int

1	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

1 2	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

import Tipo_expresion_aritmetica (Expr (..))

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

import Tipo_expresion_aritmetica (Expr (..))

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 src.tipo_expresion_aritmetica import Expr, Lit, Op, SiCero, Suma


def numeroOps(e: Expr) -> int:
    match e:
        case Lit(_):
            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

from src.tipo_expresion_aritmetica import Expr, Lit, Op, SiCero, Suma

def numeroOps(e: Expr) -> int:

match e:

case Lit(_):

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

Meses: diciembre 2022

Recorrido de árboles binarios

Profundidad de un árbol binario

Número de hojas de un árbol binario

El tipo de los árboles binarios

1. El tipo de los árboles binarios en Haskell

2. El tipo de los árboles binarios en Python

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

Entradas recientes

Buscar

Correo electrónico