C++中序遍历非递归

C++中的二叉树序遍历有三种方式：前序遍历、中序遍历和后序遍历。下面我将介绍一下C++中的中序遍历非递归实现方法。

中序遍历的非递归实现可以使用栈来辅助完成。具体步骤如下：

1. 创建一个空栈，用于存储待访问的节点。
2. 初始化当前节点为根节点。
3. 当当前节点不为空或者栈不为空时，执行以下操作：
- 若当前节点不为空，则将当前节点入栈，并将当前节点更新为其左子节点。
- 若当前节点为空，则从栈中弹出一个节点并访问它，然后将当前节点更新为其右子节点。
4. 重复步骤3，直到当前节点为空且栈为空。

下面是C++中实现中序遍历非递归的示例代码：

#include <iostream>
#include <stack>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

void inorderTraversal(TreeNode* root) {
    stack<TreeNode*> s;
    TreeNode* curr = root;

    while (curr != NULL || !s.empty()) {
        while (curr != NULL) {
            s.push(curr);
            curr = curr->left;
        }

        curr = s.top();
        s.pop();
        cout << curr->val << " ";

        curr = curr->right;
    }
}

int main() {
    // 构造一个二叉树
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    cout << "中序遍历结果：";
    inorderTraversal(root);

    return 0;
}

运行以上代码，将输出中序遍历的结果。