分别写出二叉树的先序遍历，中序遍历和后序遍历的非递归算法。（给出完整的C++代码）

在C++中，我们可以使用栈来实现非递归的二叉树遍历。以下是三种遍历方法的非递归算法示例：

先序遍历（根-左-右）
void preorderTraversal(Node* root) {
stack<Node*> s;
if (root != nullptr) {
s.push(root);
}
while (!s.empty()) {
Node* node = s.top();
cout << node->val << " ";
// 将当前节点的右子节点入栈
if (node->right != nullptr) {
s.push(node->right);
}
// 然后将左子节点入栈
if (node->left != nullptr) {
s.push(node->left);
}
// 弹出并访问当前节点
s.pop();
}
}
登录后复制

中序遍历（左-根-右）
void inorderTraversal(Node* root) {
stack<Node*> s;
Node* cur = root;
while (cur != nullptr || !s.empty()) {
// 当前节点还有未访问的左子节点时，将左子节点入栈
while (cur != nullptr) {
s.push(cur);
cur = cur->left;
}
// 从栈顶取出节点，访问它，然后移动到右子节点
cur = s.top();
s.pop();
cout << cur->val << " ";
cur = cur->right;
}
}
登录后复制

后序遍历（左-右-根）
void postorderTraversal(Node* root) {
stack<pair<Node*, bool>> s; // pair包含Node指针和是否已经访问过标志
if (root != nullptr) {
s.push({root, false});
}
while (!s.empty()) {
Node* node = s.top().first;
bool&amp; visited = s.top().second;
if (!visited) { // 如果还没访问，就访问它并将已访问标记设为true
cout << node->val << " ";
visited = true;
if (node->left != nullptr) {
s.push({node->left, false}); // 先处理左子树
} else {
s.pop(); // 左子树为空，移除节点并处理右子树
if (node->right != nullptr) {
s.push({node->right, false});
}
}
} else { // 如果已访问，就将它弹出栈
s.pop();
}
}
}
登录后复制