序言，二叉樹

我想找到二叉樹的最深元素，到目前爲止，代碼只適用於空樹或高度爲一。序言，二叉樹

這裏是代碼我的身高功能正常工作。

deepest(node(L,X,R),X):- height(L,0),height(R,0). 
deepest(node(L,_,R),X):- height(L,D1),height(R,D2), D1 > D2, deepest(L,X). 
deepest(node(L,_,R),X):- height(L,D1),height(R,D2), D1 =< D2, deepest(R,X).

編輯：例如

?- deepest(node(node(node(leaf,8,leaf),20,leaf), 
         30, 
         node(node(leaf,88,leaf),33,node(leaf,888,leaf))), 
       X). 
X = 8 ; 
X = 88 ; 
X = 888 ; 
false.

來源

2012-10-12 John

你可以給一個查詢的例子嗎？ – NotAUser

已更新。謝謝 – John

我看起來很好，至少得到第一個結果。回溯可能有問題。如果將第一條規則更改爲「最深（節點（葉，X，葉），X）」，會發生什麼情況？ – NotAUser

我懷疑的關係height（順便說一句有在序言不功能），將是無用的任務，因爲它忘記了所需的基本信息。

deepest(T, E) :- 
    deepest(T, E, _). 

deepest(node(L, X, R), E, D) :- 
    deepest(L, EL, DL), 
    deepest(R, ER, DR), 
    ( DL > DR 
    -> E = EL, D is DL + 1 
    ; ( DL < DR 
     -> E = ER, D is DR + 1 
     ; ( DL > 0 % DL & DR are equals 
      -> E = L, D is DL % deepest is arbitrary here 
      ; E = X, D is 1 
      ) 
     ) 
    ). 
deepest(N, N, 0).

編輯爲預期的數據結構，而不是deepest(N, N, 0).我認爲這是更清晰的使用

deepest(_, _, 0).

來源

2012-10-12 06:33:51 CapelliC

下面是可替代的形式，這使得使用一些基本的內置插件，即append/3，keysort/2的， reverse/2和maplist/3：

deepest(Tree, N) :- 
    deepest(Tree, 0, NL), 
    maplist(strip_key, NL, N). 

deepest(leaf, _, []). 
deepest(node(L, X, R), D, [DN-N|Res]) :- 
    NewD is D + 1, 
    deepest(L, NewD, LL), 
    deepest(R, NewD, RL), 
    append([D-X|LL], RL, NL), 
    keysort(NL, KL), 
    reverse(KL, [DN-N|Rem]), 
    first_key_run(Rem, DN, Res). 

first_key_run([DN-N|Rem], DN, [DN-N|NL]) :- 
    !, 
    first_key_run(Rem, DN, NL). 
first_key_run(_, _, []). 

strip_key(_K-V, V).

此版本在樹中的每個節點上建立一個Depth-Node項目的列表，執行keysort/2至列表中，該列表將其排序爲最淺優先（O（N·log（N）），顛倒順序（O（N）），然後保持第一次運行的最深的節點（O（N））。

這個版本也計算確切的深度最深的節點數量。例如：

?- deepest(node(node(node(leaf,8,leaf),20,leaf),30,node(node(leaf,88,leaf),33,node(leaf,888,leaf))), X). 
X = [88, 888, 8].

來源

2012-10-14 06:08:38 sharky

序言，二叉樹

回答

相關問題