3

我正在使用 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 的使用上，但我根本无法解决。如果有人可以提供帮助，将不胜感激

4

3 回答 3

2

我得到了查询的无限循环（请注意原始查询中缺少的逗号）：

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

即使在false您的程序中添加了目标，我也会得到相同的无限循环。生成的程序称为：

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)。

所以这个剩余的子句单独导致了这个循环。事实上，任何带有节点的查询bttree/3现在都会循环，甚至

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

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

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

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

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

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

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].
于 2014-08-16T23:07:07.630 回答
0

以防万一你不想要一个dcg：

inOrder( nil, [] ).
inOrder( btree( L, N, R ), T ) :- 
    inOrder( L, TL ),
    inOrder( N, TN ),
    inOrder( R, TR ),
    append( TL, TN, TLN ),
    append( TLN, TR, T ).
于 2014-08-16T23:47:20.223 回答
0

这T1 = T, append(T1,N,T)相当于append(T,N,T)并且注定要循环......

一些更正...

inOrder(nil, []).
inOrder(bttree(N, L, R),T) :-
  inOrder(L, LT),
  inOrder(R, RT),
  append(LT, [N|RT], T).

测试：

?- inOrder(bttree(20, bttree(10, bttree(5,nil,nil), bttree(15,nil,nil)), bttree(30,nil,nil)), T).
T = [5, 10, 15, 20, 30].
于 2014-08-17T00:19:04.723 回答