时间戳

首页 > 解决方案 > Prolog 树中给定深度的节点数

recursion - Prolog 树中给定深度的节点数

问题描述

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

在此处输入图像描述

有 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 的有限理解，这意味着：

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

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

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

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

我究竟做错了什么 ？ 提前谢谢了。

标签： recursionprologbinary-tree

解决方案

怎么样

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.

两个主要变化是

  1. 我为空二叉树添加了一个子句。
  2. 我在再次调用谓词之前D从D2,计算，并且在递归调用之后不计算。D2D

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

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

如果您想G通过使用子句来证明目标

G :- L1,L2,L3.

Prolog 试图证明 L1，然后是 L2，然后是 L3——尽管从逻辑的角度来看，这个子句除了

如果 L1 和 L2 和 L3 那么 G，

这在逻辑上等价于

如果 L3 和 L1 和 L2 那么 G

如果 Prolog 检查了所有可能的订单，可能会有证据，但事实并非如此。

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

您的谓词需要实例化它的第三个参数。当您调用 nbNodes(LC,NL,D)andnbNodes(RC,NR,D)时，D不会实例化。即使您更改了子句的顺序并将其放在D2 is D+1这些子句之前，这也不起作用，因为is/2它的右侧需要完全实例化，并且D此时尚未实例化。

试问?- X is 2。和 ?-2 is X.看看有什么不同。

为了更全面地了解，您需要深入了解 Prolog 的（部分）解析原理的实现。如果您想拥有一种更具声明性的 Prolog，请查看 Constraint Logic Programming。

推荐阅读