PFH: La semana en Exercitium (31 de diciembre de 2022)
Esta semana he publicado en Exercitium las soluciones de los siguientes problemas:
- 1. Rama izquierda de un árbol binario
- 2. Árboles balanceados
- 3. Árboles con bordes iguales
- 4. Árboles con igual estructura
- 5. Existencia de elementos del árbol que verifican una propiedad
A continuación se muestran las soluciones.
1. Rama izquierda de un árbol binario
Los árboles binarios con valores en los nodos se pueden definir por
|
1 2 3 |
data Arbol a = H | N a (Arbol a) (Arbol a) deriving (Show, Eq) |
Por ejemplo, el árbol
|
1 2 3 4 5 6 |
9 / \ / \ 8 6 / \ / \ 3 2 4 5 |
se puede representar por
|
1 |
N 9 (N 8 (N 3 H H) (N 2 H H)) (N 6 (N 4 H H) (N 5 H H)) |
Definir la función
|
1 |
ramaIzquierda :: Arbol a -> [a] |
tal que ramaIzquierda a es la lista de los valores de los nodos de la rama izquierda del árbol a. Por ejemplo,
|
1 2 |
λ> ramaIzquierda (N 2 (N 5 (N 3 H H) (N 7 H H)) (N 4 H H)) [2,5,3] |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
|
1 2 3 4 5 6 7 |
data Arbol a = H | N a (Arbol a) (Arbol a) deriving (Show, Eq) ramaIzquierda :: Arbol a -> [a] ramaIzquierda H = [] ramaIzquierda (N x i _) = x : ramaIzquierda i |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
from dataclasses import dataclass from typing import Generic, TypeVar A = TypeVar("A") @dataclass class Arbol(Generic[A]): pass @dataclass class H(Arbol[A]): pass @dataclass class N(Arbol[A]): x: A i: Arbol[A] d: Arbol[A] def ramaIzquierda(a: Arbol[A]) -> list[A]: match a: case H(): return [] case N(x, i, _): return [x] + ramaIzquierda(i) assert False |
2. Árboles balanceados
Los árboles binarios con valores en los nodos se pueden definir por
|
1 2 3 |
data Arbol a = H | N a (Arbol a) (Arbol a) deriving (Show, Eq) |
Por ejemplo, el árbol
|
1 2 3 4 5 6 |
9 / \ / \ 8 6 / \ / \ 3 2 4 5 |
se puede representar por
|
1 |
N 9 (N 8 (N 3 H H) (N 2 H H)) (N 6 (N 4 H H) (N 5 H H)) |
Diremos que un árbol está balanceado si para cada nodo la diferencia entre el número de nodos de sus subárboles izquierdo y derecho es menor o igual que uno.
Definir la función
|
1 |
balanceado :: Arbol a -> Bool |
tal que (balanceado a) se verifica si el árbol a está balanceado. Por ejemplo,
|
1 2 3 4 |
λ> balanceado (N 5 H (N 3 H H)) True λ> balanceado (N 4 (N 3 (N 2 H H) H) (N 5 H (N 6 H (N 7 H H)))) False |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
data Arbol a = H | N a (Arbol a) (Arbol a) deriving (Show, Eq) balanceado :: Arbol a -> Bool balanceado H = True balanceado (N _ i d) = abs (numeroNodos i - numeroNodos d) <= 1 && balanceado i && balanceado d -- (numeroNodos a) es el número de nodos del árbol a. Por ejemplo, -- numeroNodos (N 5 H (N 3 H H)) == 2 numeroNodos :: Arbol a -> Int numeroNodos H = 0 numeroNodos (N _ i d) = 1 + numeroNodos i + numeroNodos d |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
from dataclasses import dataclass from typing import Generic, TypeVar A = TypeVar("A") @dataclass class Arbol(Generic[A]): pass @dataclass class H(Arbol[A]): pass @dataclass class N(Arbol[A]): x: A i: Arbol[A] d: Arbol[A] def numeroNodos(a: Arbol[A]) -> int: match a: case H(): return 0 case N(_, i, d): return 1 + numeroNodos(i) + numeroNodos(d) assert False def balanceado(a: Arbol[A]) -> bool: match a: case H(): return True case N(_, i, d): return abs(numeroNodos(i) - numeroNodos(d)) <= 1 \ and balanceado(i) and balanceado(d) assert False |
3. Árboles con bordes iguales
Los árboles binarios con valores en las hojas se pueden definir por
|
1 2 3 |
data Arbol a = H a | N (Arbol a) (Arbol a) deriving Show |
Por ejemplo, los árboles
|
1 2 3 4 5 6 |
árbol1 árbol2 árbol3 árbol4 o o o o / \ / \ / \ / \ 1 o o 3 o 3 o 1 / \ / \ / \ / \ 2 3 1 2 1 4 2 3 |
se representan por
|
1 2 3 4 5 |
arbol1, arbol2, arbol3, arbol4 :: Arbol Int arbol1 = N (H 1) (N (H 2) (H 3)) arbol2 = N (N (H 1) (H 2)) (H 3) arbol3 = N (N (H 1) (H 4)) (H 3) arbol4 = N (N (H 2) (H 3)) (H 1) |
Definir la función
|
1 |
igualBorde :: Eq a => Arbol a -> Arbol a -> Bool |
tal que igualBorde t1 t2 se verifica si los bordes de los árboles t1 y t2 son iguales. Por ejemplo,
|
1 2 3 |
igualBorde arbol1 arbol2 == True igualBorde arbol1 arbol3 == False igualBorde arbol1 arbol4 == False |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
data Arbol a = N (Arbol a) (Arbol a) | H a deriving Show arbol1, arbol2, arbol3, arbol4 :: Arbol Int arbol1 = N (H 1) (N (H 2) (H 3)) arbol2 = N (N (H 1) (H 2)) (H 3) arbol3 = N (N (H 1) (H 4)) (H 3) arbol4 = N (N (H 2) (H 3)) (H 1) igualBorde :: Eq a => Arbol a -> Arbol a -> Bool igualBorde t1 t2 = borde t1 == borde t2 -- (borde t) es el borde del árbol t; es decir, la lista de las hojas -- del árbol t leídas de izquierda a derecha. Por ejemplo, -- borde arbol4 == [2,3,1] borde :: Arbol a -> [a] borde (N i d) = borde i ++ borde d borde (H x) = [x] |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
from dataclasses import dataclass 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]): i: Arbol[A] d: Arbol[A] arbol1: Arbol[int] = N(H(1), N(H(2), H(3))) arbol2: Arbol[int] = N(N(H(1), H(2)), H(3)) arbol3: Arbol[int] = N(N(H(1), H(4)), H(3)) arbol4: Arbol[int] = N(N(H(2), H(3)), H(1)) # borde(t) es el borde del árbol t; es decir, la lista de las hojas # del árbol t leídas de izquierda a derecha. Por ejemplo, # borde(arbol4) == [2, 3, 1] def borde(a: Arbol[A]) -> list[A]: match a: case H(x): return [x] case N(i, d): return borde(i) + borde(d) assert False def igualBorde(t1: Arbol[A], t2: Arbol[A]) -> bool: return borde(t1) == borde(t2) |
4. Árboles con igual estructura
Los árboles binarios con valores en las hojas y en los nodos se definen por
|
1 2 3 |
data Arbol a = H a | N a (Arbol a) (Arbol a) deriving Show |
Por ejemplo, los árboles
|
1 2 3 4 5 6 |
5 8 5 5 / \ / \ / \ / \ / \ / \ / \ / \ 9 7 9 3 9 2 4 7 / \ / \ / \ / \ / \ / \ 1 4 6 8 1 4 6 2 1 4 6 2 |
se pueden representar por
|
1 2 3 4 5 |
ej3arbol1, ej3arbol2, ej3arbol3, ej3arbol4 :: Arbol Int ej3arbol1 = N 5 (N 9 (H 1) (H 4)) (N 7 (H 6) (H 8)) ej3arbol2 = N 8 (N 9 (H 1) (H 4)) (N3 3 (H 6) (H 2)) ej3arbol3 = N 5 (N 9 (H 1) (H 4)) (H 2) ej3arbol4 = N 5 (H 4) (N 7 (H 6) (H 2)) |
Definir la función
|
1 |
igualEstructura :: Arbol -> Arbol -> Bool |
tal que igualEstructura a1 a2 se verifica si los árboles a1 y a2 tienen la misma estructura. Por ejemplo,
|
1 2 3 |
igualEstructura ej3arbol1 ej3arbol2 == True igualEstructura ej3arbol1 ej3arbol3 == False igualEstructura ej3arbol1 ej3arbol4 == False |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
data Arbol a = H a | N a (Arbol a) (Arbol a) deriving (Show, Eq) ej3arbol1, ej3arbol2, ej3arbol3, ej3arbol4 :: Arbol Int ej3arbol1 = N 5 (N 9 (H 1) (H 4)) (N 7 (H 6) (H 8)) ej3arbol2 = N 8 (N 9 (H 1) (H 4)) (N 3 (H 6) (H 2)) ej3arbol3 = N 5 (N 9 (H 1) (H 4)) (H 2) ej3arbol4 = N 5 (H 4) (N 7 (H 6) (H 2)) igualEstructura :: Arbol a -> Arbol a -> Bool igualEstructura (H _) (H _) = True igualEstructura (N _ i1 d1) (N _ i2 d2) = igualEstructura i1 i2 && igualEstructura d1 d2 igualEstructura _ _ = False |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
from dataclasses import dataclass 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] ej3arbol1: Arbol[int] = N(5, N(9, H(1), H(4)), N(7, H(6), H(8))) ej3arbol2: Arbol[int] = N(8, N(9, H(1), H(4)), N(3, H(6), H(2))) ej3arbol3: Arbol[int] = N(5, N(9, H(1), H(4)), H(2)) ej3arbol4: Arbol[int] = N(5, H(4), N(7, H(6), H(2))) def igualEstructura(a: Arbol[A], b: Arbol[A]) -> bool: match (a, b): case (H(_), H(_)): return True case (N(_, i1, d1), N(_, i2, d2)): return igualEstructura(i1, i2) and igualEstructura(d1, d2) case (_, _): return False assert False |
5. Existencia de elementos del árbol que verifican una propiedad
Los árboles binarios con valores en las hojas y en los nodos se definen por
|
1 2 3 |
data Arbol a = H a | N a (Arbol a) (Arbol a) deriving Show |
Por ejemplo, el árbol
|
1 2 3 4 5 6 |
5 / \ / \ 3 2 / \ 1 4 |
se representa por
|
1 |
N 5 (N 3 (H 1) (H 4)) (H 2) |
Definir la función
|
1 |
algunoArbol :: Arbol t -> (t -> Bool) -> Bool |
tal que algunoArbol a p se verifica si algún elemento del árbol a cumple la propiedad p. Por ejemplo,
|
1 2 |
algunoArbol (N 5 (N 3 (H 1) (H 4)) (H 2)) (>4) == True algunoArbol (N 5 (N 3 (H 1) (H 4)) (H 2)) (>7) == False |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
|
1 2 3 4 5 6 7 |
data Arbol a = H a | N a (Arbol a) (Arbol a) deriving Show algunoArbol :: Arbol a -> (a -> Bool) -> Bool algunoArbol (H x) p = p x algunoArbol (N x i d) p = p x || algunoArbol i p || algunoArbol d p |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
from dataclasses import dataclass from typing import Callable, 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 algunoArbol(a: Arbol[A], p: Callable[[A], bool]) -> bool: match a: case H(x): return p(x) case N(x, i, d): return p(x) or algunoArbol(i, p) or algunoArbol(d, p) assert False |