編寫一個謂詞is_heap（Tree），如果Tree滿足堆屬性，則返回true，否則返回false

如果對於每個非數據類型，數字的二叉樹被稱爲堆（或者它被認爲滿足堆屬性）在樹中的葉節點中，存儲在該節點處的數字小於或等於存儲在其每個子節點處的數字。例如，下面的樹滿足堆屬性，因爲3≤5,5≤8和5≤7.編寫一個謂詞is_heap（Tree），如果Tree滿足堆屬性，則返回true，否則返回false

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

在另一方面，下面的樹不滿足堆屬性，因爲圖6是不小於或等於5。

tree(tree(tree(empty,4,empty), 
     3,tree(empty,5,empty)),6,tree(tree(empty,9,empty),7,empty))

實施例：

?- is_heap(tree(tree(tree(empty,4,empty), 
     3,tree(empty,5,empty)),6,tree(tree(empty,9,empty),7,empty))). 
false. 

?- is_heap(tree(empty,3,tree(tree(empty,8,empty),5,tree(empty,7,empty)))). 
true

任何幫助將appriciated。

來源

2017-04-04 Utkarsh Atri

我在書中所看到的是'樹（價值，左，右）''不樹（左，價值，右）'，但我想這並不重要。更重要的是，你根本不需要編寫任何代碼，只要求別人編寫代碼即使你需要編寫的代碼編寫起來相當微不足道，也可能寫得和我或其他人一樣好。我給你減去這個:-(對不起 – 2017-04-04 12:44:59

這裏是想法：你看每個非葉節點的價值，然後你檢查左邊和右邊的孩子都小於這個值，你只要你有'樹（L，V，R）'而不是'空'，那麼如果你成功了，你會得到'true'，否則你會得到'false'。 – 2017-04-04 12:51:09

[檢查樹是否是最小堆]可能重複（http：/ /stackoverflow.com/questions/43187131/check-if-a-tree-is-a-min-heap） – 2017-04-04 20:32:28

你可以這樣開始。這裏的樹是tree(Value, Left, Right)，但你可以很容易地改變它。然後你開始：

is_heap(empty). 
is_heap(tree(X, L, R)) :- 
    is_heap(L, X), 
    is_heap(R, X).

現在你只需要寫is_heap/2然後你就緒了。喜歡的東西：

is_heap(empty, ...). 
is_heap(tree(X, L, R), X0) :- 
    ..., 
    is_heap(L, X), 
    ....

在大多數樹的例子

來源

2017-04-04 13:29:11

編寫一個謂詞is_heap（Tree），如果Tree滿足堆屬性，則返回true，否則返回false

回答

相關問題