Prolog - 检查二叉树是否有序

发布于 2024-12-23 18:39:16 字数 451 浏览 2 评论 0原文

我想在 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)))).

非常感谢。

原文

I want to write a program in Prolog that confirms if a b-tree of integers is ordered or not. The order goes from smaller to greater.
This is what I've written so far but I do not reach any solid work. Does someone know how to do that?

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

Huge Thanks.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

思慕 2024-12-30 18:39:16

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

结果：是

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

Result: yes

回复收藏 0 原文

盛装女皇 2024-12-30 18:39:16

使用与之前相同的树结构（原子 btree 表示空树；结构 btree(Key,Left,Right) 表示非空树，类似于这应该对你有用：

空树按定义排序
```
is_ordered( btree )。
```
非空树是有序的，如果
- 它的左子节点是有序的，并且它们的键小于当前节点的键
- 它的右子节点是有序的，并且它们的键大于当前节点的键
```
is_ordered( btree( K , L , R ) ) :-
  is_ordered( L < K ) ,
  is_ordered( R > K )
  。
```
根据定义，空树小于任何指定的键值，也大于任何指定的键值。< /p>
```
is_ordered( btree < K )。
is_ordered( btree > K )。
```
非空树小于指定的键值，如果
- 其密钥小于指定的密钥，并且
- 它本身是有序的
```
is_ordered( btree(K1,L,R) < K ) :-
K1＜ ,
is_ordered( btree(K1,L,R) )
。
```
非空树大于指定的键值，如果
- 它的键大于指定的键，并且
- 它本身是有序的
```
is_ordered( btree(K1,L,R) > K ) :-
  K1> ,
  is_ordered( btree(K1,L,R) )
  。
```

Using the same same tree structure as before (the atom btree denoting an empty tree; the structure btree(Key,Left,Right) denoting a non-empty tree, something like this should do you:

An empty tree is ordered by definition
```
is_ordered( btree ).
```
A non-empty tree is ordered if
- its left children are ordered and their keys are less than that of the current node
- its right children are ordered and their keys are greater than that of the current node
```
is_ordered( btree( K , L , R ) ) :-
  is_ordered( L < K ) ,
  is_ordered( R > K )
  .
```
By definition, an empty tree is less than any specified key value and also greater than any specified key value.
```
is_ordered( btree < K ).
is_ordered( btree > K ).
```
A non-empty tree is less than a specified key value if
- its key is less than the specified key, and
- it is itself ordered
```
is_ordered( btree(K1,L,R) < K ) :-
K1 < K ,
is_ordered( btree(K1,L,R) )
.
```
A non-empty tree is greater than a specified key value if
- its key is greater than the specified key, and
- it is itself ordered
```
is_ordered( btree(K1,L,R) > K ) :-
  K1 > K ,
  is_ordered( btree(K1,L,R) )
  .
```