Prolog计算二叉树中的所有叶节点

Question

我需要使用 prolog 计算二叉树的所有内部节点我可以使用以下代码计算所有节点

internal(tree(_,L,R), I) :- internal(L, I2), internal(R, I3), I is I2 + I3 + 1.
internal(nil, 0).

而且我认为通过将基本案例更改为

internal(tree(_,nil, nil), 0).

我可以让它工作，但它 return 是错误的。

这里是一个测试用例，应该 return 4 internal(tree(8,tree(5,tree(2,nil,nil),tree(7,nil,nil)), tree(9 ,nil,tree(15,tree(11,nil,nil),nil))),I).

谁能告诉我我的错误在哪里？谢谢

在阅读了您的建议后，我得到了这个，但仍然失败。

internal(tree(_,L,R), I) :- internal(L, I2), internal(R, I3), I is I2 + I3. 
internal(tree(_,nil, R), I):- !, internal(R, I3), I is I3 + 1. 
internal(tree(_,L, nil), I):- !, internal(L, I3), I is I3 + 1.
internal(tree(_,nil, nil), 0).
internal(nil, 0).

Answer 1

如果将谓词更改为：

internal(tree(_,nil, nil), 0).
internal(tree(_,L,R), I) :- internal(L, I2), internal(R, I3), I is I2 + I3 + 1.

那么对于具有 nil child 和非 nil child 的树，这将失败。

确实：如果树是 tree(1, nil, tree(2, nil, nil))，那么 Prolog 将首先尝试满足基本情况，但是正弦 nil 不等于 tree(_, nil, nil)，那将失败。接下来针对满足递归的情况，先统一L = nil，R = tree(2, nil, nil)。现在它调用 internal(L, I2)，但由于无法满足 internal(nil, I1)，它失败了。

因此，我们可以首先构造一个谓词，如果两个子树导致一个内部节点：

isinternal(tree(_, _, _), _).
isinternal(_, tree(_, _, _)).

因此，如果至少有一个子树是 tree(_, _, _).，则此谓词成功。现在我们可以使用这个谓词来计算内部节点的数量：

internal(nil, 0).
internal(tree(_, nil, nil), 0).
internal(tree(_, L, R), I) :-
    isinternal(L, R),
    internal(L, NL),
    internal(R, NR),
    I is NL + NR + 1.

以上在可读性方面可以提高。我把它留作练习。

Prolog计算二叉树中的所有叶节点

Prolog to count all the leaf nodes in a binary tree

binary-tree

prolog