Imagen especular de un árbol binario

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

   espejo :: Arbol a -> Arbol a

1	espejo :: Arbol a -> Arbol a

tal que espejo x es la imagen especular del árbol x. Por ejemplo,

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

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

Comprobar con QuickCheck las siguientes propiedades, para todo árbol x,

   espejo (espejo x) = x
   reverse (preorden (espejo x)) = postorden x
   postorden (espejo x) = reverse (preorden x)

espejo (espejo x) = x

reverse (preorden (espejo x)) = postorden x

postorden (espejo x) = reverse (preorden x)

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)

espejo :: Arbol a -> Arbol a
espejo (H x)     = H x
espejo (N x i d) = N x (espejo d) (espejo i)

-- Generador para las comprobaciones
-- =================================

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

-- Funciones auxiliares para la comprobación
-- =========================================

-- (preorden x) 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]
preorden :: Arbol a -> [a]
preorden (H x)     = [x]
preorden (N x i d) = x : preorden i ++ preorden d

-- (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]
postorden :: Arbol a -> [a]
postorden (H x)     = [x]
postorden (N x i d) = postorden i ++ postorden d ++ [x]

-- Comprobación de las propiedades
-- ===============================

-- Las propiedades son
prop_espejo :: Arbol Int -> Bool
prop_espejo x =
  espejo (espejo x) == x &&
  reverse (preorden (espejo x)) == postorden x &&
  postorden (espejo x) == reverse (preorden x)

-- La comprobación es
--    λ> quickCheck prop_espejo
--    OK, passed 100 tests.

import Test.QuickCheck

data Arbol a = H a

| N a (Arbol a) (Arbol a)

deriving (Show, Eq)

espejo :: Arbol a -> Arbol a

espejo (H x) = H x

espejo (N x i d) = N x (espejo d) (espejo i)

-- Generador para las comprobaciones

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

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

-- Funciones auxiliares para la comprobación

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

-- (preorden x) 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]

preorden :: Arbol a -> [a]

preorden (H x) = [x]

preorden (N x i d) = x : preorden i ++ preorden d

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

postorden :: Arbol a -> [a]

postorden (H x) = [x]

postorden (N x i d) = postorden i ++ postorden d ++ [x]

-- Comprobación de las propiedades

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

-- Las propiedades son

prop_espejo :: Arbol Int -> Bool

prop_espejo x =

espejo (espejo x) == x &&

reverse (preorden (espejo x)) == postorden x &&

postorden (espejo x) == reverse (preorden x)

-- La comprobación es

-- λ> quickCheck prop_espejo

-- 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 espejo(a: Arbol[A]) -> Arbol[A]:
    match a:
        case H(x):
            return H(x)
        case N(x, i, d):
            return N(x, espejo(d), espejo(i))
    assert False

# Generador para las comprobaciones
# =================================

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

# Funciones auxiliares para la comprobación
# =========================================

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

# (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]
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 las propiedades
# ===============================

# Las propiedades son
@given(st.integers(min_value=1, max_value=10))
def test_espejo(n: int) -> None:
    x = arbolArbitrario(n)
    assert espejo(espejo(x)) == x
    assert list(reversed(preorden(espejo(x)))) == postorden(x)
    assert postorden(espejo(x)) == list(reversed(preorden(x)))

# La comprobación es
#    src> poetry run pytest -q imagen_especular_de_un_arbol_binario.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 espejo(a: Arbol[A]) -> Arbol[A]:

match a:

case H(x):

return H(x)

case N(x, i, d):

return N(x, espejo(d), espejo(i))

assert False

# Generador para las comprobaciones

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

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

# Funciones auxiliares para la comprobación

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

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

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

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

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 las propiedades

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

# Las propiedades son

@given(st.integers(min_value=1, max_value=10))

def test_espejo(n: int) -> None:

x = arbolArbitrario(n)

assert espejo(espejo(x)) == x

assert list(reversed(preorden(espejo(x)))) == postorden(x)

assert postorden(espejo(x)) == list(reversed(preorden(x)))

# La comprobación es

# src> poetry run pytest -q imagen_especular_de_un_arbol_binario.py

# 1 passed in 0.16s

Un comentario

Para definir la función espejo, podemos utilizar recursión. En el caso de un nodo hoja, no necesitamos hacer nada, simplemente devolvemos el nodo. En el caso de un nodo con hijos, intercambiamos los hijos y devolvemos el resultado:

espejo :: Arbol a -> Arbol a
espejo (H x) = H x
espejo (N x l r) = N x (espejo r) (espejo l)

espejo (N x l r) = N x (espejo r) (espejo l)

Ahora podemos comprobar las propiedades con QuickCheck. Para ello, primero debemos definir una función que genere árboles aleatorios:

import Test.QuickCheck
import Data.List

instance Arbitrary a => Arbitrary (Arbol a) where
  arbitrary = sized arbol
    where
      arbol 0 = return (H 0)
      arbol n = do
        x <- arbitrary
        l <- arbol (n `div` 2)
        r <- arbol (n `div` 2)
        return (N x l r)

import Data.List

arbitrary = sized arbol

where

arbol 0 = return (H 0)

arbol n = do

x <- arbitrary

l <- arbol (n `div` 2)

r <- arbol (n `div` 2)

return (N x l r)

Con esto podemos definir la primera propiedad:

prop_espejo_inversa :: Arbol Int -> Bool
prop_espejo_inversa x = espejo (espejo x) == x

1 2	prop_espejo_inversa :: Arbol Int -> Bool prop_espejo_inversa x = espejo (espejo x) == x

Para comprobar las propiedades, podemos utilizar la función quickCheck:

main = do
  quickCheck prop_espejo_inversa

1 2	main = do quickCheck prop_espejo_inversa

Responder

Imagen especular de un árbol binario

Un comentario

Leave a Reply to chatGPTCancel reply

Entradas recientes

Buscar

Correo electrónico

Se puede imprimir o compartir con

Un comentario

Leave a Reply to chatGPTCancel reply

Entradas recientes

Buscar

Correo electrónico