1

对于树的 PreOrder 遍历，我有这个 Prolog 谓词：

preOrder(nil, []).
preOrder(node(X, nil, nil), [X]).
preOrder(node(X, L, _), [X|T]) :- preOrder(L, T).
preOrder(node(X, _, R), [X|T]) :- preOrder(R, T).

问题是，它返回一个不完整的列表。例如，我得到：

?- preOrder(node(1, node(2, node(3,nil,nil), node(4,nil,nil)), node(5,nil,nil)), L). 
L = [1,2,3]

什么时候应该L=[1,2,3,4,5]。

为什么会短暂停顿？

4

2 回答 2

1

看看 Prolog 产生的答案。这不是一个：

| ?- preOrder(node(1,node(2,node(3,nil,nil),node(4,nil,nil)),node(5,nil,nil)),L).
L = [1,2,3] ? ;
L = [1,2,3] ? ;
L = [1,2,3] ? ;
L = [1,2,4] ? ;
L = [1,2,4] ? ;
L = [1,2,4] ? ;
L = [1,5] ? ;
L = [1,5] ? ;
L = [1,5] ? ;
no

您的每条规则都独立于其他规则描述了某些部分。但是你需要一起描述它们。

解决这个问题的最好方法是使用 DCG

于 2014-11-26T15:12:00.953 回答
-1

它停止了，因为您有两个递归子句，每个子句都只到树的一侧。尽管不需要第二个，但您也有两个基本案例。

因此，您将删除第二个子句并将两个递归子句连接到一个子句中，该子句附加两个分支的结果。

例如：

preOrder(nil, []).
preOrder(node(X, L, R), [X|T]) :- 
  preOrder(L, LT), 
  append(LT, RT, T), 
  preOrder(R, RT).

您还可以使用累加器进行遍历：

preOrder(Tree, List):-
  preOrder(Tree, [], RList),
  reverse(RList, List).

preOrder(nil, List, List).
preOrder(node(X, L, R), List, NList) :- 
    preOrder(L, [X|List], MList), 
    preOrder(R, MList, NList).

请注意，正如一位评论者所说，preOrder 的这些定义在给定遍历的情况下无法正确生成树。

您可能希望使用 DCG 来定义一个可逆的过程，在内部使用开放列表：

preOrder(nil)-->[].
preOrder(node(X, L, R))-->[X], preOrder(L), preOrder(R).

你会用它来调用它phrase/2：

?- phrase(preOrder(node(1, node(2, node(3,nil,nil), node(4,nil,nil)), node(5,nil,nil))), L).
L = [1, 2, 3, 4, 5].
于 2014-11-26T15:13:33.940 回答