检查树是否是最小堆

Question

如何让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)))).

输出应该为真。

Answer 1

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

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

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

接下来我们定义谓词minheap/1。空树绝对是minheap。此外，如果树的子级较低，并且所有子级都是minheap/1本身，则树就是minheap，所以：

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

就是这样。这比尝试在minheap/1谓词中完成所有工作要好，因为在这种情况下，您应该处理五种情况：空，树（空，val，空），树（…），val，空），树（空，val，树（…））和树（树（…），val，树（…））。通过使用下/2帮助谓词，我们只需要处理两种情况：空和树/3。