c++ - 二叉搜索树上的范围查询（递归）

Question

我被要求编写一些基于模板的代码，该模板将从范围查询中返回一个键向量（即 [x,y] 中的所有键）。请耐心等待，我对递归也很陌生。

template <typename Key, typename Value>
vector<<BSTNode<Key, Value>*> range_query(BSTNode<Key, Value>* root,Key key1,Key key2) {

vector<BSTNode<Key, Value>*> found;
if(key1 > key2) return found;

while(root != NULL){
    range_query(root->left,key1,key2);
    range_query(root->right,key1,key2);
    if(root->key >= key1 && root->key <= key2) found.push_back(root);
}

由于我假设向量中的顺序无关紧要，这是否是遍历并将键存储在向量中的正确方法？另外，我将如何在递归结束时返回完成的向量？

Answer 1

作为参数传入（对 vector 的引用）并在函数内部更新：

template <typename Key, typename Value>
void range_query(BSTNode<Key, Value>* root, Key key1, Key key2, vector<<BSTNode<Key, Value>*>& found) 
{
    if (!root) return;
    if(key1 > key2) return;

    range_query(root->left,key1,key2,found);
    range_query(root->right,key1,key2,found);

    if(root->key >= key1 && root->key <= key2) 
        found.push_back(root);
    }
} 

我稍微修改了你的代码。