使用Prolog在线性时间内将树展平

Question

我正在尝试优化Prolog中的树数据结构的扁平化。我能够实现一个简单的解决方案来按顺序遍历列表，如下所示：

naive_flatten_tree(leaf(X), [X]).
naive_flatten_tree(tree(Left, Val, Right), Flattened_Tree) :-
    naive_flatten_tree(Left, LFlat), 
    naive_flatten_tree(Right, RFlat),
    append(LFlat, [Val|RFlat], Flattened_Tree). 

简单明了。如果是叶子，则返回它，如果不是，则在左子树和右子树上递归。将左边、右边和根值追加在一起，你就得到了扁平化的树。还值得注意的是，树叶在树的定义中是明确规定的。一个示例树是tree (叶子(2)，1，叶子(3))。所以这棵树看起来像

    1
   / \
  2   3

我需要优化这运行在线性时间到树的大小。描述说这可以使用一个累加器和一个辅助过程来完成，在这个过程中，你可以传入一个空的累加器。还声明以相反的顺序构建树的展平，然后在辅助过程完成后反转列表。

编辑：

这就是你的意思吗？框架代码：

flatten_tree(tree(Left, Val, Right), Final):-
    flatten_tree(Tree, Flat, []).

    flatten_tree(Tree, FlatHead, FlatTail):-

然后从这里开始，我一个接一个地添加到FlatTail，因为它是累加器？

Answer 1

优化的解决方案是：

%      1
%     / \
%    2   3
%   / \   \
%  4   5   6

example(tree(tree(leaf(4),2,leaf(5)),1,tree(nil,3,leaf(6)))).

flatten_tree(Tree, InOrder) :-
    flatten_tree(Tree, [], InOrder).

flatten_tree(nil, Suffix, Suffix).
flatten_tree(leaf(Val), Suffix, [Val|Suffix]).
flatten_tree(tree(Left, Val, Right), Suffix, InOrder) :-
    flatten_tree(Right, Suffix, NewSuffix),
    flatten_tree(Left, [Val|NewSuffix], InOrder).

示例：

?- example(A), flatten_tree(A, L).
A = tree(tree(leaf(4), 2, leaf(5)), 1, tree(nil, 3, leaf(6))),
L = [4, 2, 5, 1, 3, 6].

?- flatten_tree(nil, L).
L = [].

?- flatten_tree(leaf(1), L).
L = [1].

?- flatten_tree(tree(leaf(1),2,leaf(3)), L).
L = [1, 2, 3].

?- flatten_tree(tree(leaf(1),2,nil), L).
L = [1, 2].

?- flatten_tree(tree(nil,2,leaf(3)), L).
L = [2, 3].

Answer 2

根据GuyCoder的建议，遵循DCG解决方案：

%      1
%     / \
%    2   3
%   / \   \
%  4   5   6

example(tree(tree(leaf(4),2,leaf(5)),1,tree(nil,3,leaf(6)))).

% inorder(+Tree, -List)

inorder(Tree, List) :-  phrase(ft(Tree), List, []).

ft(nil) --> [].
ft(leaf(V)) --> [V].
ft(tree(L,V,R)) --> ft(L), [V], ft(R).

示例：

?- example(T), inorder(T, L).
T = tree(tree(leaf(4), 2, leaf(5)), 1, tree(nil, 3, leaf(6))),
L = [4, 2, 5, 1, 3, 6].

?- inorder(nil, L).
L = [].

?- inorder(leaf(1), L).
L = [1].

?- inorder(tree(leaf(1),2,leaf(3)), L).
L = [1, 2, 3].

?- inorder(tree(leaf(1),2,nil), L).
L = [1, 2].

?- inorder(tree(nil,2,leaf(3)), L).
L = [2, 3].