5.3.1_2 二叉树的层次遍历
- 👋 Hi, I’m @Beast Cheng
- 👀 I’m interested in photography, hiking, landscape…
- 🌱 I’m currently learning python, javascript, kotlin…
- 📫 How to reach me --> 458290771@qq.com
喜欢《数据结构》部分笔记的小伙伴可以订阅专栏，今后还会不断更新。🧑💻
此外，《程序员必备技能》专栏日后会逐步更新，感兴趣的小伙伴可以点一下订阅、收藏、关注！🚀
谢谢大家！🙏
![![[Pasted image 20240616161315.png]]](https://img-blog.csdnimg.cn/direct/7f90511cf51b4b42b72aa378f9ff3353.png)
算法思想：
- 初始化一个辅助队列
- 根结点入队
- 若队列非空，则头结点出队，访问该结点，并将其左、右孩子插入队尾（如果有的话）
- 重复第三步，直到队列为空
// 层序遍历
void LevelOrder(BiTree T){LinkQueue Q;InitQueue(Q); // 初始化辅助队列BiTree p;EnQueue(Q, T); // 根结点入队while(!isEmpty(Q)){ // 队列不空则循环DeQueue(Q, p); // 对头结点出队visit(p); // 访问出队结点if(p->lchild != NULL)EnQueue(Q, p->lchild); // 左孩子入队if(p->rchild != NULL)EnQueue(Q, p->rchild); // 右孩子入队}
}// 二叉树的结点（链式存储）
typedef struct BiTNode{char data;struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;// 链式队列结点
typedef struct LinkNode{BiTNode *data;struct LinkNode *next;
}LinkNode;typedef struct{LinkNode *front, *rear; // 队头队尾
}LinkQueue;