[数据结构]二叉树的层序遍历

一、二叉树的层序遍历

设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

层序遍历比较特别,需要用到前面学过的队列知识.

[数据结构]队列-CSDN博客

我先来说一下我们的思路:

我们是这样完成的:

1.我们先创建一个队列:

2.然后让1入队列:

3.接着把1的左右子树入队列:

4.因为1的左右子树已经入队列了,此时打印1然后让1出队列:

5.然后让2(也就是一的左子树)的左右子树入队列:

6.因为2的左右子树已经入队列了,此时打印2然后让2出队列:

7.然后让3的左右子树入队列:

8.然后让3出队列:

9.后面子树为空就不入队列,依次打印元素,,在打印完最后一个元素时(这里是7),销毁队列.

接下来我们来完成这个思路,下面是代码实现:

1.我们先写一个二叉树的接口:

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

2.写一个队列的接口,以及相关操作:

typedef struct QueueNode {
    TreeNode* treenode;
    struct QueueNode* next;
} QueueNode;

typedef struct Queue {
    QueueNode* front;
    QueueNode* rear;
} Queue;

void initQueue(Queue* q) {
    q->front = q->rear = NULL;
}

int isEmpty(Queue* q) {
    return q->front == NULL;
}

void enqueue(Queue* q, TreeNode* treenode) {
    QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
    newNode->treenode = treenode;
    newNode->next = NULL;
    if (isEmpty(q)) {
        q->front = q->rear = newNode;
    }
    else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
}

3.二叉树节点出队列:

TreeNode* dequeue(Queue* q) {
    if (isEmpty(q)) return NULL;
    QueueNode* temp = q->front;
    TreeNode* treenode = temp->treenode;
    q->front = q->front->next;
    if (q->front == NULL) {
        q->rear = NULL;
    }
    free(temp);
    return treenode;
}

4.层序遍历:

void levelOrderTraversal(TreeNode* root) {
    if (root == NULL) return;
    Queue q;
    initQueue(&q);
    enqueue(&q, root);
    while (!isEmpty(&q)) {
        TreeNode* current = dequeue(&q);
        printf("%d ", current->val);
        if (current->left != NULL) {
            enqueue(&q, current->left);
        }
        if (current->right != NULL) {
            enqueue(&q, current->right);
        }
    }
}

下面我们来简单的测试一下:

我们写一个简单的主函数,然后运行一下:

int main() {
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->val = 1;
    root->left = (TreeNode*)malloc(sizeof(TreeNode));
    root->left->val = 2;
    root->left->left = (TreeNode*)malloc(sizeof(TreeNode));
    root->left->right = (TreeNode*)malloc(sizeof(TreeNode));
    root->right = (TreeNode*)malloc(sizeof(TreeNode));
    root->right->val = 3;
    root->right->left = (TreeNode*)malloc(sizeof(TreeNode));
    root->right->right = (TreeNode*)malloc(sizeof(TreeNode));
    root->left->left->val = 4;
    root->left->left->left = NULL;
    root->left->left->right = NULL;
    root->left->right->val = 5;
    root->left->right->left = NULL;
    root->left->right->right = NULL;
    root->right->left->val = 6;
    root->right->left->left = NULL;
    root->right->left->right = NULL;
    root->right->right->val = 7;
    root->right->right->left = NULL;
    root->right->right->right = NULL;
    levelOrderTraversal(root);

    return 0;
}

我们把上面的二叉树数据写入,如果是层序遍历,结果应该就是:1 2 3 4 5 6 7

运行结果:

结果正确.

大家也可结合上回的前序遍历来把数据写入二叉树，使这段代码更加有意思。本篇的内容到此就结束了，感谢阅读。