prolog - Prolog 中二进制搜索树的范围查询

Question

我知道如何以过程方式(即，在 C++、Java 等中)对 BST 执行范围查询，但我发现很难转换为 Prolog 语言。

程序的方式应该是这样的:

http://www.geeksforgeeks.org/print-bst-keys-in-the-given-range/

任何提示如何将其转换为 Prolog 范例？

非常感谢大家

Answer 1

您引用的网站的声明性描述可以直接翻译成 Prolog:

1) 如果key大于k1，则递归调用左子树。

序言翻译:

bst(tree(Key, Left, Right), K1, K2, Value) :-
        Key > K1,
        bst(Left, K1, K2, Value).

2) 如果 key 在范围内，则打印 key 。

我们不使用像“print”这样的不纯谓词，因为它们是不可逆的。相反，我们使用 Prolog 为我们报告顶层的绑定(bind):

bst(tree(Key, _, _), K1, K2, Key) :- between(K1, K2, Key).

3) 如果key小于k2，则递归调用右子树。

我把它留作练习。

查询

?- bst(树, K1, K2, 值).

将为给定范围内的 Value 回溯绑定(bind)产生 yield 。

如果使用约束，则可以在所有方向上使用此谓词，还可以生成包含值的树。