【c-数据结构】二叉树的层序遍历

层序遍历二叉树的层序遍历也被称为广度优先遍历BFS是一种按层次访问树中所有节点的算法。它从根节点开始一层一层地向下遍历每一层都从左到右依次访问节点。与前序、中序、后序遍历这些属于深度优先遍历DFS不同层序遍历关注的是树的“层次”结构。深度优先遍历 (DFS)会沿着一条分支一直深入到叶子节点然后再回溯访问其他分支。层序遍历 (BFS)像剥洋葱一样先完整地访问完当前层的所有节点再进入下一层。一、实现方式使用队列实现源于队列先进先出的特性借助队列的先进先出特性将每一层的节点依次入队并处理1、初始化一个队列将根节点入队。2、循环直到队列为空出队当前节点并访问。3、将当前节点的左子节点和右子节点如果存在依次入队。二、层序遍历的实现因为在实现层序遍历需要用到队列因此需要定义队列的机构体以及相关功能的实现。为了方便查找以及观察我建设了队列的头文件声明、队列功能实现、二叉树的头文件声明、层序遍历功能实现、测试文件。1、队列的头文件声明在该处定义了队列的结构体以及相关功能声明#pragma once #includestdio.h #includestdlib.h #includeassert.h #includestdbool.h #includebinarytreenode.h typedef struct binarytreenode* datatype; typedef struct queuenode { datatype val; struct queuenode* next; }QN; typedef struct queue { QN* phead; int size; QN* ptail; }Q; //初始化 void Qinit(Q* pq); //销毁 void Qdestroy(Q* pq); //队尾插 void Qpush(Q* pq, datatype x); //队头删 void Qpop(Q* pq); //取队头数据 datatype Qfront(Q* pq); //取队尾数据 datatype Qback(Q* pq); //判空 bool Qempty(Q* pq); //队列数据个数 int Qsize(Q* pq);2、队列功能实现在该处主要是相关功能的实现#define _CRT_SECURE_NO_WARNINGS #includequeue.h //初始化 void Qinit(Q* pq) { assert(pq); pq-phead pq-ptail NULL; pq-size 0; } //销毁 void Qdestroy(Q* pq) { assert(pq); QN* pcur pq-phead; while (pcur) { QN* next pcur-next; free(pcur); pcur next; } pq-phead pq-ptail NULL; } //队尾插 void Qpush(Q* pq, datatype x) { assert(pq); QN* newnode (QN*)malloc(sizeof(QN)); if (newnode NULL) { perror(malloc fail!); return; } newnode-next NULL; newnode-val x; if (pq-ptail NULL) { pq-phead pq-ptail newnode; } else { pq-ptail-next newnode; pq-ptail newnode; } pq-size; } //队头删 void Qpop(Q* pq) { assert(pq); assert(pq-size); if (pq-phead-next NULL) { free(pq-phead); pq-phead pq-ptail NULL; } else { QN* next pq-phead-next; free(pq-phead); pq-phead next; } pq-size--; } //取队头数据 datatype Qfront(Q* pq) { assert(pq); assert(pq-phead); return pq-phead-val; } ////取队尾数据 //datatype Qback(Q* pq) //{ // assert(pq); // assert(pq-ptail); // return pq-ptail-val; //} //判空 bool Qempty(Q* pq) { assert(pq); return pq-size 0; } ////队列数据个数 //int Qsize(Q* pq) //{ // assert(pq); // return pq-size; //}因为队列的实现我在前几章已完成再此不多解释3、二叉树的头文件声明在这里实现二叉树结构体的定义以及层序遍历的声明#pragma once #includestdio.h #includestdlib.h #includeassert.h #includestdbool.h typedef int datatype; typedef struct binarytreenode { datatype val; struct binarytreenode* left; struct binarytreenode* right; }BTN; //前序遍历 void preverorder(BTN* root);4、层序遍历功能实现//层序遍历 //其需要用到队列 void treelevelorder(BTN* root) { //先建立一个队列 Q q; Qinit(q); if (root) { Qpush(q, root); } while (!Qempty(q)) { BTN* front Qfront(q); Qpop(q); printf(%d, front-val); if (front-left) { Qpush(q, front-left); } if (front-right) { Qpush(q, front-right); } } Qdestroy(q); }5、测试文件与前中后序测试一样在这就不一一测试了三、层序遍历判断二叉树是否是完全二叉树层序遍历到底有什么用是的判断完全二叉树。原理就是在二叉树层序遍历中当遇到空时就开始判断如果后继又出现了空则为非完全二叉树。具体实现//判断是否是完全二叉树 bool treecomplete(BTN* root) { //先建立一个队列 Q q; Qinit(q); if (root) { Qpush(q, root); } while (!Qempty(q)) { BTN* front Qfront(q); Qpop(q); if (front) { break; } Qpush(q, front-left); Qpush(q, front-right); while (!Qempty(q)) { BTN* front Qfront(q); Qpop(q); } if (front) { Qdestroy(q); return false; } } Qdestroy(q); return true; }四、其他的一些常见应用场景按层处理需要对树的每一层进行特定操作如按层打印树结构。计算树高遍历的层数即为树的高度。寻找最短路径在无权图中BFS能找到从起点到终点的最短路径。序列化与反序列化将树结构转换为数组或字符串便于存储和传输。检查对称性判断一棵树是否为镜像对称。