Prolog:对二叉树中叶子的值求和

Question

我有一个二叉树，对于这个二叉树，我必须添加叶子中包含的值，给定一个类似的谓词:

sum_leafs ([Node, Left, Right], Sum).

我不明白我该怎么做，必须计算叶子的值我应该计算节点的总和，以防 Left 和 Right 都为 nil ..

[Node, nil, nil]

所以我有类似的东西:

sum_leafs([Node, Left, Right], Sum):-
    sum_leafs(Left, Sum_Left),
    sum_leafs(Right, Sum_Right),
    Sum is (Sum_Left + Sum_Right).

我的尝试:

sum_leafs(nil, 0).
sum_leafs([Node, nil, nil], Node).
sum_leafs([_, Left, Right], Sum):-
    sum_leafs(Left, Sum_Left),
    sum_leafs(Right, Sum_Right),
    Sum is (Sum_Left + Sum_Right).

我怎样才能做到这一点？

谢谢

Answer 1

列表不能很好地表示二叉树。让我们开始改变它:

• 空树:nil
• 非空树:t(Left,Value,Right)

使用这种表示，对叶子值求和的谓词可以写成:

sum_leaves(Tree, Sum) :-
    sum_leaves(Tree, 0, Sum).

sum_leaves(nil, Sum, Sum).
sum_leaves(t(nil,Value,nil), Sum0, Sum) :-
    !,
    Sum is Sum0 + Value. 
sum_leaves(t(Left,_,Right), Sum0, Sum) :-
    sum_leaves(Left, Sum0, Sum1),
    sum_leaves(Right, Sum1, Sum).

但是第一个版本不是尾递归的。我们可以改进它:

sum_leaves(Tree, Sum) :-
    sum_leaves(Tree, 0, Sum).

sum_leaves(nil, Sum, Sum).
sum_leaves(t(nil,Value,nil), Sum0, Sum) :-
    !,
    Sum is Sum0 + Value. 
sum_leaves(t(Left,_,Right), Sum0, Sum) :-
    sum_leaves(Left, LeftSum),
    Sum1 is Sum0 + LeftSum,
    sum_leaves(Right, Sum1, Sum).