时间戳

首页 > 解决方案 > 使用 Prolog 在线性时间内展平树

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

问题描述

我正在尝试优化 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(leaf(2), 1, leaf(3))。所以树看起来像

    1
   / \
  2   3

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

编辑：

你是这个意思吗？骨架代码：

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

    flatten_tree(Tree, FlatHead, FlatTail):-

然后从这里我一一添加到 FlatTail 因为那是累加器？

标签： optimizationprolog

解决方案

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

推荐阅读