2

我有一些代码

tree1(tree(1,
            tree(2,
                tree(3,nil,nil),
                tree(4,nil,nil)),
            tree(5,
                tree(6,nil,nil),
                tree(7,nil,nil))
        )
    ).
rbt_count_nodes(e,0):-!.
rbt_count_nodes(t(_,L,R),N):-
    rbt_count_nodes(L,NL),
    rbt_count_nodes(R,NR),
    N=NL+NR+1.

?-tree1(T),rbt_count_nodes(T,N),write(N).

但是目标总是返回No。为什么？

4

2 回答 2

5 
rbt_count_nodes(t(_,L,R),N)

应该成为

rbt_count_nodes(tree(_,L,R),N)

和

N=NL+NR+1

应该成为

N is NL + NR + 1

（(=)/2用于执行统一，(is)/2执行算术）。

和

rbt_count_nodes(e,0):-!.

应该成为

rbt_count_nodes(nil,0).

在这三个编辑之后应该没问题，虽然我无法测试所以我可能被证明是错误的。

于 2012-05-24T12:18:35.543 回答
4

除了另一个答案中给出的注释（使用is/2而不是=/2和术语 t->tree 和 e->empty 名称中的拼写错误）之外，您应该考虑使用累加器来允许 prolog 系统进行尾递归：

rbt_count_nodes(T,N):-
  rbt_count_nodes(T, 0, N).

rbt_count_nodes(nil,N, N):-!.
rbt_count_nodes(tree(_,L,R),C,N):-
    succ(C, C1),
    rbt_count_nodes(L,C1,NL),
    rbt_count_nodes(R,NL,N).

过程rbt_count_nodes/2只是rbt_count_nodes/3以零作为第二个参数（累加器）调用。在每个递归步骤中，该累加器都会递增 1 并进行递归。基本情况只是将累加器与您的输出统一起来，允许系统进行尾递归并节省堆栈空间。

[编辑]

根据评论，要使其真正成为尾递归（即所有递归调用都是尾调用），您可以向 rbt_count_nodes/3 添加一个新子句（并修改另一个子句）：

rbt_count_nodes(nil,N, N):-!.
rbt_count_nodes(tree(Node,tree(LNode, LL, LR),R),C,N):-
  rbt_count_nodes(tree(Node, LL, tree(LNode, LR, R)), C, N).
rbt_count_nodes(tree(_,nil,R),C,N):-
  succ(C, C1),
  rbt_count_nodes(R,C1, N).

使用这种方法，第一个子句处理一个空节点，第二个子句处理树的左侧，它只是将分支“移动”到当前节点的右侧，第三个子句只计算节点。

于 2012-05-24T14:49:37.217 回答