Как обновить указатели, когда они помещены в std :: stack с помощью итерации?

Question

Вот ситуация:

Если указан указатель на root дерева двоичного поиска (целых чисел) root и целое число data, выполните функцию rotate (предопределено) на всех наследственных узлах узла, содержащего data, с использованием итеративного метода. Для простоты предположим, что data существует и всегда происходит на конечных узлах.

Функция rotate передает указатель по ссылке следующим образом:

struct Node
{
    Node *left;
    int data;
    Node *right;
};

void rotate(Node* &root); // performs some rotation on the root and reflects the change.

void search(Node* &root, int data)
{
    stack<Node*> s;
    while(root->data!=data)
    {
        s.push(root);
        if(data<root->data)
            root=root->left;
        else
            root=root->right;
    }

    while(!s.empty())
    {
        rotate(s.top()); // does not reflect changes to root
        s.pop();
    }
}

Итерационная версия требует использования стека. std::stack::push() функция перемещает указатель по значению. В результате, при совмещении указателей предков я буду отражать изменения в стеке.

Как лучше обойти эту ситуацию?

Answer 1

Это решает мою проблему.

void search(Node* &root, int data)
{   
    if(root->data==data)
        return;

    stack<Node**> s;
    while(root->data!=data)
    {
        if(data<root->data)
        {
            s.push(&root->left);
            root=root->left;
        }
        else
        {
            s.push(&root->right);
            root=root->right;
        }
    }
    s.pop(); // to avoid leaf
    while(!s.empty())
    {
        rotate(*s.top())
        s.pop();
    }
    rotate(root);
}