时间戳

首页 > 解决方案 > 检查结构是否是带有序言的二叉树

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

问题描述

使用结构：

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

标签： prolog

解决方案

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

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

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

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

现在我们可以实现bst/3谓词 where 对于每个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).

推荐阅读