编写一个谓词 is_heap(Tree)，如果 Tree 满足堆属性，则返回 true，否则返回 false

Question

如果

对于树中的每个非叶节点，存储在该节点上的数字小于或等于存储在其每个子节点上的数字，则数字的二叉树称为堆(或者，据说它满足堆属性(。例如，以下树满足堆属性，因为 3 ≤ 5、5 ≤ 8 和 5 ≤ 7。

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 

任何帮助都将得到认可。

Answer 1

你可以

这样开始。这里的树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),
    ....