Prolog中樹遍歷

樹遍歷是指系統地訪問樹數據結構中的每個節點的過程。該postorder遍歷下面的圖片Prolog中樹遍歷

回報A, C, E, D, B, H, I, G, F (left, right, root)英寸對於PREORDER遍歷序言代碼

preorder(tree(X,L,R),Xs) :- 
    preorder(L,Ls), 
    preorder(R,Rs), 
    append([X|Ls],Rs,Xs). 

preorder(void,[]).

我想修改上面的代碼來實現後序遍歷。

來源

2012-05-08 Mark

你必須遍歷左支，並得到一個列表的節點值Left後序的情況下，然後遍歷右支，並得到一個列表的節點值Right，最後返回左，右和串聯的node value。

因此，修改代碼將重新排列你實例結果列表的方式：不過

postorder(tree(X, L, R), Xs):- 
    postorder(L, Ls), 
    postorder(R, Rs), 
    append(Ls, Rs, Xs1), 
    append(Xs1, [X], Xs). 
postorder(void, []).

注意，這段代碼是在這個意義上最理想的，它不是尾遞歸。你應該考慮在累加器的幫助下實現它。

來源

2012-05-08 19:14:49 gusbro

夥計們，請考慮描述列表時，例如使用DCG中：

preorder(void) --> []. 
preorder(tree(X, L, R)) --> 
     [X], 
     preorder(L), 
     preorder(R).

用法：

?- phrase(preorder(Tree), List).

您可以通過簡單地決定在何處放置[X]序列中獲得不同的順序。

來源

2012-05-08 19:24:03 mat

Prolog中樹遍歷

回答

相關問題