Menu Close

Día: 23 diciembre, 2022

Suma de un árbol

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

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