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