Prolog - 检查一个二叉树是否被排序

Question

我想在Prolog中编写一个程序来确认一个整数b树是否被排序。顺序从小到大。 这是迄今为止我写的，但我没有达到任何坚实的工作。有人知道如何做到这一点？

Domains 
element=integer 
tree=a(tree,element,tree);void 

Predicates 
    nondeterm ordre(tree) 

Clauses 
    order(a(_,Node,a(_,Node2,_))):-Node<Node2. 
    order(a(Esq,Node,Dre)) :- 
     order(Esq), 
     write(Node),nl, 
     order(Dre). 

Goal 
     order(a(a(void,1,void),2,a(a(void,3,void),4,a(void,6,void)))). 

巨大的谢谢。

Answer 1

domains 
    element = integer 
    arbre = a (arbre, element, arbre) ; buit 

predicates 
    nondeterm ordenat (arbre) 
    nondeterm ordenat2 (arbre, element) 

clauses 
    ordenat2 (a (buit, E, buit), E). 
    ordenat2 (a (buit, E, R), MR) :- 
     ordenat2 (R, MR), 
     E<MR. 
    ordenat2 (a (L, E, buit), E) :- 
     ordenat2 (L, ML), 
     ML<E. 
    ordenat2 (a (L, E, R), MR) :- 
     ordenat2 (L, ML), ML<E, 
     ordenat2 (R, MR), E<MR. 

    ordenat (A) :- 
     ordenat2 (A, _). 

goal 
    B=a (a (a (buit, 1, buit), 2, a (buit, 3, buit)), 4, a (a (buit, 5, buit), 6, a (buit, 7, buit))), 
    ordenat (B) 
    . 

结果：是

Answer 2

使用相同的相同的树结构之前（表示一个空树原子btree;表示一个非空的树结构btree(Key,Left,Right)，这样的事情应该做你：

• 空树是有序顾名思义

  is_ordered(btree). 
  

• 一个非空的树是有序的，如果

  名
  • 它的留守儿童是有序和他们的键小于当前节点

  • 其右孩子是有序的和他们的键大于当前节点

    is_ordered(btree(K , L , R)) :- 
        is_ordered(L < K) , 
        is_ordered(R > K) 
        . 
    

• 的通过定义中，空树小于任何指定的键值并且也大于任何指定的键值。

  is_ordered(btree < K). 
  is_ordered(btree > K). 
  

• 非空树小于指定的键值，如果

  • 其关键是小于指定的键，

  • 它本身就是下令

    is_ordered(btree(K1,L,R) < K) :- 
    K1 < K , 
    is_ordered(btree(K1,L,R)) 
    . 
    

• 非空树较大超过指定键值，如果

  • 其关键字大于指定的键更大，

  • 它本身就是下令

    is_ordered(btree(K1,L,R) > K) :- 
        K1 > K , 
        is_ordered(btree(K1,L,R)) 
        .