在递归函数中存储堆栈

我试图通过二叉搜索树进行搜索，并将每个节点存储在堆栈中，以便遍历树以记住我的路径，以便我可以执行旋转。在递归函数中存储堆栈

这里是我的代码：

template <typename T> 
bool BST<T>::contains(const T& v, BSTNode *&t) 
{ 
    stack<BSTNode*> s; 
    BSTNode * g; 
    BSTNode * p; 

    if(t == NULL) 
     return false; 
    else if(v < t->element){ 
     s.push(t); 
     return contains(v, t->leftChild); 
    } 

    else if(v > t->element){ 
     s.push(t); 
     return contains(v, t->rightChild); 
    } 
    else 
    { 
    t->search_c += 1; 

    if(t->search_c > threshold) //we need to rotate 
    {//begin rotation 

    cout << s.size(); //outputs 1 


    }//end rotation 

    return true; 
    } 
}

我觉得现在的问题是，堆栈（S）超出范围的每个函数被调用一次，所以当它发现我在寻找它的价值是存储在堆栈中的唯一东西。所以我的问题是，我该如何做到让堆栈包含我遍历的每个项目而不仅仅是最后一个项目？

来源

2011-03-29 dubyaa

你可以让堆栈变成一个静态变量吗？或者将栈作为参数传递给函数？ – dhorn 2011-03-29 20:10:44

你可以作为第三个参数传递堆栈吗？当然，通过参考;） – fredoverflow 2011-03-29 20:11:40

将一个（非const）引用与其他参数一起传递给堆栈。您可能需要一个“设置”功能来初始创建堆栈。

来源

2011-03-29 20:13:36 Mat

我正试图设置此刻 – dubyaa 2011-03-29 20:18:00

好吧，我搞砸了这里的东西。我做了函数原型'bool contains（const T＆v，BSTNode *＆t，stack &s);'和另一个调用“contains”的函数，它具有'stack s; return contains（v，root，s）;'给我一个错误说没有匹配的原型 – dubyaa 2011-03-29 20:35:21

可能是一个错误的地方。你可以用你的进度更新你的问题到目前为止，并且完整的编译器错误信息（通常包含关于错误的线索） – Mat 2011-03-29 20:39:44

看起来你需要让堆栈成为类的成员，或者将你的contains方法和堆栈提取到一个新的类中，从BST类中调用它。

来源

2011-03-29 20:14:10 quamrana

通常会发生的是，您创建一个私有重载，它引用原始被调用函数的本地堆栈上的堆栈。

template<typename T> class BST { 
public: 
    bool contains(const T&, BSTNode*&); 
private: 
    bool contains(const T&, BSTNode*&, stack<BSTNode*>&); 
};

来源

2011-03-29 20:17:43 Puppy

第二种方法应该是...... stack ＆）;'我想。 – Mat 2011-03-29 20:22:52

在递归函数中存储堆栈

回答

相关问题