迭代方式实现中序遍历的非递归算法

思路：

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;
}

转载请注明：汇站网 » 迭代方式实现中序遍历的非递归算法