Prolog - 이진 트리가 정렬되었는지 확인

Question

정수의 b- 트리가 정렬되었는지 확인하는 프로그램을 Prolog에 작성하고 싶습니다. 순서는 점점 작아집니다. 이것은 내가 지금까지 작성했지만 굳건한 작업에 도달하지는 못합니다. 누군가 그 일을하는 방법을 알고 있습니까?

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

큰 감사. 빈 트리를 나타내는 원자 btree (이전과 동일 같은 트리 구조 사용

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(Key,Left,Right)를,이 같은 당신을 수행해야합니다

• 빈 트리가 주문한 정의

  is_ordered(btree). 
  

• 비 빈 나무 주문한

  ,536 경우
  • 의 왼쪽 아이들은 정렬과 키는

  • 오른쪽 아이들이 정렬 현재 노드의보다 작은 자신의 키에 의해 현재 노드

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