二叉树的层次遍历（c++）_102. 二叉树的层次遍历(c++)

层次遍历 ：对于一颗二叉树，从根结点开始，按从上到下，从左到右的顺序访问每一个结点

思路

使用队列
1，将根结点入队
2，队不为空时循环：出列一个结点，打印它
①有左孩子，将左孩子入队
②有右孩子，将右孩子入队

#include<iostream>
#include<queue>
using namespace std;
typedef struct TriTNode{
	struct TriTNode *lchild;
	struct TriTNode *rchild;
	char Node;
}BiTNode,*BiTree; 
void levelOrder(BiTNode *root)
{
	BiTNode *p=root;
	queue<BiTNode*> qu;//初始化队列 
	qu.push(p);//根结点入队
	while(!qu.empty())//队非空循环 
	{
		p=qu.front();//出队，队内第一个元素
		qu.pop();//首元素出队 
		cout<<p->Node;//打印
		if(p->lchild!=NULL) qu.push(p->lchild);//左孩子入队
		if(p->rchild!=NULL) qu.push(p->rchild);//右孩子入队
	 } 
 }
void CreateBiTree(BiTree &T)
{
	char ch;
	cin>>ch;
	if(ch=='#') T=NULL;
	else{
		T=new BiTNode;
		T->Node=ch;
		CreateBiTree(T->lchild);
		CreateBiTree(T->rchild);
	}	
 } 
int main()
{
	BiTree T;
	cout<<"请输入"<< endl; 
 	CreateBiTree(T);
 	cout << "二叉树创建完成！"<<endl;
 	cout<<"二叉树层次遍历为"<<endl;
 	levelOrder(T); 
	return 0;
} 
//例：abc##de###fg#h### ->abfcdgeh

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46