编写一个谓词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

回答

相关问题