使用Prolog的二叉樹序列遍歷

Question

我想實現一個inorder遍歷，在每個階段我會得到當前節點。 例如：

?- getnodesinorder(tree(1,nil,nil),X). 
X = 1 ; 
false. 

?- getnodesinorder(tree(5,tree(4,tree(1,nil,tree(3,tree(2,nil,nil),nil)),nil),tree(6,nil,nil)),X). 
X = 1 ; 
X = 2 ; 
X = 3 ; 
X = 4 ; 
X = 5 ; 
X = 6 ; 
false. 

我已經嘗試了下面的代碼：

getnodesinorder(tree(CurrentNode,nil,nil), CurrentNode). 
getnodesinorder(tree(X, Left, nil), CurrentNode) :- 
    getnodesinorder(Left, _), 
    CurrentNode is X. 
getnodesinorder(tree(X, nil, Right), CurrentNode) :- 
    CurrentNode is X, 
    getnodesinorder(Right, _). 
getnodesinorder(tree(X, Left, Right), CurrentNode) :- 
    getnodesinorder(Left, _), 
    CurrentNode is X, 
    getnodesinorder(Right, _). 

所以當然底座（例如1號作品），但試圖運行：第二個我得到

X=5; 
false 

時

作爲結果。這是爲什麼？

Answer 1

，因爲你正在處理的左，右子樹，但他們沒有做與值有任何出現的錯誤：getnodesinorder(Left, _)只是拋出他們離開。所以，你的謂詞只返回最上面的元素。

這裏是你如何做一箇中序遍歷：

inorder(tree(_,L,_), X) :- inorder(L,X). 
inorder(tree(X,_,_), X). 
inorder(tree(_,_,R), X) :- inorder(R,X). 

例子查詢：

?- inorder(tree(5,tree(4,tree(1,nil,tree(3,tree(2,nil,nil),nil)),nil),tree(6,nil,nil)),X). 
X = 1 ; 
X = 2 ; 
X = 3 ; 
X = 4 ; 
X = 5 ; 
X = 6 ; 
false. 

Answer 2

[test] λ = cat test.pl 
append([], Ys, Ys). 
append([X|Xs], Ys, [X|Zs]) :- append(Xs, Ys, Zs). 

getnodesinorder(nil, []). 

getnodesinorder(tree(X, Left, Right), R) :- 
    getnodesinorder(Left,R1), 
    getnodesinorder(Right,R2), 
    append(R1,[X|R2],R). 

對我的作品

?-getnodesinorder(tree(5,tree(4,tree(1,nil,tree(3,tree(2,nil,nil),nil)),nil),tree(6,nil,nil)),X). 
X = [1,2,3,4,5,6] ? 
yes