BST:虚拟价值不应该被忽视,因为它应该是

Question

我试图在C++中实现BST.这是一个特定的成员函数,用于遍历和返回带有树元素的向量.现在问题出现在我设置为当前节点的stack pop()函数中.
void value not ignored as it ought to be

我理解空堆栈将在前面的pop()调用之后返回一个void值.但是这个解决方案是什么,导致这个遍历算法需要从堆栈中检索最后一个节点.

vector <int> BSTree::in_order_traversal()
{

vector <int> list;
stack <Node *> depthStack;
Node * cur = root;

while ( !depthStack.empty() || cur != NULL ) {
                if (cur != NULL) {
                         depthStack.push(cur);
                         cur = cur->left;
                                                     }
                else                             {
                         cur = depthStack.pop(); // Heres the line 
                         list.push_back(cur->key);
                         cur = cur->right;
                                                      }

                                                                                                                                            }
return list;

}

Answer 1

在C++中的功能

std::stack::pop()

不会返回从堆栈中删除的值.原因是从异常安全的角度来看,通常无法正确编写这样的函数.

您需要先存储该值,然后将其删除pop...例如

Node *x = depthStack.top();
depthStack.pop();