list - Prolog二进制列表问题

Question

我正在使用 Prolog 编写二叉树程序。我遇到的具体问题是遍历。这是我所拥有的:

inOrder(bttree(_,L,_),T):-  inOrder(L,T).
inOrder(bttree(N,_,_),T) :- T1 = T, append(T1,N,T).
inOrder(bttree(_,_,R),T):-  inOrder(R,T).

我一直在查询它:

inOrder(bttree(20,
    bttree(10, bttree(5, nil, nil), bttree(15, nil, nil)) bttree(30)), T).

所以输出应该是:

[5,10,15,20,30];
false.

但是当我运行它时，它只返回 false。我相当确定问题出在我对 append/3 的使用上，但我就是无法解决。如果有人可以提供帮助，我们将不胜感激

Answer 1

我得到了一个查询的无限循环(请注意原始查询中缺少的逗号):

?- inOrder(bttree(20,
      bttree(10, bttree(5, nil, nil), bttree(15, nil, nil)), bttree(30)), T).
   loops.

我得到了相同的无限循环，即使在将目标 false 添加到您的程序之后也是如此。生成的程序称为 failure-slice :

inOrder(bttree(_,L,_),T):- false, inOrder(L,T).inOrder(bttree(N,_,_),T) :- T1 = T, append(T1,N,T), false.inOrder(bttree(_,_,R),T):-  false, inOrder(R,T).

So this remaining clause alone causes this loop. In fact, any query with a node bttree/3 will now loop, even

 ?- inOrder(bttree(20, nil,nil), T).
    loops.

所以我们至少需要修复剩下的可见部分。

并不是说条款是相互独立阅读的，所以你的第一个条款是:

inOrder(bttree(_,L,_),T):- inOrder(L,T).

因此节点的中序遍历将只是左子树的中序遍历。这似乎不对。

您真正想要的是一起描述它们。最好的方法不是使用 append/3 而是使用 dcg :

inorder(nil) --> [].
inorder(bttree(N,L,R)) -->
   inorder(L),
   [N],
   inorder(R).

现在我们得到:

?- phrase(inorder(bttree(20,
      bttree(10, bttree(5, nil, nil), bttree(15, nil, nil)), bttree(30))), T).
   false.

又是假的!但这次应该替换的是 bttree(30):

?- phrase(inorder(bttree(20,
      bttree(10, bttree(5, nil, nil), bttree(15, nil, nil)), bttree(30,nil,nil))), T).
   T = [5,10,15,20,30].