檢查樹是否是最小堆

如何在prolog中獲取謂詞以返回值？檢查樹是否是最小堆

我需要找到一個樹的節點，並檢查它是否是最小堆。我猜它是這樣的： -

getnode(tree(_, node, _), node).

我到目前爲止的代碼是這樣

minheap(tree(L, Node, empty)) :- 
    getnode(L, Val), 
    Node =< Val, 
    minheap(L). 
minheap(tree(empty, Node, R)) :- 
    getnode(R, Val), 
    Node =< Val, 
    minheap(R). 

getnode(tree(_,n,_) , n).

輸入是類型 -

minheap(tree(empty,3,tree(tree(empty,8,empty),5,tree(empty,7,empty)))).

輸出的應該是真實的。

來源

2017-04-03 John Keaton

「tree/3」的格式是什麼？ '樹（左，價值，右）'？ –

是的，這是正確的 –

如果節點的值小於（或至少不大於）所有子節點的值（通常是：兩者）子節點_and_所有以子節點爲根的子樹，那麼以節點爲根的樹就是最小堆也是最小的堆。你的代碼能夠測試給定節點的_all_子節點嗎？ – CiaPan

爲了解決這個問題，你最好定義一些使生活更簡單的效用謂詞。

例如謂詞lower/2。 lower(Tree,Value)，如果Tree是empty，或者Tree的值高於Value，則成功。所以，你可以實現這個樣：

lower(empty,_). 
lower(tree(_,TreeValue,_),Value) :- 
    TreeValue >= Value.

接下來我們定義謂詞minheap/1。 empty樹絕對是minheap。此外，樹是minheap如果其子下，所有的孩子都minheap/1 s ^自己，所以：

minheap(empty). 
minheap(tree(Left,Value,Right)) :- 
    lower(Left,Value), 
    lower(Right,Value), 
    minheap(Left), 
    minheap(Right).

，就是這樣。這是不是試圖做所有因爲在這種情況下，在minheap/1謂詞的工作，你應該處理案件更好：empty，tree(empty,val,empty)，tree(tree(..),val,empty)，tree(empty,val,tree(..))和tree(tree(..),val,tree(..))。通過使用lower/2輔助謂詞，我們只需處理兩種情況：empty和tree/3。

來源

2017-04-03 14:41:32

謝謝！我不知道爲什麼我沒有想到這一點。 –

通常，參數順序符合「pred（A，B）」的讀數爲「A is * pred * B」。 –

檢查樹是否是最小堆

回答

相關問題