检查树是否是最小堆

Question

如何在 return 值的序言中获取谓词？

我需要找到树的一个节点并检查它是否是最小堆。我猜它是这样的：-

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

输出应为真。

Answer 1

为了解决这个问题，你最好定义一些使生活更简单的实用谓词。

例如谓词lower/2。如果 Tree 为 empty，或者 Tree 的值高于 Value，则 lower(Tree,Value) 成功。所以你可以这样实现：

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

接下来我们定义谓词minheap/1。一棵 empty 树绝对是一棵 minheap。此外，如果一棵树的子节点较低并且所有子节点本身都是 minheap/1，则该树是一个最小堆，因此：

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

就是这样。这比尝试在 minheap/1 谓词中执行 all 工作要好，因为在那种情况下你应该处理 5 个案例：empty、tree(empty,val,empty)、tree(tree(..),val,empty)、tree(empty,val,tree(..)) 和 tree(tree(..),val,tree(..))。通过使用 lower/2 辅助谓词，我们只需处理两种情况：empty 和 tree/3.

检查树是否是最小堆

Check if a tree is a min heap

tree

prolog

min-heap