非递归中序遍历二叉树代码

非递归中序遍历二叉树通常使用栈数据结构来辅助完成。其基本思路是先将左子树的所有节点压入栈中，然后访问当前节点（根节点），接着访问右子树。以下是使用Python实现的一个示例：

def inorder_traversal(root):
    stack = []
    current = root

    while True:
        # 当前节点为空或者还有未处理的左子节点时
        while current:
            stack.append(current)
            current = current.left

        # 如果栈不为空并且顶部元素为右子节点，则弹出并访问
        if not stack:
            return
        current = stack.pop()
        print(current.value)  # 替换成实际的数据访问操作

        # 将焦点移动到弹出节点的右子树
        current = current.right

在这个代码中，我们不断从左子树将节点压入栈，直到遇到空节点。然后，我们依次取出栈顶的节点并访问，再将焦点切换到右子树，直到栈为空为止。

相关问题

二叉树的非递归中序遍历代码

以下是二叉树的非递归中序遍历代码：

vector<int> inorderTraversal(TreeNode* root) {
    stack<TreeNode*> st;
    vector<int> res;
    TreeNode* cur = root;
    while (cur || !st.empty()) {
        while (cur) {
            st.push(cur);
            cur = cur->left;
        }
        cur = st.top();
        st.pop();
        res.push_back(cur->val);
        cur = cur->right;
    }
    return res;
}

该代码使用了栈来模拟递归过程，具体实现如下：

1. 初始化栈和结果数组，将当前节点指向根节点。

2. 当前节点不为空或栈不为空时，执行以下操作：

a. 当前节点不为空时，将当前节点入栈，并将当前节点指向其左子节点，直到当前节点为空。

b. 当前节点为空时，从栈中弹出一个节点，将其值加入结果数组中，并将当前节点指向该节点的右子节点。

3. 返回结果数组。

先序非递归遍历算法遍历二叉树 ​中序非递归遍历算法遍历二叉树 ​后序非递归遍历算法遍历二叉树 ​层序遍历二叉树

好的，我可以给您介绍一下二叉树的四种非递归遍历算法以及层序遍历。

先序非递归遍历算法：
1. 新建一个栈，将根节点入栈。
2. 当栈不为空时，取出栈顶元素并访问它。
3. 将当前节点的右子节点（如果存在）入栈，再将左子节点（如果存在）入栈。
4. 重复步骤2-3，直到栈为空。

中序非递归遍历算法：
1. 新建一个栈，将根节点入栈。
2. 如果当前节点不为空，则将当前节点的左子节点全部入栈，并将当前节点置为左子节点。
3. 如果当前节点为空，则取出栈顶元素并访问它，将当前节点置为它的右子节点。
4. 重复步骤2-3，直到栈为空。

后序非递归遍历算法：
1. 新建两个栈：s1和s2，将根节点入s1。
2. 当s1不为空时，取出栈顶元素并将其压入s2中。
3. 将当前节点的左子节点（如果存在）入s1，再将右子节点（如果存在）入s1。
4. 重复步骤2-3，直到s1为空。
5. 依次访问s2中的元素即可得到后序遍历结果。

层序遍历算法：
1. 新建一个队列，将根节点入队。
2. 当队列不为空时，取出队首元素并访问它。
3. 将当前节点的左子节点（如果存在）入队，再将右子节点（如果存在）入队。
4. 重复步骤2-3，直到队列为空。