1

我需要做一个序言谓词from_list/2，这样如果我打电话，from_list([], T)我会得到一个包含列表（ints）中项目的树，到目前为止我有：

from_list([], empty).
from_list([X], T) :-
    insert(X, empty, T).
from_list([X|Y], T) :-
    from_list(Y, NT),
    insert(X, NT, T).

编辑：想通了，但它以列表的相反顺序将它们添加到树中。有什么帮助吗？

这是我的插入谓词，它似乎工作得很好。

insert( X, empty, bt(X, empty, empty) ). 
insert( X, bt(X2, L, R), bt(X2, NL, R) ) :-
    X < X2,
    !,
    insert(X, L, NL). 
insert( X, bt(X2, L, R), bt(X2, L, NR) ):-
    insert(X, R, NR).

也不是第二个不需要答案的小得多的问题

我知道 prolog 在正确使用时具有非常优雅的风格......而这段代码......不是那么优雅......

is_search(empty).
is_search( bt(_, empty, empty) ).
is_search( bt( X, empty, bt(Y,LEFT,RIGHT) ) ) :-
    X < Y,
    is_search(LEFT),
    is_search(RIGHT).
is_search( bt(X, bt(Y,LEFT,RIGHT), empty) ) :-
    X > Y,
    is_search(LEFT),
    is_search(RIGHT).
is_search( bt( X, bt(Y,L1,R1), bt(Z, L2, R2) ) ) :-
    X > Y,
    X < Z,
    is_search( bt(Y, L1, R1) ),
    is_search( bt(Z, L2, R2) ).

关于如何清理它的任何提示？

4

2 回答 2

1

关于你的第二个问题，我想说你应该描述二叉树的两种（不是五个！）情况：要么是空的，要么是一个内部节点，其中左右所有元素分别较小和较大, 并且是二叉树本身：

bt(empty).
bt(bt(Val, Left, Right)) :-
    all_smaller_than(Left, Val),
    all_larger_than(Right, Val),
    bt(Left),
    bt(Right).

我将 all_smaller_than/2 和 all_larger_than/2 作为练习留给你。提示：同样，两个子句对它们中的每一个都足够了。你也可以找到一种方法让它更快......

于 2012-05-04T12:15:26.270 回答
1

只是我这边的一个提示：

from_list([], empty).
from_list([X], T):- insert(X, empty, T).
from_list([X|Y], T):- from_list(Y, NT), insert(X, NT, T).

这是行不通的，因为您不知道第 2 行是否为空。

要以相反的顺序使用列表

reverse(X,R).

PS：据我所知，我们正在谈论 SWI-Prolog，对吗？

于 2012-04-27T12:03:36.950 回答