Хранение стека в рекурсивной функции - PullRequest
Новая
       15

Хранение стека в рекурсивной функции

0 голосов
/ 30 марта 2011

Я пытаюсь выполнить поиск по двоичному дереву поиска и сохранить каждый узел в стеке, пока я прохожу через дерево, чтобы запомнить свой путь, чтобы я мог выполнять вращения.

Вот мой код: 

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

Я думаю, что проблема в том, что стек (ы) выходит из области видимости каждый раз, когда вызывается функция, поэтому, когда она находит искомое значение, это единственное, что хранится в стеке. Итак, мой вопрос: как мне сделать так, чтобы в стеке был каждый элемент, через который я прошел, а не только последний?

Ответы [ 3 ]

2 голосов
/ 30 марта 2011

Передайте (неконстантную) ссылку на стек вместе с другими аргументами. Для первоначального создания стека может потребоваться функция «setup».

1 голос
/ 30 марта 2011

Обычно происходит то, что вы делаете частную перегрузку, которая принимает ссылку на стек, который находится в локальном стеке исходной вызываемой функции. 

template<typename T> class BST {
public:
    bool contains(const T&, BSTNode*&);
private:
    bool contains(const T&, BSTNode*&, stack<BSTNode*>&);
};
0 голосов
/ 30 марта 2011

Похоже, вам нужно сделать стек членом класса или извлечь ваш метод contains и стек в новый класс, вызвав его из класса BST.

...