이진 트리 inorder 탐색을 사용하여 프롤로그

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 

를 얻을 수 2 하나를 실행하려고 할 때 결과적으로

결과로 왜 그런가요?

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