Los árboles binarios con valores en los nodos se pueden definir por
data Arbol a = H | N a (Arbol1 a) (Arbol1 a) deriving (Show, Eq)
Por ejemplo, el árbol
9 / \ / \ 8 6 / \ / \ 3 2 4 5
se puede representar por
N 9 (N 8 (N 3 H H) (N 2 H H)) (N 6 (N 4 H H) (N 5 H H))
Definir por recursión la función
sumaArbol :: Num a => Arbol1 a -> a
tal sumaArbol x es la suma de los valores que hay en el árbol x. Por ejemplo,
sumaArbol (N 2 (N 5 (N 3 H H) (N 7 H H)) (N 4 H H)) == 21
El árbol, con valores en los nodos,
9
/ \
/ \
/ \
8 6
/ \ / \
3 2 4 5
/\ /\ /\ /\
· ·· ·· · · ·
se puede representar por
N 9 (N 8 (N 3 H H) (N 2 H H)) (N 6 (N 4 H H) (N 5 H H))
usando el tipo de los árboles con valores en los nodos definido como se muestra a continuación.
data Arbol a = H | N a (Arbol a) (Arbol a) deriving (Show, Eq)
El árbol binario, con valores en los nodos,
9
/ \
/ \
/ \
8 6
/ \ / \
3 2 4 5
/\ /\ /\ /\
· ·· ·· · · ·
se puede representar por
N(9, N(8, N(3, H(), H()), N(2, H(), H())), N(6, N(4, H(), H()), N(5, H(), H())))
usando el tipo de los árboles binarios con valores en los nodos definido como se muestra a continuación.
from dataclasses import dataclass @dataclass class Arbol: pass @dataclass class H(Arbol): pass @dataclass class N(Arbol): x: int i: Arbol d: Arbol
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 las funciones
repeatArbol :: a -> Arbol a replicateArbol :: Int -> a -> Arbol a
tales que
repeatArbol x es es árbol con infinitos nodos x. Por ejemplo,takeArbol 0 (repeatArbol 3) == H 3 takeArbol 1 (repeatArbol 3) == N 3 (H 3) (H 3) takeArbol 2 (repeatArbol 3) == N 3 (N 3 (H 3) (H 3)) (N 3 (H 3) (H 3))
replicate n x es el árbol de profundidad n cuyos nodos son x. Por ejemplo,replicateArbol 0 5 == H 5 replicateArbol 1 5 == N 5 (H 5) (H 5) replicateArbol 2 5 == N 5 (N 5 (H 5) (H 5)) (N 5 (H 5) (H 5))
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)
La función take está definida por
take :: Int -> [a] -> [a] take 0 = [] take (n+1) [] = [] take (n+1) (x:xs) = x : take n xs
Definir la función
takeArbol :: Int -> Arbol a -> Arbol a
tal que takeArbol n t es el subárbol de t de profundidad n. Por ejemplo,
takeArbol 0 (N 9 (N 3 (H 2) (H 4)) (H 7)) == H 9 takeArbol 1 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (H 3) (H 7) takeArbol 2 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (N 3 (H 2) (H 4)) (H 7) takeArbol 3 (N 9 (N 3 (H 2) (H 4)) (H 7)) == N 9 (N 3 (H 2) (H 4)) (H 7)
Comprobar con QuickCheck que la profundidad de takeArbol n x es menor o igual que n, para todo número natural n y todo árbol x.
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
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))
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)
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 las funciones
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]
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]
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.
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
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 (N 9 (N 3 (H 2) (H 4)) (H 7)) == 3
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.
El árbol binario
9
/ \
/ \
3 7
/ \
2 4
se puede representar por
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
El árbol binario
9
/ \
/ \
3 7
/ \
2 4
se puede representar por
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))])
Usando el tipo de las expresiones aritméticas, 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