prolog - プロローグ - ツリー内およびツリー間の減算

Question

これは私が遭遇した問題です。二分木の値を再帰的に減算するにはどうすればよいですか?

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

この例では、ツリー間の値を減算する前に、まず各ツリーの葉を減算します。したがって、最初のツリーの値は 4 です。2 番目のツリーの値は 1 です。これは、2-1=1 であるためです。次に、木の間で 4-1 を引くと、答えは 3 になります。

Answer 1

ツリー構造のアリティは 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 つの中間ケース、葉が 1 つの木と葉としての木

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.