中序遍历非递归实现 迭代

中序遍历非递归实现

跟大家分享中序遍历非递归实现的话题，接下来分享详细内容。

思路：

1. 从根节点开始，一直访问左子树，同时将经过的节点入栈。
2. 当左子树访问完毕（为空）时，弹出栈顶元素，访问该节点，并转向其右子树，然后重复步骤1。
3. 直到栈为空且当前节点为空时，遍历结束。

参考代码：

#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*> nodeStack;
    TreeNode* current = root;
    while (current != nullptr || !nodeStack.empty()) {
        // 将左子树入栈
        while (current != nullptr) {
            nodeStack.push(current);
            current = current->left;
        }
        // 访问节点并转向右子树
        current = nodeStack.top();
        nodeStack.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);
    return 0;
}

本文分享的中序遍历非递归实现 迭代的详细讲解，仅供大家参考建议！