1

我一直在尝试解决我的这个问题一段时间，但我不确定如何去做。

例如，假设我的数据库中有这个“树”：

tree4(b(b(l(Apple),l(Banana)), b(l(Orange), l(Pear)))).

我希望能够查询数据库，以便检索每个 l() 中的信息并将其呈现在列表中。到目前为止，我已经这样做了：

leaves(l(X), L) :-
    L = X.
leaves(b(X,Y), L) :-
    leaves(X, A),
    leaves(Y, B),
    L = [A, B].

然后我查询数据库，它给了我这个：

?- tree4(T), leaves(T, L).
T = b(b(l(1), l(2)), b(l(3), l(4))),
L = [[1, 2], [3, 4]].

这段代码的问题是它会生成多个列表，这些列表位于我原来的列表中。还有其他方法可以解决这个问题吗？任何帮助将不胜感激！

4

4 回答 4

2

当您描述一个列表（在这种情况下：叶子）时，请考虑使用 DCG：

leaves(l(L))     --> [L].
leaves(b(B1,B2)) --> leaves(B1), leaves(B2).

示例查询（使用原子而不是变量tree4/1）：

?- tree4(Tree), phrase(leaves(Tree), Leaves).
Tree = b(b(l(apple), l(banana)), b(l(orange), l(pear))),
Leaves = [apple, banana, orange, pear].
于 2013-09-08T01:10:40.737 回答
1

append/3您可以通过在树的遍历期间使用累加器收集叶子来避免谓词的成本：

leaves(Tree, Leaves) :-
    leaves(Tree, [], Leaves).

leaves(l(Leaf), Leaves, [Leaf| Leaves]).
leaves(b(Left,Right), Leaves0, Leaves) :-
    leaves(Right, Leaves0, Leaves1),
    leaves(Left, Leaves1, Leaves).

使用您的示例调用：

?- leaves(b(b(l(1), l(2)), b(l(3), l(4))), Leaves).
Leaves = [1, 2, 3, 4].
于 2013-09-07T22:59:37.120 回答
0

假设你的 Prolog 实现有一个append谓词，你可以这样做：

leaves(l(X), [X]).

leaves(b(X,Y), L) :-
    leaves(X, A),
    leaves(Y, B),
    append(A, B, L).

所以leaves总是会返回一个平面列表，即使只有一个。这也假设您的树是严格的二元树，正如您所描述的那样。

于 2013-09-07T21:55:57.963 回答
0

只是提醒一下flatten /2，一个方便的内置函数：

?- leaves(b(b(l(1), l(2)), b(l(3), l(4))), L), flatten(L, F).
L = [[1, 2], [3, 4]],
F = [1, 2, 3, 4].

正如您从文档中看到的那样，不鼓励使用它，并且您已经收到了很多可以避免使用它的好提示。

于 2013-09-08T07:05:34.067 回答