我需要编写一个函数,以查找二叉树中所有元素的总和。
二叉树的定义如下:
datatype 'a tree= Leaf of 'a | Node of 'a tree * 'a * 'a tree
我不知道该怎么做。我承认我是SML的初学者。
例如:sumTree (Node (Node (Leaf 1, 3, Leaf 2), 7, Leaf 4))
应该返回17。sumTree是函数名。
谢谢您的帮助。
我需要编写一个函数,以查找二叉树中所有元素的总和。
二叉树的定义如下:
datatype 'a tree= Leaf of 'a | Node of 'a tree * 'a * 'a tree
我不知道该怎么做。我承认我是SML的初学者。
例如:sumTree (Node (Node (Leaf 1, 3, Leaf 2), 7, Leaf 4))
应该返回17。sumTree是函数名。
谢谢您的帮助。
我希望你能花时间理解这个。如果有任何问题,请让我知道:
(*
* This is a recursive datatype, because the Node constructor contains two
* elements of type `tree`, the type which we're currently defining.
*)
datatype 'a tree =
Leaf of 'a
| Node of 'a tree * 'a * 'a tree
(*
* Notice how the structure of the `sumTree` function follows the structure
* of the `tree` datatype. But `tree` is a recursive datatype, which means
* that `sumTree` will probably be a recursive function. This is called
* structural recursion. We recurse accordingly to the structure of the type.
*)
fun sumTree (Leaf n) = n
| sumTree (Node (left, n, right)) = (sumTree left) + n + (sumTree right)
Leaf
),并在复杂情况(Node
)中依赖于简单情况的解决方案。