Suma de un árbol
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 por recursión la función
|
1 |
sumaArbol :: Num a => Arbol1 a -> a |
tal sumaArbol x es la suma de los valores que hay en el árbol x. Por ejemplo,
|
1 |
sumaArbol (N 2 (N 5 (N 3 H H) (N 7 H H)) (N 4 H H)) == 21 |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
|
1 2 3 4 5 6 7 |
data Arbol1 a = H | N a (Arbol1 a) (Arbol1 a) deriving (Show, Eq) sumaArbol :: Num a => Arbol1 a -> a sumaArbol H = 0 sumaArbol (N x i d) = x + sumaArbol i + sumaArbol d |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
from dataclasses import dataclass @dataclass class Arbol: pass @dataclass class H(Arbol): pass @dataclass class N(Arbol): x: int i: Arbol d: Arbol def sumaArbol(a: Arbol) -> int: match a: case H(): return 0 case N(x, i, d): return x + sumaArbol(i) + sumaArbol(d) assert False |