Prolog二叉搜索树测试-不需要的父节点的父节点比较

我是 Prolog 菜鸟，请记住这一点。 我尝试编写一个谓词来确定某个给定术语是否是二叉搜索树。我想出了这段代码：

is_btree(nil).
is_btree(node(N,L,R)) :-
   number(N),
   is_btree(L), 
   is_btree(R), 
   small(N, R),
   big(N, L).

small(N, nil).
small(N, node(M,L,R)) :-
   N < M,
   small(N, L),
   small(N, R).

big(N, nil).
big(N, node(M,L,R)) :-
   N > M,
   big(N, L),
   big(N, R).

它工作得很好，直到我测试右侧有一个节点的图，该节点通过“高于父节点”的条件，但它高于或等于父节点的父节点。在这种情况下，Prolog 报告失败。

以下是意外失败的示例查询：

?- is_btree(node(9,node( 3,node( 2,nil,nil),
                           node(10,nil,nil)),
                   node(12,node( 8,nil,nil),
                           node(15,nil,nil)))).
false.

当左侧的某个节点高于父节点的父节点时，会出现非常类似的问题，如下图所示：

如何仅使用其直接父节点的值而不是父节点的父节点的值来检查节点值？

这是对您要解决的问题的稍微不同的看法。

1. dcg /questions/tagged/dcg用于收集元素：按顺序树遍历 /questions/tagged/tree-traversal

   
   
   in_order(nil) --> [].
   in_order(node(X,L,R)) --> in_order(L), [X], in_order(R).
     

2. clpfd /questions/tagged/clpfd用于关联相邻的list /questions/tagged/list元素（都是有限域变量）

   
   
   chain(Zs, #<)
     

让我们把它们放在一起并定义is_bintreeFD/1像这样：

:- use_module http://www.swi-prolog.org/pldoc/doc_for?object=use_module/1(library(clpfd) http://www.swi-prolog.org/man/clpfd.html).

is_bintreeFD(T) :-
   phrase http://www.swi-prolog.org/pldoc/doc_for?object=phrase/2(in_order(T), Zs),
   chain http://www.swi-prolog.org/pldoc/doc_for?object=chain/2(Zs, #<).
  

示例查询：

?- is_bintreeFD(node(9,node( 3,node(2,nil,nil),node(10,nil,nil)),
                       node(12,node(8,nil,nil),node(15,nil,nil)))).
false.

?- is_bintreeFD(node(9,node( 3,node( 2,nil,nil),node( 8,nil,nil)),
                       node(12,node(10,nil,nil),node(15,nil,nil)))).
true.