Prolog尋找樹中元素的位置（不使用列表）

我正在嘗試通過中間旅行方法中的二叉樹我的目標是在樹中尋找特定鍵的發生例如，我有以下三種：Prolog尋找樹中元素的位置（不使用列表）

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))

時，我會用我的inorder_finder我會得到如下：爲「C」我會得到8 爲「d」我會得到1 的「w 「我會得到-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）有什麼想法？

更新：我已經根據我得到的意見更新的代碼 - 它仍然會返回錯誤和不工作，我將它喜歡

來源

2017-10-16 user1322801

_「C 「我會得到8_爲什麼？你的樹根本沒有''c「'？ – coder

這有點令人困惑。請將位置從1或0開始？您的無效位置設置爲-1，但如果位置<1，則代碼會繼續搜索，這意味着0被視爲無效的位置指示符。你是什麼意思*目前它不工作？*它不起作用的方式？最後，如果你在顯示'inorder_finder（...）時調用謂詞，你會得到一個錯誤，因爲在Prolog中，函數和左括號之間不能有空格。 – lurker

嗨 - 首先感謝我更新了樹（它沒有複製我用c寫的第二行），並更新了謂詞沒有空格，我需要它的第一個指標是1，任何建議我做錯了什麼？ – user1322801

最明顯的錯誤在評論中已經提到，有什麼仍然是：

Place<1：我不明白爲什麼？地點可能有值大於1
inorder_place更大：從未定義...
inorder_place(t(_,X,_),X,Count,Place):-Place is Count+1.：即使你找到你需要先遞歸枚舉樹的左分支，然後通緝信廣場（見下面的答案）的信
我認爲問題可以分兩部分解決，一個按順序枚舉所有節點，然後簡單地遍歷，直到找到正確的節點。儘管我沒有遵循這個版本（甚至更清楚），因爲使用簡單混合的解決方案會更有效，因爲您可能不需要枚舉所有節點。對於這次嘗試，你正在試圖做我認爲你需要兩個計數器- 第一個調用inorder_find當計數器（..），如進入時，第二計數器將返回這裏，以停止計數繼續從那裏在樹的右邊分支。
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.

來源

2017-10-17 18:01:58 coder

Prolog尋找樹中元素的位置（不使用列表）

回答

相關問題