二叉树T的叶节点中的值的列表

List是二叉树的叶节点值的列表，我想弄清楚如何输出。 这是给我所有的节点，但我只需要叶子。

lea(nil,[]). lea(t(X,L,R),[X|L]) :- lea(L,L1), lea(R,L2), append(L1,L2,L). 

运行这个给我：

 ?- lea(t(a,t(b,t(d,nil,nil),t(e,nil,nil)),t(c,nil,t(f,t(g,nil,nil),nil))), List). List = [a, b, d, e, c, f, g] 

但是我需要

 List = [d, e,g] 

可能吗。

Answer 1

让我们使用一个DCG – 一个确定的句子语法。 我们从您的原始定义开始：

 lea(T, L) :- phrase(values(T), L). values(nil) --> []. values(t(X,L,R)) --> [X], values(L), values(R). 

现在，我们需要把自己限制在那些叶子的t/3上。 一种可能性是列举所有情况：

 lea2(T, L) :- phrase(leaves(T), L). leaves(nil) --> []. leaves(t(X,nil,nil)) --> [X]. leaves(t(_,L,R)) --> { dif(L+R,nil+nil) }, leaves(L), leaves(R). 

使用类似于if_/3的条件构造会更好，更高效。 我想把这个留给有兴趣的人。

Answer 2

首先，我们扩展if_/3与DCG的工作：

 if_(C_1, Then_0, Else_0) --> % if_//3 { call(C_1, Truth) }, { functor(Truth, _, 0) }, % safety check ( { Truth == true } -> phrase(Then_0) ; { Truth == false }, phrase(Else_0) ). 

使用if_//3和(=)/3我们可以用一个子句（而不是两个）处理非零树节点：

 lea3(T, Ls) :- phrase(leaves(T), Ls). leaves(nil) --> []. leaves(t(X,L,R)) --> if_(LR = nil-nil, [X], []), leaves(L), leaves(R). 

Answer 3

与第一次实施相差甚远的解决scheme可以表示为：

 lea(nil, []). lea(t(X, nil, nil), [X]). lea(t(_, A, B), L) :- lea(A, L1), lea(B, L2), append(L1, L2, L) L \= []. 

最后一行（ L \= [] ）可以被删除（如果你接受find每个解决scheme的可能性）。