返回二叉樹的各級序言

我試圖讓一個程序來返回一個列表的方式BT的水平，我被堵在此：返回二叉樹的各級序言

nivel(nodo(L,Root,R)) :- nivel(nodo(L,Root,R),X),writeln(X). 
nivel(vacio,[]). 
nivel(nodo(L,Root,R),[Root|T]) :- nivel(L,T),nivel(R,T),writeln(T).

一例輸入輸出我想要的是：

nivel(nodo(nodo(vacio,4,vacio), t, nodo(vacio,r,vacio)) 
    X =[t] 
    X =[4,r]

問題是我不知道如何使程序得到新的根。任何想法？另外，在此先感謝！

來源

2011-03-31 Kirby

這裏有一個解決方案，一旦構建了每個級別的項目列表，就會遍歷樹。

nivel(Arbol, SubNivel):- 
    nivel(Arbol, [], [], Items), 
    member(SubNivel, Items), 
    SubNivel \= []. 

nivel(vacio, Items, SubNiveles, [Items|SubNiveles]). 
nivel(nodo(Izq, Item, Der), Items, [], [[Item|Items]|NSubNiveles]):- 
    nivel(Izq, [], [], [MSubItems|MSubNiveles]), 
    nivel(Der, MSubItems, MSubNiveles, NSubNiveles). 
nivel(nodo(Izq, Item, Der), Items, [SubItems|SubNiveles], [[Item|Items]|NSubNiveles]):- 
    nivel(Izq, SubItems, SubNiveles, [MSubItems|MSubNiveles]), 
    nivel(Der, MSubItems, MSubNiveles, NSubNiveles).

nivel/4的第二個子句是由於算法事先不知道樹的高度這一事實而引發的。

測試用例：

?- nivel(nodo(nodo(nodo(nodo(vacio,f,vacio),e,nodo(vacio,g,vacio)),b,vacio),a,nodo(vacio,c,nodo(vacio,d,vacio))), X). 
X = [a] ;  --> Root 
X = [c, b] ; --> First Level 
X = [d, e] ; --> Second Level 
X = [g, f] ; --> Third Level

來源

2011-03-31 16:32:47 gusbro

相當棘手的一個序言，但這裏有一個解決方案來考慮它提供了一個真正的level-order (L-R breadth-first)樹遍歷：

nivel(nodo(L,Root,R), Level) :- 
    depth_value_pairs(nodo(L,Root,R), 0, DVPairs), 
    keylistmerge(DVPairs, Groups), 
    maplist(keyvalue, Groups, _, Values), 
    member(Level, Values).

nivel/2是您的輸入謂詞。基本上，其使用depth_value_pairs/3，其產生Depth-Value形式的解（例如，0-t以表示層深度的根節點t或1-4以表示在層深度1等處的節點4）。然後，它使用keylistmerge/2將所有深度值對列表合併成深度組，例如[0-[t], 1-[4,t], ...]。然後，maplist(keyvalue...調用從列表中刪除Depth-部分，並且最終謂詞調用member/2選擇每個列表以綁定到輸出Level。

下面是其他謂詞的定義：

depth_value_pairs(vacio, _, []). 
depth_value_pairs(nodo(L, Root, R), Depth, [Depth-Root|Level]) :- 
    NextLevel is Depth + 1, 
    depth_value_pairs(L, NextLevel, LL), 
    depth_value_pairs(R, NextLevel, RL), 
    append(LL, RL, Level). 

keyvalue(K-V, K, V). 

keylistmerge(KVL, MKVL) :- 
    keysort(KVL, [K-V|KVs]), 
    keylistmerge([K-V|KVs], K, [], MKVL). 
keylistmerge([], K, Acc, [K-Acc]). 
keylistmerge([K0-V|KVs], K, Acc, MKVL) :- 
    K == K0, !, 
    append(Acc, [V], NewAcc), 
    keylistmerge(KVs, K, NewAcc, MKVL). 
keylistmerge([K0-V|KVs], K, Acc, [K-Acc|MKVs]) :- 
    keylistmerge(KVs, K0, [V], MKVs).

行使這給了我們：

?- nivel(nodo(nodo(vacio,4,nodo(vacio,5,vacio)), t, nodo(vacio,r,vacio)), Level). 
Level = [t] ; 
Level = [4, r] ; 
Level = [5] ; 
false.

請注意，我們依靠內置keysort/2是保序（穩定）以保留二叉樹中節點的LR順序。

來源

2011-03-31 06:57:39 sharky

返回二叉樹的各級序言

回答

相關問題