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