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

喜欢《数据结构》部分笔记的小伙伴可以订阅专栏，今后还会不断更新。🧑‍💻
此外，《程序员必备技能》专栏日后会逐步更新，感兴趣的小伙伴可以点一下订阅、收藏、关注！🚀
谢谢大家！🙏

算法思想：

1. 初始化一个辅助队列
2. 根结点入队
3. 若队列非空，则头结点出队，访问该结点，并将其左、右孩子插入队尾（如果有的话）
4. 重复第三步，直到队列为空

// 层序遍历
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;