haskell - 在 Haskell 中查找二叉树的值

Question

给出的代码:

data Tree a b = Leaf a | Branch b [Tree a b] deriving (Eq,Read,Show)

--用这些树定义

t1 = Branch "+" [Leaf 10, Leaf 20, Branch "*" [Leaf 2, Leaf 3, Leaf 4], Leaf 50]

t2 = Branch "*" [t1,t1,t1] //should multiply t1 3 times

如何找到 t1 的值？例如，10 + 20 + (2 * 3 * 4) + 50 = 104

我已经启动了解决函数:

solve (Leaf a) = a 
solve (Branch _ ts) = //not sure how to make it solve itself recursively here.

如有任何帮助，我们将不胜感激。谢谢。

Answer 1

只需递归调用solve即可。您也可以为运算符创建自己的类型，而不是使用字符串。

data Op = Plus | Mult

solve :: Tree Int Op -> Int
solve (Leaf a) = a
solve (Branch Plus args) = sum (map solve args)
solve (Branch Mult args) = product (map solve args)