用Prolog实现PreOrder树的遍历

Question

我有这个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]时。

为什么它突然停了下来？

Answer 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

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

解决这个问题的最好方法是to use DCGs

Answer 2

它突然停止了，因为您有两个递归子句，每个子句都只到树的一侧。您还有两个基本用例，尽管第二个用例不是必需的。

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

例如：

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的这些定义不适合在给定遍历的情况下生成树。

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

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].