检查树是否是最小堆 [英] Check if a tree is a min heap

问题描述

如何在 prolog 中获取谓词以返回值?

How do I get a predicate in prolog to return a value?

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

I need to find a node of a tree and also check if its a min heap or not. I'm guessing it goes something like this:-

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

到目前为止我的代码是这样的

My code so far is this

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

输出应该是真的.

推荐答案

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

In order to solve this, you better define some utility predicates that make life simpler.

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

For instance predicate lower/2. lower(Tree,Value) that succeeds if either Tree is empty, or the value of the Tree is higher than Value. So you can implement this like:

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

接下来我们定义谓词minheap/1.空 树绝对是minheap.此外，如果一棵树的子节点较低并且所有子节点都是 minheap/1 本身，那么它就是一个 minheap，所以:

Next we define the predicate minheap/1. An empty tree is definitely a minheap. Furthermore a tree is a minheap if its children are lower and all the children are minheap/1s themselves, so:

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

就是这样.这比尝试在 minheap/1 谓词中完成所有工作要好，因为在这种情况下您应该处理五种情况:空, tree(empty,val,empty), tree(tree(..),val,empty), tree(empty,val),tree(..)) 和 tree(tree(..),val,tree(..)).通过使用 lower/2 辅助谓词，我们只需要处理两种情况:empty 和 tree/3.

and that's it. This is better than trying to do all the work in the minheap/1 predicate since in that case you should handle five cases: empty, tree(empty,val,empty), tree(tree(..),val,empty), tree(empty,val,tree(..)) and tree(tree(..),val,tree(..)). By using the lower/2 helper predicate, we only have to handle two cases: empty and tree/3.

这篇关于检查树是否是最小堆的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！