二叉树的先序,中序,后序遍历 非递归

可以使用栈来实现二叉树的先序、中序和后序遍历非递归算法。具体实现方法如下：

1. 先序遍历非递归算法：
先访问根节点，再访问左子树和右子树。具体实现如下：
(1) 创建一个空栈，将根节点压入栈中；
(2) 循环执行下列步骤，直到栈为空：
a. 弹出栈顶元素，访问它；
b. 如果有右孩子，将右孩子压入栈中；
c. 如果有左孩子，将左孩子压入栈中。

2. 中序遍历非递归算法：
先访问左子树，再访问根节点和右子树。具体实现如下：
(1) 创建一个空栈，将根节点压入栈中；
(2) 循环执行下列步骤，直到栈为空：
a. 如果栈顶元素存在左孩子，将左孩子压入栈中；
b. 否则，弹出栈顶元素，访问它；
c. 如果栈顶元素存在右孩子，将右孩子压入栈中。

3. 后序遍历非递归算法：
先访问左子树和右子树，再访问根节点。具体实现如下：
(1) 创建两个栈：s1和s2，将根节点压入s1中；
(2) 循环执行下列步骤，直到s1为空：
a. 弹出s1栈顶元素，将它压入s2中；
b. 如果s1栈顶元素存在左孩子，将左孩子压入s1中；
c. 如果s1栈顶元素存在右孩子，将右孩子压入s1中。
(3) 循环执行下列步骤，直到s2为空：
a. 弹出s2栈顶元素，访问它。

希望以上算法实现对你有所帮助！

相关问题

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

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

先序非递归遍历算法：
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，直到队列为空。

二叉树的层序遍历先序遍历中序遍历后序遍历非递归算法代码

当然，二叉树的遍历有三种主要方式：先序遍历（根-左-右）、中序遍历（左-根-右）和后序遍历（左-右-根）。非递归的层次遍历（也叫广度优先遍历，从上到下、从左到右）通常使用队列来辅助实现。

这里分别给出这些遍历的非递归算法代码：

1. 层序遍历（广度优先遍历）：

#include <stdio.h>
#include <stdlib.h>
#include <queue>

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

void levelOrder(struct TreeNode* root) {
    if (root == NULL) return;

    // 使用队列存储每一层的节点
    queue<struct TreeNode*> q;
    q.push(root);

    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            struct TreeNode* node = q.front();
            q.pop();
            printf("%d ", node->val); // 打印当前节点值

            if (node->left != NULL) q.push(node->left);
            if (node->right != NULL) q.push(node->right);
        }
        printf("\n"); // 换行表示新的一层
    }
}

2. 先序遍历（递归和非递归两种方式，这里是非递归版本，使用栈）：

void preorderNonRecursive(struct TreeNode* root) {
    if (root == NULL) return;

    stack<struct TreeNode*> s;
    s.push(root);

    while (!s.empty()) {
        struct TreeNode* node = s.top();
        s.pop();
        printf("%d ", node->val); // 打印当前节点值

        if (node->right != NULL) s.push(node->right);
        if (node->left != NULL) s.push(node->left);
    }
}

3. 中序遍历（非递归，同样使用栈）：

void inorderNonRecursive(struct TreeNode* root) {
    if (root == NULL) return;

    stack<struct TreeNode*> s;
    struct TreeNode* curr = root;

    while (curr != NULL || !s.empty()) {
        while (curr != NULL) {
            s.push(curr);
            curr = curr->left;
        }
        curr = s.top();
        s.pop();
        printf("%d ", curr->val); // 打印当前节点值
        curr = curr->right;
    }
}

4. 后序遍历（非递归，使用两个栈）：

void postorderNonRecursive(struct TreeNode* root) {
    if (root == NULL) return;

    stack<struct TreeNode*> s1, s2;
    s1.push(root);

    while (!s1.empty()) {
        struct TreeNode* node = s1.top();
        s1.pop();

        s2.push(node);
        if (node->left != NULL) s1.push(node->left);
        if (node->right != NULL) s1.push(node->right);
    }

    while (!s2.empty()) {
        struct TreeNode* node = s2.top();
        s2.pop();
        printf("%d ", node->val); // 打印当前节点值
    }
}