C++中序遍历非递归算法

在C++中，可以使用非递归算法来实现二叉树的中序遍历。下面是一个示例代码：

#include <iostream>
#include <stack>

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

void inorderTraversal(TreeNode* root) {
    std::stack<TreeNode*> stack;
    TreeNode* current = root;

    while (current != nullptr || !stack.empty()) {
        while (current != nullptr) {
            stack.push(current);
            current = current->left;
        }

        current = stack.top();
        stack.pop();
        std::cout << current->val << " ";

        current = current->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);

    // 中序遍历
    std::cout << "Inorder Traversal: ";
    inorderTraversal(root);
    std::cout << std::endl;

    // 释放内存
    delete root->left->right;
    delete root->left->left;
    delete root->right;
    delete root->left;
    delete root;

    return 0;
}

在这个示例中，我们使用了一个栈来模拟递归的过程。首先，我们将根节点入栈，然后沿着左子树一直向下遍历，将经过的节点都入栈。当当前节点为空时，说明已经到达了最左边的叶子节点，此时我们从栈中弹出一个节点并输出它的值。然后，将当前节点指向弹出节点的右子树，并继续遍历右子树的左子树。重复这个过程，直到栈为空且当前节点为空，遍历结束。

在示例代码中，我们创建了一个简单的二叉树，并对其进行中序遍历。输出结果为 "Inorder Traversal: 4 2 5 1 3"。最后，我们释放了动态分配的内存，以避免内存泄漏。