在prolog中输出一个预先排序的二叉树作为列表

Question

我正在尝试创建一个列表作为prolog中二叉树的输出，这是我到目前为止的代码。

preorder(node(R, empty, empty),[R]).
preorder(node(R,Lb,Rb),[R|Ys]) :- preorder(Lb, Ys).
preorder(node(R,Lb,Rb),[R|Ys]) :-preorder(Rb, Ys).

我的想法是你遍历树并将R添加到剩下的Ys列表中。它不能像预期的那样工作

?- preorder(node(1,node(2,empty,empty),node(3,empty,empty)),Z).
Z = [1, 2] ;
Z = [1, 3] ;
false.

这是我试图运行的查询和我得到的。Prolog为我提供了所有可能的方法，但我只想要一个包含所有值的列表，所以基本上这两个列表组合在一起([1,2,3])。

Answer 1

您可以使用以下代码:

preorder(T, L) :-
preorder(T, [], L).
preorder(empty, L, L).
preorder(node(R, Lb, Rb), L0, [R|L2]) :-
preorder(Rb, L0, L1),
preorder(Lb, L1, L2).

例子:

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