检查结构是否是带有prolog的二叉树

Question

使用结构：

tree(tip).
tree(bin(L,_,R)) :- tree(L), tree(R).

如何确定一棵树是否是左边每个节点都比右边每个节点小的二叉树？

到目前为止，我所拥有的是：

bst(tip).
bst(tip, _, _).
bst(bin(bin(L, Ln, R), N, tip)):- N > Ln -> bst(bin(L, Ln, R)).
bst(bin(bin(L, Ln, R), N, bin(L, Rn, R))):- (
N > Ln ->  bst(bin(L, Ln, R)); false,   
N < Rn ->  bst(bin(L, Rn, R)); false
).

Answer 1

我认为你把这弄得太复杂了。我们可以在这里定义一个谓词来检查间隔，并用一个null值来检查(无(有界的间隔。例如：

check(null, X) :-
!.
check(X, null) :-
!.
check(X, Y) :-
X < Y.

接下来，我们可以创建一个谓词，最初传递两个null作为边界：

bst(Tree) :-
bst(Tree, null, null).

现在我们可以实现bst/3谓词，对于每个bin/3复合项，我们检查该值是否在范围内，然后递归地检查该值作为新边界：

bst(tip, _, _).
bst(bin(L, V1, R), V0, V2) :-
check(V0, V1),
check(V1, V2),
bst(L, V0, V1),
bst(R, V1, V2).

Answer 2

以下是 Willem 作为解决方案提供的略有不同。它只是以不同的方式处理空分支：

bst(Tree) :-
bst(Tree, _).
bst(tree(tip, V, tip), V).
bst(tree(tip, V, R), Rmax) :-
bst(R, Rmax),
V =< Rmax.
bst(tree(L, V, tip), Lmax) :-
bst(L, Lmax),
Lmax =< V.
bst(tree(L, V, R), R) :-
bst(L, Lmax),
bst(R, Rmax),
Lmax =< V, V =< Rmax.