SML сумма двоичного дерева

Question

Мне нужно написать функцию, которая найдет сумму всех элементов в двоичном дереве.

То, как оно определено (дерево):

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 - это название функции.

Спасибо за помощь.

Answer 1

Надеюсь, вы потратите время, чтобы это понять. Дайте мне знать, если у вас есть какие-либо вопросы, касающиеся его:

(* 
* 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) полагаться на решения для легкого случая.