c++ - 在 push_back 中调用递归函数

Question

我正在编写一个函数来使用二叉搜索树中的值按升序填充向量。我也试图将这个函数的运行时间保持在 O(n)。我想我需要调用一个遍历 bst 并按升序获取数字的递归函数。我对如何使用递归函数的结果感到困惑。像这样在推回中使用递归函数可以吗？

void vector_function(){
    std::vector<int> *v = new std::vector<int>(); 
    v.pushback(recursive_function(node *p));
}

例如，如果二叉搜索树的值为 5、3、4、7，则结果向量将具有 3、4、5、7

标签： c++c++11recursionvector

Answer 1

我对如何使用递归函数的结果感到困惑。像这样在推回中使用递归函数可以吗？

我可以想到两种方法。

选项1

更改recursive_function为也接受对 a 的引用std::vector<int>。适当地将其实现更新push_back为向量的元素。调用时将向量传递recursive_function给它。

void recursive_function(node* p, std::vector<int>& v)
{

    // When appropriate...
    v.push_back(p.data);
}

并将其用作

void vector_function(){
    std::vector<int> v;
    recursive_function(p, v));
}

选项 2

更改 recursive_function为也接受一个std::function. 更新其实现以std::function使用节点的值适当地调用 。使用可以转换为在函数调用std::function中recursive_function接受的 lambda 函数。请注意push_back在传递给它的参数的情况下调用 lambda 函数中的向量。

void recursive_function(node* p, std::function<void(int)> f)
{

    // When appropriate...
    f(p.data);
}

并将其用作

void vector_function(){
    std::vector<int> v;
    recursive_function(p, [&v](int e) -> void { v.push_back(e); });
}