prolog - Prolog - 树中和树之间的减法

Question

这是我遇到的一个问题。如何递归地减去二叉树中的值？

subtractTree(tree(leaf(4), tree(leaf(2), leaf(1))),S).
  S = 3.

对于此示例，它首先减去每棵树中的叶子，然后再减去树之间的值。所以对于第一棵树，它的值为 4。第二棵树的值为 1，因为 2-1=1。然后它在树之间减去 4-1，答案是 3。

Answer 1

因为你的树结构有 arity 2（它必须是），你可以做一个非常简单的访问

subtractTree(leaf(N), N).
subtractTree(tree(L, R), S) :-
    subtractTree(L, X),
    subtractTree(R, Y),
    S is X - Y.

测试：

?- subtractTree(tree(leaf(4), tree(leaf(2), leaf(1))),S).
S = 3.

Answer 2

你有 4 个案例： 基本案例：一棵只有叶子的树

subtractTree(tree(leaf(A), leaf(B)),S) :-
         S is A-B.

2个中间案例，一棵树和一棵树作为叶子

subtractTree(tree(leaf(A), Tree2),S) :-
    subtractTree(Tree2, S1),
    S is A - S1.

subtractTree(tree(Tree1, leaf(B)),S) :-
    subtractTree(Tree1, S1),
    S is S1 - B.

一般情况下，一棵树的叶子是树：

subtractTree(tree(Tree1, Tree2),S) :-
    subtractTree(Tree1, S1),
    subtractTree(Tree2, S2),
    S is S1 - S2.