19-diciembre-2022 – Exercitium

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

Día: 19-diciembre-2022

Recorrido de árboles binarios

Entradas recientes

Buscar

Correo electrónico