Prolog:对二叉树中叶子的值求和
Prolog: Sum the values of the leaves in the binary tree
我有一棵二叉树,对于这棵二叉树,我必须添加叶子中包含的值,给定一个类似的谓词:
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).
我怎样才能做到这一点?
谢谢
我是这样做的:
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).
列表不能很好地表示二叉树。让我们开始改变它:
- 空树:
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).
我有一棵二叉树,对于这棵二叉树,我必须添加叶子中包含的值,给定一个类似的谓词:
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).
我怎样才能做到这一点?
谢谢
我是这样做的:
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).
列表不能很好地表示二叉树。让我们开始改变它:
- 空树:
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).