c语言二叉树的层次遍历（超详细）学习笔记

 前言：

我学习数据结构的方式是看书加看视频，视频看的是哔哩哔哩up主的 二叉树的层次遍历 我总结并补充他所讲的内容，他的视频适合有c语言基础的看。本文章继我的上一篇文章  c语言二叉树的创建与前序、中序、后序遍历（超详细）学习笔记 ,在二叉树的前序、中序、后序的三种遍历上，继续详细解释二叉树的层次遍历。看完此片文章，一定会有所收获的！

思路：

若想实现层次遍历，那么应该是先遍历根节点A，然后遍历它的左子树B，再遍历它的右子树C，再遍历B的左子树，再遍历B的右子树...

按照这个逻辑关系，我们可以运用树+队的形式，树的结点作为队的元素。

每次入队一个树结点，进行遍历，出队，然后再在将这个树结点的左孩子和右孩子进行入队,依次进行...最终得到层次遍历：A B C D E F G

一、创建树结构体

//创建树结构体typedef struct TreeNode{    char data;    struct TreeNode* lChild;    struct TreeNode* rChild;}treeNode;

二、创建循环队列结构体（链式存储方式）

循环队列的解释：

队的特点是先进先出，循环队列适应两种存储结构，顺序存储有队满情况，链式存储不存在队满情况。因为是链式存储方式，所以不能通过顺序存储中的real和front来判断队空，通过链式结构中的指针域来联系队中的元素彼此。

那么就有两种循环方式：单循环队列和双循环队列方式。所以我会展示两种方式。当然两种方法各有所爱了，总体上是差不多的。

（1）创建单循环队列

//创建循环队列结构体typedef struct QueueNode{    treeNode* data;树的结点作为元素    struct QueueNode* next;}QueueNode;

（2）创建双循环队列

//创建双循环队列结构体typedef struct QueueNode{    treeNode* data; //树的结点作为元素    struct QueueNode* next;    struct QueueNode* pre;}QueueNode;

三、初始化二叉树

仍是使用先序方式进行传入数据 并运用递归。如果想了解递归详细的推导，可以看看我的这篇文章 c语言二叉树的创建与前序、中序、后序遍历（超详细）学习笔记

//初始化二叉树TreeNode* creatTree(){    TreeNode* T;    char ch;    scanf_s("%c", &ch);//通过输入的ch是否是‘#’来判断该节点是否有孩子节点    if (ch == '#') //'#'代表传入的是空结点    {        //此时为空结点        return NULL;    }    else    {        //不为空        T = (TreeNode*)malloc(sizeof(TreeNode));        T->data = ch;        //创建左子树，逻辑一致，进行递归        T->lChild = creatTree();        //创建右子树，逻辑一致，进行递归        T->rChild = creatTree();        return T;    }}

四、创建空队

（1）单循环队列：

//创建空队QueueNode* initQueue(){    QueueNode* Q = (QueueNode*)malloc(sizeof(QueueNode));    Q->data = NULL;    Q->next = Q;    return Q;}

（2）双循环队列：

//创建空队QueueNode* initQueue(){    QueueNode* Q = (QueueNode*)malloc(sizeof(QueueNode));    Q->data = NULL;    Q->next = Q;    Q->pre = Q;    return Q;}

五、入队  （尾插法入队）

尾插法入队的解释：先进先出，方便出队时快速找到当前元素，Q->next == 出队的元素 

如：按照1，2，3，4，5的顺序入队，那么出队的顺序为1，2，3，4，5

头插法入队：Q->1->2->3->4->5，若想出队1，需找到元素1 即：Q->nest == 1，非常快速。

（1）单循环队列：

//入队  尾插法void enQueue(QueueNode* Q, treeNode* data){    QueueNode* node = (QueueNode*)malloc(sizeof(QueueNode));    QueueNode* q = Q->next;    while(q->next != Q)    {         q = q->next;    }    node->data = data;    q->next = node;    node->next = Q;    }

（2）双循环队列：

//入队  尾插法void enQueue(QueueNode* Q, treeNode* data){    QueueNode* node = (QueueNode*)malloc(sizeof(QueueNode));    node->data = data;    node->pre = Q->pre;    node->next = Q;    Q->pre->next = node;    Q->pre = node;}

六、判断队是否为空

//判断队是否为空int isEmpty(QueueNode* Q){    if (Q->next == Q)    {        return 1;    }    else    {        return 0;    }}

