在递归函数中存储堆栈
我试图搜索二叉搜索树，并在遍历树时将每个节点存储在堆栈中，以便记住我的路径，以便可以执行旋转。
这是我的代码：
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;
}
}
我认为问题在于每次调用函数时堆栈都会超出范围，因此当它找到我正在查找的值时，它是堆栈中存储的唯一内容。所以我的问题是，如何使堆栈包含我遍历的每一项而不仅仅是最后一项？
I am trying to search through a binary search tree and store each node in a stack as I traverse through the tree in order to remember my path so that I can perform rotations.
Here is my code:
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;
}
}
I think that the problem is that the stack (s) goes out of scope each time the function is called, so when it find the value I am looking for it is the only thing stored in the stack. So my question is, how do I make it so that the stack contains each item I traversed through instead of just the last one?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
将（非常量）引用与其他参数一起传递给堆栈。
您可能需要一个“设置”函数来最初创建堆栈。
Pass a (non-const) reference to the stack along with the other arguments.
You might need a "setup" function to create the stack initially.
通常发生的情况是，您进行私有重载，该重载引用原始被调用函数的本地堆栈上的堆栈。
What usually happens is that you make a private overload which takes a reference to the stack which is on the original called function's local stack.
看起来您需要使堆栈成为该类的成员，或者将
contains方法和堆栈提取到一个新类中，从BST类调用它。It looks like you need to make the stack a member of the class, or extract your
containsmethod and the stack into a new class, calling it from theBSTclass.