El árbol binario
5
/ \
/ \
3 7
/ \ / \
1 4 6 9 |
5
/ \
/ \
3 7
/ \ / \
1 4 6 9
se puede representar por
ejArbol = Nodo (Nodo (Hoja 1) 3 (Hoja 4))
5
(Nodo (Hoja 6) 7 (Hoja 9)) |
ejArbol = Nodo (Nodo (Hoja 1) 3 (Hoja 4))
5
(Nodo (Hoja 6) 7 (Hoja 9))
El tipo de los árboles binarios se puede definir por
data Arbol = Hoja Int
| Nodo Arbol Int Arbol |
data Arbol = Hoja Int
| Nodo Arbol Int Arbol
Definir las funciones
ocurre :: Int -> Arbol -> Bool
aplana :: Arbol -> [Int] |
ocurre :: Int -> Arbol -> Bool
aplana :: Arbol -> [Int]
tales que
ocurre m a
se verifica si m
ocurre en el árbol a
. Por ejemplo,
ocurre 4 ejArbol == True
ocurre 10 ejArbol == False |
ocurre 4 ejArbol == True
ocurre 10 ejArbol == False
aplana a
es la lista obtenida aplanando el árbol a
. Por ejemplo,
aplana ejArbol == [1,3,4,5,6,7,9] |
aplana ejArbol == [1,3,4,5,6,7,9]
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
Soluciones en Haskell
data Arbol = Hoja Int
| Nodo Arbol Int Arbol
ejArbol :: Arbol
ejArbol = Nodo (Nodo (Hoja 1) 3 (Hoja 4))
5
(Nodo (Hoja 6) 7 (Hoja 9))
ocurre :: Int -> Arbol -> Bool
ocurre m (Hoja n) = m == n
ocurre m (Nodo i n d) = m == n || ocurre m i || ocurre m d
aplana :: Arbol -> [Int]
aplana (Hoja n) = [n]
aplana (Nodo i n d) = aplana i ++ [n] ++ aplana d |
data Arbol = Hoja Int
| Nodo Arbol Int Arbol
ejArbol :: Arbol
ejArbol = Nodo (Nodo (Hoja 1) 3 (Hoja 4))
5
(Nodo (Hoja 6) 7 (Hoja 9))
ocurre :: Int -> Arbol -> Bool
ocurre m (Hoja n) = m == n
ocurre m (Nodo i n d) = m == n || ocurre m i || ocurre m d
aplana :: Arbol -> [Int]
aplana (Hoja n) = [n]
aplana (Nodo i n d) = aplana i ++ [n] ++ aplana d
Soluciones en Python
from dataclasses import dataclass
@dataclass
class Arbol:
pass
@dataclass
class Hoja(Arbol):
x: int
@dataclass
class Nodo(Arbol):
i: Arbol
x: int
d: Arbol
ejArbol = Nodo(Nodo(Hoja(1), 3, Hoja(4)),
5,
Nodo(Hoja(6), 7, Hoja(9)))
def ocurre(m: int, a: Arbol) -> bool:
match a:
case Hoja(n):
return m == n
case Nodo(i, n, d):
return m == n or ocurre(m, i) or ocurre(m, d)
assert False
def aplana(a: Arbol) -> list[int]:
match a:
case Hoja(n):
return [n]
case Nodo(i, n, d):
return aplana(i) + [n] + aplana(d)
assert False |
from dataclasses import dataclass
@dataclass
class Arbol:
pass
@dataclass
class Hoja(Arbol):
x: int
@dataclass
class Nodo(Arbol):
i: Arbol
x: int
d: Arbol
ejArbol = Nodo(Nodo(Hoja(1), 3, Hoja(4)),
5,
Nodo(Hoja(6), 7, Hoja(9)))
def ocurre(m: int, a: Arbol) -> bool:
match a:
case Hoja(n):
return m == n
case Nodo(i, n, d):
return m == n or ocurre(m, i) or ocurre(m, d)
assert False
def aplana(a: Arbol) -> list[int]:
match a:
case Hoja(n):
return [n]
case Nodo(i, n, d):
return aplana(i) + [n] + aplana(d)
assert False