我知道如何以过程方式(即,在 C++、Java 等中)对 BST 执行范围查询,但我发现很难转换为 Prolog 语言。
程序的方式应该是这样的:
http://www.geeksforgeeks.org/print-bst-keys-in-the-given-range/
任何提示如何将其转换为 Prolog 范例?
非常感谢大家
最佳答案
您引用的网站的声明性描述可以直接翻译成 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 。
如果使用约束,则可以在所有方向上使用此谓词,还可以生成包含值的树。
关于prolog - Prolog 中二进制搜索树的范围查询,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20466747/