二叉樹的葉節點中的值的列表T

列表是二叉樹的葉節點中的值的列表，我試圖弄清楚如何輸出。這給了我所有的節點，但我只需要葉子。二叉樹的葉節點中的值的列表T

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]

是否有可能。

來源

2015-03-31 user1732558

讓我們使用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一個條件結構。我想把這留給有興趣的人。

來源

2015-03-31 10:28:17 false

首先，我們擴展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_(L-R = nil-nil, [X], []), 
    leaves(L), 
    leaves(R).

來源

2015-03-31 11:28:26 repeat

不確定，但我認爲（至少）在SWI-Prolog中可以直接使用（ - >）/ 2構造 – CapelliC 2015-03-31 13:05:09

否，'（ - >）/ 2'立即提交，可能會刪除部分解決方案組。 – repeat 2015-03-31 13:54:27

不應該'調用（Then_0）'讀'phrase（Then_0）'？那麼你將不再需要「添加// 1」和「空// 0」。 '（=）/ 3'比'equal_truth/3'更緊湊。 Ergo'if_（L-R = nil-nil，[X]，[]）'。 – false 2015-03-31 16:34:26

的相同的解決方案，與第一次實施不相同，可以表示爲：

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 \= []）可以刪除（如果您接受查找每個解決方案的可能性）。

來源

2015-04-24 14:42:14 Ludwig

二叉樹的葉節點中的值的列表T

回答

相關問題