在Prolog中合併兩個二叉搜索樹

我正在處理一個SWI-Prolog程序，我將兩個二叉搜索樹合併在一起，但是我收到了錯誤的輸出。 BST T2是將來自BST T1的每個節點插入BST T的結果。在Prolog中合併兩個二叉搜索樹

merge(T,T1,T2).

，我現在所擁有的代碼：

add_BST(T , T1 , T2). 
add_BST(t(L , T1 , R) , t(L , T2 , R), t(t(L , ROOT , RIGHT) , T1 , NT)) :- 
    T1 < T2 , add_BST(T2 , T1 , NT). 
add_BST(t(L , T1 , R) , t(L , T2 , R), t(NT1 , T1 ,t(LEFT , ROOT ,R))) :- 
    T1 > T2 , add_BST(T2 , T1 ,NT1).

輸出此：

?- add_BST(t(nil , 1 , nil) , t(nil , 2 , nil) , NT). 

true; 

NT=t(t(nil,_G1601, _G1602),1,_G1598)

我希望得到的輸出二進制搜索樹和不知道是什麼我做錯了。任何幫助將不勝感激。

來源

2016-03-06 user3765848

你有一些不使用變量的情況。例如，在你的第二條規則中，應該使用什麼變量「ROOT」？ –

ROOT是爲了存儲樹的屋頂 – user3765848

我猜你試圖編譯這段代碼時會得到警告。不要忽視它們：如果你弄清楚爲什麼你會得到警告，以及如何避免它們，你可以自己解決問題。 – 2016-03-06 21:01:58

從小開始。先從你已經知道：

add_BST(t(nil , 1 , nil) , t(nil , 2 , nil) , NT) :-

這是一個非常有效的一段代碼，斷言其與t(nil , 2 , nil)合併t(nil , 1 , nil)涉及的頭。我們對這種情況瞭解多少？

1 < 2,

其結果應該很明顯是

NT = t(t(nil , 1 , nil) , 2, nil).

試試：

?- add_BST(t(nil , 1 , nil) , t(nil , 2 , nil) , NT).

，或者

?- A=1, B=2, add_BST(t(nil , A , nil) , t(nil , B , nil) , NT).

這一個希望讓我們重新編寫的想法它作爲

add_BST(t(nil , A , nil) , t(nil , B , nil) , NT) :- 
    A < B, 
    NT = t(t(nil , A , nil) , B, nil).

您應該能夠從這裏進一步推廣，並涵蓋更多可能的情況（如A > B等）。

來源

2016-03-07 22:32:01

@ user3765848好，這對你有幫助嗎？你有什麼問題嗎？ –

在Prolog中合併兩個二叉搜索樹

回答

相關問題