在序言中计算二叉树中的零节点

Question

我编写了用于计算零值节点的谓词，但计数器 Num1 工作不正确。

countZeros(empty, Num).
countZeros(tree(0, Left, Right), Num) :- 
    Num1 = Num + 1,
    countZeros(Left, Num1),
    countZeros(Right, Num1).
countZeros(tree(_, Left, Right), Num) :-
    countZeros(Left, Num),
    countZeros(Right, Num).

这是我的查询：

countZeros(tree(5,
        tree(0,
            tree(6, empty, empty),
            tree(4, empty, empty)
        ),
        tree(0,
            tree(2, empty, empty),
            tree(0, empty, empty)
        )
        )
    , 0).

谁可以帮忙？

Answer 1

你的计数递归计算是倒退的。您从一个未实例化的计数开始，然后加 1 直到到达一个空节点并且不更改计数。所以计数永远不会初始化也不会返回。

如果您从逻辑上考虑谓词从句并描述它们的含义，这有助于正确定义它们。例如，如果当前节点为空，则零的个数为0。这将表示为：

countZeros(empty, 0).

也可以说，如果当前节点是一个0，那么零的个数就是左边分支零的个数加上右边分支零的个数分支，加上1。这可以表示为：

countZeros(tree(0, Left, Right), Num) :-
    countZeros(Left, Num1),
    countZeros(Right, Num2),
    Num is Num1 + Num2 + 1.

类似地，如果当前节点不是0，那么零的个数就是左分支零的个数加上右分支零的个数.

countZeros(tree(X, Left, Right), Num) :-
    dif(X, 0),
    countZeros(Left, Num1),
    countZeros(Right, Num2),
    Num is Num1 + Num2.

您需要将这些操作转换为 Visual Prolog。（我不知道 "terms are different" 的运算符，而我在上面使用 dif(X, 0)。我使用 is/2 而不是 =/2。）

在序言中计算二叉树中的零节点

Counting zero nodes in binary tree in prolog

tree

binary-tree

prolog