c++ - BST中的中序遍历

Question

我有一个平衡的整数二叉搜索树，我想找到最左边的节点，它存储大于或等于固定数字的整数，如 a 使用 ask(a )。

例如，假设我在我的树中添加了以下点，8,10,3,6,1,4,7,14,13

那么树应该是这样的:

现在ask(1)应该是1，ask(3)应该是3，ask(2) 应该是 3 等等。

我认为我可以使用中序遍历来编写我的ask 函数，但我不知道如何做。

到目前为止，我已经编写了这段代码:

inorderFind(node->left, a);
if (node->key.getX() >= a)
    return node;
inorderFind(node->right, a);

第一个参数是当前树节点，a 是上面描述的a。我知道我可以使用 bool 变量，如 flag 并在 if 条件成立时将其设置为 true，然后它会阻止行走通过树的其他节点并返回错误节点。还有什么我可以做的吗？

Answer 1

树具有允许通过简单的递归算法进行查询的奇妙特性。因此，让我们尝试找到您的查询的递归公式。

说 LEFTMOST(u) 是一个回答这个问题的函数:

Given the binary search subtree rooted at node u, with(possibly null) left and right children l and r, respectively, what is the left-most node with a value >= a?

关系很简单:

LEFTMOST(u) = LEFTMOST(l) if it exists
              LEFTMOST(r) otherwise

就是这样。如何将其转化为您的问题以及如何处理“空”和“不存在”等概念是您表示的一个功能。