c++ - BST：应忽略的无效值

Question

我试图在 C++ 中实现一个 BST。这是一个特定的成员函数，用于执行顺序遍历并返回一个带有树元素的向量。现在问题出现在我设置为当前节点的堆栈 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();

Answer 2

在 C++ 中，stack.pop() 函数不会从堆栈中返回值。

所以，首先你存储值然后你弹出它。在你的情况下：

---

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.top();   //solution
                                 depthStack.pop();                             
                         list.push_back(cur->key);
                         cur = cur->right;
                                                      }

                                                                                                                                            }
return list;

}