트리에서 요소의 inorder 위치를 찾고있는 프롤로그 (목록을 사용하지 않고)

Question

inorder 여행 방법에서 이진 트리를 통과하려고합니다. 내 목표는 트리에서 특정 키의 출현을 찾는 것입니다. for 난 내 inorder_finder를 사용할 때

t(t(t(nil,"d",t(nil,"g",nil)),"b",t(nil,"e",nil)),"a",t(t(nil,"f",t(nil,"h",nil)),"c",nil)) 

난 다음 얻을 것이다 : 예, 난 다음 나무가 "C"에 대한 을 내가 "w에 대한"D "내가 얻을 것이다 1 을 얻을 것이다 "얻을 것이다 -1

나는 가지고있다 com

inorder_finder(nil,_,_,0). 

inorder_place(t(_,X,_),X,Count,Place) :- 
    Place is Count+1. 

inorder_place(t(L,_,R),Wanted,Count,Place) :- 
     inorder_place(L,Wanted,Count+1,Place), 
     Place<1, 
     inorder_place(R,Wanted,Count+1,Place), 
     Place<1, 
     Count = Count+1. 

그리고 난 다음 술어를 호출 : 전자까지 다음 코드

inorder_finder inorder_place(t(t(t(nil,"d",t(nil,"g",nil)),"b",t(nil,"e",nil)),"a",t(t(nil,"f",t(nil,"h",nil)),"c",nil)),"c",1,Place) 

하지만 순간에 일을 나던. (그냥 항상 false를 반환) 어떤 아이디어?

업데이트 : 내가받은 의견에 따라 코드를 업데이트 한 - 아직 내가 남아 어떤 의견에 언급 된

Answer 1

대부분의 명백한 오류에 좋아하는 것처럼 허위 나던 작업을 반환은 다음과 같습니다

1. Place<1 : 이유가 무엇입니까 ?? ...
2. inorder_place(t(_,X,_),X,Count,Place):-Place is Count+1. 정의 결코 : 장소 1.
3. inorder_place보다 큰 값을 가지고 있습니다 당신은 당신이 먼저 재귀 (아래 답변을 참조) 왼쪽 트리의 분기 및 원하는 편지의 다음 장소를 열거 할 필요가 편지를 찾을 경우에도
4. 문제가 두 부분으로 해결 될 수 있다고 생각합니다. 올바른 노드를 찾을 때까지 모든 노드를 열거 한 다음 트래버스합니다. 비록 내가이 버전을 따르지는 않았지만 (단순한 혼합 솔루션으로 모든 노드를 열거 할 필요가 없기 때문에 더 명확하다). 나는 두 개의 카운터가 필요하다고 생각한다.- 처음으로을 호출 할 때 inorder_find (..)를 호출 할 때 카운터가 입력된다. 두 번째 카운터은 계속하기 위해 카운팅이 멈춘 곳으로 돌아 간다. 거기에서 나무의 오른쪽 가지에.
5. inorder_finder inorder_place(...) : 그것은 거짓없는 오류를 반환해야 predicate-를 호출 여전히 유효하지 않은 구문 ...

내 구현 :

inorder_finder(nil,_,Count,Count,-1). 

inorder_finder(t(L,X,_),X,Count,Count2,Place):- 
       inorder_finder(L,X,Count,Count3,_), 
       Place is Count3+1,Count2 is Place. 

inorder_finder(t(L,X,R),Wanted,Count,Count2,Place):- 
       dif(X,Wanted), 
       inorder_finder(L,Wanted,Count,Count3,Place1), 
       Count4 is Count3+1, 
       inorder_finder(R,Wanted,Count4,Count2,Place2), 
       Place is max(Place1,Place2). 

예 :

?- inorder_finder(t(t(t(nil,"d",t(nil,"g",nil)),"b",t(nil,"e",nil)),"a",t(t(nil,"f",t(nil,"h",nil)),"c",nil)),"c",0,_,P). 
P = 8 ; 
false. 

?- inorder_finder(t(t(t(nil,"d",t(nil,"g",nil)),"b",t(nil,"e",nil)),"a",t(t(nil,"f",t(nil,"h",nil)),"c",nil)),"W",0,_,P). 
P = -1. 

?- inorder_finder(t(t(t(nil,"d",t(nil,"g",nil)),"b",t(nil,"e",nil)),"a",t(t(nil,"f",t(nil,"h",nil)),"c",nil)),"d",0,_,P). 
P = 1 ; 
false.