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