如何将 1-2-3 树展平为列表？

Question

我正在研究将树转换为整数列表的函数。我的问题是，当我只需要添加一个或两个整数时，我可以追加到列表中。但是我似乎无法在没有得到这个的情况下附加三个整数：

[[2], 3, 4]，当我应该得到 [2, 3, 4].

我知道这个问题源于这个声明

append([Temp1 | Temp2] , Temp3, L)

其中 Temp1、Temp2 和 Temp3 是我要添加的整数。 L 是包含到目前为止树中所有整数的主列表。

我尝试使用两个追加语句，但是 returns 一个 false 布尔值而不是 [2, 3, 4]。我试着在 [ | ] 周围移动，但我认为我对它们的了解还不足以产生影响。

append/3 页面也只能将两个列表连接成一个。任何帮助将不胜感激:)

编辑：我的代码如下，我添加了我的测试示例。

chopTree(leaf(_), []).
chopTree(node1(Leaf, Node), L) :- 
    chopTree(Node, Temp), 
    append([], [Leaf | Temp], L).
chopTree(node2(Leaf, Node1, Node2), L) :- 
    chopTree(Node1, Temp1), 
    chopTree(Node2, Temp2), 
    append(Temp1, [Leaf | Temp2], L).
chopTree(node3(_, Node1, Node2, Node3), L) :- 
    chopTree(Node1, Temp1), 
    chopTree(Node2, Temp2), 
    chopTree(Node3, Temp3), 
    append([Temp1 | Temp2] , Temp3, L).

query(E) :- 
    chopTree(node3(1, 
                   node1(2, leaf(1)), 
                   node2(3, leaf(1), leaf(1)), 
                   node1(4, leaf(1))), 
             E).

Answer 1

您的命名已关闭。变量看起来更好称为 "Label"。那么，node3大概应该有两个：

chopTree(leaf(_), []).
chopTree(node1(Label, Node), L) :- 
    chopTree(Node, Temp), 
    % append([], [Label | Temp], L).
    L = [Label | Temp].
chopTree(node2(Label, Node1, Node2), L) :- 
    chopTree(Node1, Temp1), 
    chopTree(Node2, Temp2), 
    append(Temp1, [Label | Temp2], L).
chopTree(node3(Label1, Label2, Node1, Node2, Node3), L) :- 
    chopTree(Node1, Temp1), 
    chopTree(Node2, Temp2), 
    chopTree(Node3, Temp3), 
    append(Temp1, [Label1 | Temp2] , L1),
    append(L1, [Label2 | Temp3], L).

也许node1里面也不应该有任何标签。无论如何，如您所见，我们只需调用 append 两次，或者我们需要调用多少次，来逐个构建结果列表。

Answer 2

将树与列表相关联时，检查 DCG 表示法：DCG 让您完全避免 append/3，使您的代码更简单并同时经常提高其终止性能。

例如：

tree_list(leaf(Leaf)) --> [Leaf].
tree_list(node1(Leaf, Node)) -->
        [Leaf],
        tree_list(Node).
tree_list(node2(Leaf, Node1, Node2)) -->
        tree_list(Node1),
        [Leaf],
        tree_list(Node2).
tree_list(node3(_, Node1, Node2, Node3)) -->
        tree_list(Node1),
        tree_list(Node2),
        tree_list(Node3).

示例查询和回答：

?- phrase(tree_list(node3(1,
                     node1(2, leaf(1)),
                     node2(3, leaf(1), leaf(1)),
                     node1(4, leaf(1)))), Ls).
Ls = [2, 1, 1, 3, 1, 4, 1].

您只需在 DCG 体内移动终结符和非终结符，即可轻松将其调整为其他所需顺序。

请注意，所有的辅助变量都完全消失了！

如何将 1-2-3 树展平为列表？

How to flatten a 1-2-3 tree into a list?

tree

recursion

list

prolog

flatten