七、出队  （头插法出队）

头插法出队，非常快速的找到需要出队的元素，Q->next == 出队的元素

找到出队元素，进行出队操作并返回其元素。

（1）单循环队列：

//出队  头插法treeNode* deQueue(QueueNode* Q){    if (isEmpty(Q))    {        return NULL;    }    else    {        QueueNode* node = Q->next;        treeNode* T = node->data;        Q->next = node->next;        free(node);        return T;    }}

（2）双循环队列：

//出队  头插法treeNode* deQueue(QueueNode* Q){    if (isEmpty(Q))    {        return NULL;    }    else    {        QueueNode* node = Q->next;        treeNode* T = node->data;        Q->next = node->next;        node->next->pre = Q;        free(node);        return T;    }}

八、层次遍历

//层次遍历void levelTraverse(QueueNode* Q, treeNode* T){    //先进队    enQueue(Q, T);    while (!isEmpty(Q))    {        treeNode* node = deQueue(Q);        //将node 进行遍历        printf("%c ", node->data);        //如果有左孩子        if (node->lChild)        {            enQueue(Q, node->lChild);        }        //如果有右孩子        if (node->rChild)        {            enQueue(Q, node->rChild);        }    }}

思路：每次入队一个树结点，出队并取出其元素，进行遍历，然后再在将这个树结点的左孩子和右孩子进行入队,依次进行...最终得到层次遍历：A B C D E F G

九、前序遍历

//前序遍历   根 左 右void preOrder(treeNode* T){    if (T == NULL)    {        return;    }    else    {       //先办事        printf("%c ", T->data);        //左孩子                                            preOrder(T->lChild);        //右孩子                                            preOrder(T->rChild);    }}

十、完整代码

(1)单循环队列完整代码：

#include#include//创建树结构体typedef struct TreeNode{    char data;    struct TreeNode* lChild;    struct TreeNode* rChild;}treeNode;//创建循环队列结构体typedef struct QueueNode{    treeNode* data;树的结点作为元素    struct QueueNode* next;}QueueNode;//初始化二叉树TreeNode* creatTree(){    TreeNode* T;    char ch;    scanf_s("%c", &ch);//通过输入的ch是否是‘#’来判断该节点是否有孩子节点    if (ch == '#') //'#'代表传入的是空结点    {        //此时为空结点        return NULL;    }    else    {        //不为空        T = (TreeNode*)malloc(sizeof(TreeNode));        T->data = ch;        //创建左子树，逻辑一致，进行递归        T->lChild = creatTree();        //创建右子树，逻辑一致，进行递归        T->rChild = creatTree();        return T;    }}//创建空队QueueNode* initQueue(){    QueueNode* Q = (QueueNode*)malloc(sizeof(QueueNode));    Q->data = NULL;    Q->next = Q;    return Q;}//入队  尾插法void enQueue(QueueNode* Q, treeNode* data){    QueueNode* node = (QueueNode*)malloc(sizeof(QueueNode));    QueueNode* q = Q->next;    while(q->next != Q)    {         q = q->next;    }    node->data = data;    q->next = node;    node->next = Q;    }//判断队是否为空int isEmpty(QueueNode* Q){    if (Q->next == Q)    {        return 1;    }    else    {        return 0;    }}//出队  头插法treeNode* deQueue(QueueNode* Q){    if (isEmpty(Q))    {        return NULL;    }    else    {        QueueNode* node = Q->next;        treeNode* T = node->data;        Q->next = node->next;        free(node);        return T;    }}//层次遍历void levelTraverse(QueueNode* Q, treeNode* T){    //先进队    enQueue(Q, T);    while (!isEmpty(Q))    {        treeNode* node = deQueue(Q);        //将node 进行打印        printf("%c ", node->data);        //如果有左孩子        if (node->lChild)        {            enQueue(Q, node->lChild);        }        //如果有右孩子        if (node->rChild)        {            enQueue(Q, node->rChild);        }    }}//前序遍历   根 左 右void preOrder(treeNode* T){    if (T == NULL)    {        return;    }    else    {       //先办事        printf("%c ", T->data);        //左孩子                                            preOrder(T->lChild);        //右孩子                                            preOrder(T->rChild);    }}int main(){    QueueNode* Q = initQueue();    treeNode* T = creatTree();    printf("前序遍历：\n");    preOrder(T);    printf("\n");    printf("层次遍历：\n");    levelTraverse(Q, T);    printf("\n");    return 0;}

