列表列表中的树路径 [英] Tree path in a List of Lists

问题描述

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

I want to build a predicate (Prolog) that takes a tree and returns a list of lists and each list is a tree path. The tree is defined as tree(Root,LeftTree,RightTree). Do you have any suggestions, please?

推荐答案

这很不寻常(例如，更常见的是询问树与其所有节点的平面列表之间的关系，其中 DCG 是合身)，可能是这样的:

This is quite unusual (it is more common to ask for example for a relation between a tree and a flat list of all its nodes, for which DCGs are a good fit), maybe like this:

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 个元素，所以为什么不使用三元术语而不是列表?)而且在我看来是不必要的(因为你已经在第一个中使用了树表示地方)，但谁知道它有什么用...

This representation is wasteful (you know that all non-empty lists will have 3 elements, so why not use a ternary term instead of a list?) and in my opinion unnecessary (because you already have the tree representation in the first place), but who knows what it is good for...

这篇关于列表列表中的树路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！