在 prolog 中按顺序输出二叉树作为列表

Question

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

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 给了我所有可能的方法到叶子，但我只想要一个包含所有值的列表，所以基本上 2 个列表组合（[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].

在 prolog 中按顺序输出二叉树作为列表

output a binary tree in preorder as a list in prolog

binary-tree

prolog