(2)双循环队列完整代码：

#include#include//创建树结构体typedef struct TreeNode{    char data;    struct TreeNode* lChild;    struct TreeNode* rChild;}treeNode;//创建双循环队列结构体typedef struct QueueNode{    treeNode* data; //树的结点作为元素    struct QueueNode* next;    struct QueueNode* pre;}QueueNode;//初始化二叉树TreeNode* creatTree(){    TreeNode* T;    char ch;    scanf_s("%c", &ch);//通过输入的ch是否是‘#’来判断该节点是否有孩子节点    if (ch == '#') //'#'代表传入的是空结点    {        //此时为空结点        return NULL;    }    else    {        //不为空        T = (TreeNode*)malloc(sizeof(TreeNode));        T->data = ch;        //创建左子树，逻辑一致，进行递归        T->lChild = creatTree();        //创建右子树，逻辑一致，进行递归        T->rChild = creatTree();        return T;    }}//创建空队QueueNode* initQueue(){    QueueNode* Q = (QueueNode*)malloc(sizeof(QueueNode));    Q->data = NULL;    Q->next = Q;    Q->pre = Q;    return Q;}//入队  尾插法void enQueue(QueueNode* Q, treeNode* data){    QueueNode* node = (QueueNode*)malloc(sizeof(QueueNode));    node->data = data;    node->pre = Q->pre;    node->next = Q;    Q->pre->next = node;    Q->pre = node;}//判断队是否为空int isEmpty(QueueNode* Q){    if (Q->next == Q)    {        return 1;    }    else    {        return 0;    }}//出队  头插法treeNode* deQueue(QueueNode* Q){    if (isEmpty(Q))    {        return NULL;    }    else    {        QueueNode* node = Q->next;        treeNode* T = node->data;        Q->next = node->next;        node->next->pre = Q;        free(node);        return T;    }}//层次遍历void levelTraverse(QueueNode* Q, treeNode* T){    //先进队    enQueue(Q, T);    while (!isEmpty(Q))    {        treeNode* node = deQueue(Q);        //将node 进行遍历        printf("%c ", node->data);        //如果有左孩子        if (node->lChild)        {            enQueue(Q, node->lChild);        }        //如果有右孩子        if (node->rChild)        {            enQueue(Q, node->rChild);        }    }}//前序遍历   根 左 右void preOrder(treeNode* T){    if (T == NULL)    {        return;    }    else    {       //先办事        printf("%c ", T->data);        //左孩子                                            preOrder(T->lChild);        //右孩子                                            preOrder(T->rChild);    }}int main(){    int index = 0;    QueueNode* Q = initQueue();    treeNode* T = creatTree();    printf("前序遍历：");    preOrder(T);    printf("\n");    printf("层次遍历：");    levelTraverse(Q, T);    printf("\n");    return 0;}

十一、运行结果

输入：ABD##E##CF##G##

​

总结：

二叉树层次遍历的好处包括：

1.按照层级顺序访问节点：层次遍历可以按照树的层级顺序访问节点，从根节点开始，逐层向下遍历，这样可以更加直观地观察和理解整个二叉树的结构。

2.方便实现广度优先搜索：层次遍历是广度优先搜索（BFS）的一种实现方式。BFS是一种重要的图搜索算法，广泛应用于图的遍历、路径搜索、连通性判断等问题中。层次遍历的结果正好可以按照广度优先搜索的顺序得到。

3.快速查找某一层的节点：对于二叉树层次遍历的结果，每一层的节点都是按照从左到右的顺序排列的。因此，可以直接通过索引或下标的方式快速查找到某一层的节点。这种特性在某些问题中非常有用，比如在二叉树的每一层中查找特定的节点或值。

4.方便处理与层次相关的问题：有些问题与二叉树的层次相关，比如计算二叉树的最大深度、最小深度，判断二叉树是否是完全二叉树等等。通过层次遍历，可以轻松地处理与层次相关的问题，因为遍历的结果已经按照层级顺序排列好了。

总之，二叉树层次遍历可以提供对二叉树结构的直观理解，方便实现广度优先搜索，快速查找某一层的节点，并处理与层次相关的问题。

实现二叉树的层次遍历需要树+队的结合，队是循环队列，那么有单循环队列和双循环队列两种方式进行实现。制作不易，真心想让你懂，还是有不足的地方，望见谅嘞。