二叉树的层次遍历

经典例题

D - 数据结构实验之二叉树五：层序遍历

层次遍历介绍

先从上到下在从左到右的遍历一颗二叉树

屏幕截图(348)

具体算法思路

屏幕截图(349)

算法过程示意图

屏幕截图(350)

队列介绍

因为层次遍历需要队列 屏幕截图(351)

具体算法的伪代码

屏幕截图(352)

C++代码实现

队列使用STL

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cstring>
#include <unordered_set>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <sstream>
#include <queue>
#define int long long
#define yes cout<<"YES"<<'\n'
#define no 	cout<<"NO"<<'\n'

using namespace std;

typedef struct BiNode {
	char data;//数据域
	struct BiNode *lchild, *rchild; //左孩子右孩子
} BiNode, *BiTree;
/*
  前序建立二叉树
 */
void CreateBitree(BiTree &T) {
	char ch;
	cin >> ch;
	if (ch == '#') {
		T = NULL; //指针指向空
	} else

	{
		T = new BiNode; //建立一个新结点
		T->data = ch; //给新结点赋值
		CreateBitree(T->lchild);//创建左孩子
		CreateBitree(T->rchild);//创建右孩子
	}


}

/*
  二叉树的层次遍历算法
 */
void LevelOrder(BiTree T) {
	queue <BiTree> q;//生成一个队列
	q.push(T);//根结点入队
	while (!q.empty()) {//队列不为空就循环
		BiTree p = q.front(); //取出队头
		cout << p->data; //打印队尾指针指向的结点的数据域
		q.pop();//元素出队
		if (p->lchild != NULL) { //左孩子入队
			q.push(p->lchild);
		}
		if (p->rchild != NULL) { //右孩子入队
			q.push(p->rchild);
		}
	}



}

signed main () {
	BiTree root = NULL;
	CreateBitree(root);
	cout << "正在进行层次遍历\n";
	LevelOrder(root);

	cout << '\n';




	return 0;
}
/*
  abd##eg###cf###
  abcdefg
 */
/*
  xnl##i##u##
  xnuli
 */