prolog - 列表列表中的树路径

Question

我想构建一个谓词（Prolog），它接受一棵树并返回一个列表列表，每个列表都是一个树路径。树被定义为树（根，左树，右树）。请问您有什么建议吗？

Answer 1

这是非常不寻常的（例如，更常见的是询问树与其所有节点的平面列表之间的关系，DCG 非常适合），可能像这样：

tree_list(nil, []).
tree_list(tree(Node,Left,Right), [Lefts,Node,Rights]) :-
        tree_list(Left, Lefts),
        tree_list(Right, Rights).

例子：

?- tree_list(tree(a,tree(b,nil,tree(d,nil,nil)),tree(c,nil,nil)), Ts).
Ts = [[[], b, [[], d, []]], a, [[], c, []]].

这种表示是浪费的（你知道所有非空列表都会有 3 个元素，那么为什么不使用三元项而不是列表呢？）而且在我看来是不必要的（因为你首先已经有了树表示），但谁知道它有什么用...