Los árboles binarios con valores en los nodos se pueden definir por
|
data Arbol a = H | N a (Arbol a) (Arbol a) deriving (Show, Eq) |
Por ejemplo, el árbol
|
9 / \ / \ 8 6 / \ / \ 3 2 4 5 |
se puede representar por
|
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
|
sumaArbol :: Num a => Arbol1 a -> a |
tal sumaArbol x
es la suma de los valores que hay en el árbol x
. Por ejemplo,
|
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.
Soluciones en Haskell
|
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 |
Soluciones en Python
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 |
Se puede imprimir o compartir con