Prolog 树中给定深度的节点数

Question

我是 Prolog 的新手。我正在尝试编写一个谓词，其中 returns 树中给定深度的 二叉树 的节点数。比如下面的树

有1个深度为0的节点（根节点），2个深度为1的节点，3个深度为2的节点和3个深度为3的节点。

在我的程序中，二叉树表示为 [value, left-child, right-child] 形式的列表，其中左右子节点本身可以用相同的方式表示。例如，这里是上面树的表示：

[8, [3, [1, [], []], 
        [6, [4, [], []], 
            [7, [], []]]], 
    [10, [], 
         [14, 
            [13, [], []], 
            []]]]

这是我到目前为止的想法：

nbNodes([_,_,_],1,0).
nbNodes([_,LC,RC],N2,D2) :- 
    nbNodes(LC,NL,D), nbNodes(RC,NR,D), N2 is NL+NR, D2 is D+1.

基于我对Prolog的有限理解，这意味着：

每棵树只有一个深度为0的节点。
一棵树中深度为D2的节点数为三者的左右子节点中深度为D2-1的节点数之和。

这两个假设似乎都是正确的。

但是，当我测试我的代码时，返回的数字（如果有的话）是错误的。例如，以下代码输出“false”而不是“3”：

nbNodes([8, [3, [1, [], []], [6, [4, [], []], [7, [], []]]], [10, [], [14, [13, [], []], []]]], N, 2).

我做错了什么？ 非常感谢。

Answer 1

怎么样

nbNodes( [],0,_).
nbNodes( [_,_,_],1,0).
nbNodes( [_,LC,RC],N2,D2):-
    D2 > 0,
    D is D2-1,
    nbNodes( LC,NL,D), 
    nbNodes( RC,NR,D), 
    N2 is NL+NR.

结果是：

?- T = [8,[3,[1,[],[]],[6,[4,[],[]],[7,[],[]]]],[10,[],[14,[13,[],[]],[]]]],
   nbNodes(T,N,0).
T = [8, [3, [1, [], []], [6, [4, []|...], [7|...]]], [10, [], [14, [13|...], []]]],
N = 1 ;
false.
    
?- T = [8,[3,[1,[],[]],[6,[4,[],[]],[7,[],[]]]],[10,[],[14,[13,[],[]],[]]]],
   nbNodes(T,N,1).
T = [8, [3, [1, [], []], [6, [4, []|...], [7|...]]], [10, [], [14, [13|...], []]]],
N = 2 ;
false.
    
?- T = [8,[3,[1,[],[]],[6,[4,[],[]],[7,[],[]]]],[10,[],[14,[13,[],[]],[]]]],
   nbNodes(T,N,2).
T = [8, [3, [1, [], []], [6, [4, []|...], [7|...]]], [10, [], [14, [13|...], []]]],
N = 3 ;
false.
    
?- T = [8,[3,[1,[],[]],[6,[4,[],[]],[7,[],[]]]],[10,[],[14,[13,[],[]],[]]]],
   nbNodes(T,N,3).
T = [8, [3, [1, [], []], [6, [4, []|...], [7|...]]], [10, [], [14, [13|...], []]]],
N = 3 ;
false.

?- T = [8,[3,[1,[],[]],[6,[4,[],[]],[7,[],[]]]],[10,[],[14,[13,[],[]],[]]]], 
   nbNodes(T,N,4).
T = [8, [3, [1, [], []], [6, [4, []|...], [7|...]]], [10, [], [14, [13|...], []]]],
N = 0.

两个主要变化是

我为空二叉树添加了一个子句。
我从D2计算了D，之前我又调用了谓词，不从D计算了D2 在递归调用之后。

我猜你是在问有什么区别，因为你被告知 Prolog 是声明性的，因此我们只需要指定情况（我们的知识库）而不是如何从我们的知识中推断出某些东西.

好吧，你被骗了。 Prolog 不是纯粹的声明性的，因为有一个 order，它在其中搜索答案。

如果您想通过使用子句

来证明一个目标G

G :- L1,L2,L3.

Prolog 试图证明 L1，然后是 L2，然后是 L3 - 虽然从逻辑的角度来看，这个条款只说

IF L1 and L2 and L3 THEN G,

逻辑上等同于

IF L3 and L1 and L2 THEN G

如果 Prolog 检查了所有可能的顺序，可能会有证据，但它没有。

此外，对于许多谓词，某些参数需要实例化才能使谓词起作用。其中一个谓词是 is/2。它的右侧需要完全实例化 is/2 才能工作。

您的谓词需要实例化其第三个参数。你打电话的时候 nbNodes(LC,NL,D)和nbNodes(RC,NR,D)、D没有实例化。即使您更改了子句的顺序并将 D2 is D+1 放在这些子句之前，这也不起作用，因为 is/2 需要将其右侧完全实例化，而 D 则不需要尚未实例化。

试着问 ?- X is 2。和 ?- 2 is X. 看看区别。

为了获得更全面的了解，您需要深入研究 Prolog 对 分辨率原则 的（部分）实现。如果您想拥有更具声明性的 Prolog，请查看约束逻辑编程。

Prolog 树中给定深度的节点数

Prolog number of nodes at a given depth in a tree

recursion

binary-tree

prolog