时间戳

首页 > 解决方案 > 如何在函数的递归调用之间传递值？

c++ - 如何在函数的递归调用之间传递值？

问题描述

我有一个名为 inorderHelperArray 的函数，它接受一个数组和一个指向二叉搜索树根节点的指针，并使用中序遍历从 BST 中的每个节点获取数据并将数据放入一个数组中。这是该函数的样子：

void BinTree::inorderHelperArray(NodeData* a[], Node *startNode) const{
    /*static*/ int i = 0;
    //This code works if I set i as a static int.
    //However, I cannot call this function again, as i is never reset to 0.
    
    if(startNode != nullptr){
        inorderHelperArray(a, startNode->left);
        cout << "i: " << i << endl;
        a[i++] = startNode->data;
        inorderHelperArray(a, startNode->right);
    }
}

如果 i 在static int i = 0;. 但是，这是一个问题，就好像我再次调用 inorderHelperArray 一样，代码会中断。i 永远不会重置为 0，我最终将数组中的值分配给我“离开”的任何地方。例如，如果我调用 inorderHelperArray 并且 BST 有 13 个节点，那么我将是 13。如果我然后再次调用 inorderHelperArray ，我将从 13 开始，这意味着我将在我尝试创建的数组中分配值开始在索引 13 处。如果 i 未声明为 static int i=0;，那么这不起作用，因为每次对函数进行递归调用时，i 都保持为 0。

谁能给我一些关于如何让上述代码正常工作的建议？有没有一种方法可以获得静态变量的好处，但是一旦我在最终递归调用后退出 inorderHelperArray ，它就会自行重置？

标签： c++arraysrecursionbinary-search-tree

解决方案

我建议你改变你的界面。可能最好的改变是通过引用传入一个向量，并在您访问数据时将其 push_back。由于移动语义，这应该是有效的返回。

void inorderHelper(std::vector<NodeData*>& a, Node *startNode) {
    if(startNode != nullptr) {
        inorderHelper(a, startNode->left);
        a.push_back(startNode->data);
        inorderHelper(a, startNode->right);
    }
}

auto inorder(Node * startNode) {
    std::vector<NodeData*> result;
    inorderHelper(result, startNode);
    return result;
}

另一种方法，更接近您的原始方法 - 但前提是您必须使用数组（恕我直言，这是一个坏主意，因为没有针对内存覆盖的保护，并且容易出错并且可能导致泄漏），是传递整数通过引用，以类似于我上面的向量的方式：

void inorderHelper(NodeData* a[], int& i, NodeData *startNode) {
    if(startNode != nullptr) {
        inorderHelper(a, i, startNode->left);
        a[i++] = startNode->data;
        inorderHelper(a, startNode->right);
    }
}

void inorder(NodeData* a[], Node * startNode) {
    int i = 0;
    inorderHelper(a, i, startNode);
}

我从一个类中删除了这些函数，以便它们可以单独显示。

推荐阅读