c++ - 在递归函数中存储堆栈

Question

我正在尝试搜索一个二叉搜索树，并在我遍历该树时将每个节点存储在一个堆栈中，以便记住我的路径，以便我可以执行旋转。

这是我的代码:

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;
   }
}

我认为问题是每次调用函数时堆栈都超出范围，所以当它找到我正在寻找的值时，它是唯一存储在堆栈中的东西。所以我的问题是，如何使堆栈包含我遍历的每一项，而不仅仅是最后一项？

Answer 1

将一个(非常量)引用连同其他参数一起传递到堆栈。 您可能需要一个“设置”函数来最初创建堆栈。