在Prolog中对二叉搜索树进行范围查询

Question

我知道如何在过程化语言（如C++、Java等）中执行二叉搜索树的范围查询，但我觉得将其转换为Prolog语言比较困难。

过程化语言的实现方式应该是：

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

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

非常感谢大家。

- Papatakis

Answer 1

你引用网站上的声明性描述可以直接翻译为Prolog：

1）如果关键字大于k1，则在左子树中递归调用。

Prolog翻译：

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

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

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

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

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

我将这个留作练习。

查询

?- bst(Tree, K1, K2, Value).

回溯时，该查询将返回给定范围内的Value绑定。

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

- mat

---

它的效果非常好...但是如果我想要在一个输出列表中一次性得到所有答案呢？这个解决方案逐个检索结果。 - Papatakis

在Prolog中收集所有解决方案很容易：使用像setof/3这样的全解决方案谓词。 - mat

Answer 2

在编程语言C++或Java中，你可以做与此相同的事情。 只要你写了所需的最小代码（在C++中），就有非常高的机会得到正确的结果。这通常涉及到递归定义，例如：

// pseudocode - Elem must implement operator<
struct BST<Elem> {
  bool find(const Elem e) { return find(root, e) }
private:
  bool find(Node n, Elem e) {
    if (!n) return false;
    if (n.payload() == e) return true;
    return n.payload() < e ? find(n.left) : find(n.right);
  }
}

相同的搜索可以通过手动展开堆栈，利用（呃）堆栈，然后迭代来编写。

stack<Node> stack; stack.push(root);
while (!stack.isEmpty()) {
  Node n = stack.pop();
  // check found, return true
  // push left or right...
}

在Prolog中，堆栈是“嵌入”语言中的：只需说明解决方案的“形式”即可。假设有一棵树如t（Payload，Left，Right），默认值为t（0，-，-），则可以执行以下操作：

% note: untested
bst(t(Payload,_,_), Payload). % found
bst(t(Payload,L,R), Sought) :- Sought @< Payload -> bst(L, Sought) ; bst(R, Sought).

关于 C++ 的注释：我在 Github 上上传了一个声明性、非侵入式的 C++ 接口示例（链接地址：loqt），它基于原始指针模型（Agraph_t* 和 friends）。有了这个接口，现在我们有 lambda 在 C++ 中，实现变得非常简单。

// live code here
void lqXDotScene::dump(QString m) const {
    qDebug() << m;
    cg->depth_first([&](Gp t) { qDebug() << "graph" << gvname(t) << CVP(find_graph(t)); });
    qDebug() << "nodes";
    cg->for_nodes([&](Np n) {
        qDebug() << "node" << gvname(n) << CVP(find_node(n));
        cg->for_edges_out(n, [&](Ep e) {
            qDebug() << "edge" << gvname(e) << CVP(find_edge(e)) << "to" << gvname(e->node) << CVP(find_node(e->node));
        });
    });
}

这一行

    cg->depth_first([&](Gp t) { qDebug() << "graph" << gvname(t) << CVP(find_graph(t)); 

执行一个完整的访问。find_graph、find_等都是成员函数：lambda非常强大。

- CapelliC