建立二叉树，层序、先序、中序、后序遍历

二叉树是一种树形结构，每个节点最多有两个子节点。常用的遍历方式有层序遍历、先序遍历、中序遍历和后序遍历。

层序遍历是按照树的层次顺序遍历每个节点，从根节点开始，先遍历左子树，再遍历右子树。先序遍历是先遍历根节点，再遍历左子树，最后遍历右子树。中序遍历是先遍历左子树，再遍历根节点，最后遍历右子树。后序遍历是先遍历左子树，再遍历右子树，最后遍历根节点。

建立二叉树的方法有很多种，常用的有递归和非递归两种。递归建树是指在每个节点处递归地创建左子树和右子树，直到遇到空节点为止。非递归建树是指使用队列来存储节点，从根节点开始，依次读取每个节点的左右子节点，将其加入队列中，直到队列为空为止。

相关问题

二叉树的层序遍历先序遍历中序遍历后序遍历

在二叉树的遍历中，有三种主要的方式：先序遍历（Pre-order traversal）、中序遍历（In-order traversal）和后序遍历（Post-order traversal），每种遍历顺序都会按照不同的方式访问节点。

1. **先序遍历** (Pre-order):
- 首先访问根节点，然后递归地遍历左子树，最后遍历右子树。
- 格式：根 -> 左 -> 右

2. **中序遍历** (In-order):
- 首先递归地遍历左子树，然后访问根节点，最后遍历右子树。
- 格式：左 -> 根 -> 右

3. **后序遍历** (Post-order):
- 首先递归地遍历左子树和右子树，最后访问根节点。
- 格式：左 -> 右 -> 根

对于层序遍历（Level-order traversal），也称为广度优先遍历（Breadth-First Search, BFS），它按照从上到下、从左到右的顺序逐层访问每个节点，通常使用队列数据结构来实现：

- 重复此过程，直到队列为空。

**相关问题--:**
1. 除了以上提到的遍历方式，还有哪些常见的二叉树遍历？
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); // 打印当前节点值
    }
}