数据结构第12讲 二叉树的层次遍历
数据结构第12讲 二叉树的层次遍历
二叉树的遍历一般有先序遍历、中序遍历和后序遍历，这三种遍历比较简单。今天我们讲二叉树的另一种遍历方式，层次遍历。即按照层次进行遍历。如图1所示：
图1二叉树
对图1的二叉树，进行层次遍历：首先搜索第1层A，然后搜索第2层，从左向右B、C，再搜索第3层，从左向右D、E、F，再搜索第4层G，很简单吧，这就是层次遍历。
程序是怎么实现层次遍历呢？用队列噢，很多同学觉得数据结构没什么用，其实数据结构就像我们小学时学的九九乘法表，你有时根本感觉不到它的存在，但却无时不刻都在用！
首先创建一个队列Q：
1.令树根入队，如图2所示。（注意：实际上是指向树根A的指针入队，这里为了图解方便，把数据入队了）
图2层次遍历队列1
（注意：实际上是指向树根A的指针入队，这里为了图解方便，把数据入队了）
2.队头元素出队，输出A，同时令A的孩子(从左向右顺序，如果是普通树，则包含所有孩子)入队。如图3、4所示。
图3 层次遍历队列2
图4二叉树层次遍历过程1
3.队头元素出队，输出B，同时令B的孩子D、E入队。如图5、6所示。
图5层次遍历队列3
图6二叉树层次遍历过程2
4.队头元素出队，输出C，同时令C的孩子F入队。如图7、8所示。
图7层次遍历队列4
图8二叉树层次遍历过程3
5.队头元素出队，输出D，同时令D的孩子入队，D没有孩子，什么也不做。如图9、10所示。
图9层次遍历队列5
图10二叉树层次遍历过程4
6.队头元素出队，输出E，同时令E的孩子入队，E没有孩子，什么也不做。如图11、12所示。
图11层次遍历队列6
图12二叉树层次遍历过程5
7.队头元素出队，输出F，同时令F的孩子G入队。如图13、14所示。
图13层次遍历队列7
图14二叉树层次遍历过程6
8.队头元素出队，输出G，同时令G的孩子入队, G没有孩子，什么也不做。。如图15、16所示。
图15层次遍历队列8
图16二叉树层次遍历过程7
9.队列为空，算法结束。
算法实现：
1.首先输入一个先序序列字符串，创建一棵二叉树。
在先序序列中，孩子为空时为"#"号。
如图17所示：
图17 二叉树
那么图17中二叉树的先序遍历结果为：ABD##E##CF#G###
调用先序创建二叉树程序，创建二叉树。
2.调用层次遍历函数，对该二叉树进行层次遍历。
运行结果：
按先序次序输入二叉树中结点的值（孩子为空时输入#），创建一棵二叉树
ABD##E##CF#G###
二叉树的层次遍历结果：
A B C D E F G
源码：
[cpp]
#include <iostream>
#include <queue> //引入队列头文件
using name space std;
typedef struct Bnode/*定义二叉树存储结构*/
{ char data;
struct Bnode *lchild,*rchild;
}Bnode,*Btree;
void Createtree(Btree &T)/*创建二叉树函数*/
{
//按先序次序输入二叉树中结点的值（一个字符），创建二叉链表表示的二叉树T
char ch;
cin >> ch;
if(ch=='#')
T=NULL;//递归结束，建空树
else{
T=newBnode;
T->data=ch;//生成根结点
Createtree(T->lchild);//递归创建左子树
Createtree(T->rchild);//递归创建右子树
}
return;
}
bool Leveltraverse(Btree T)
{
Btree p;
if(!T)
return false;
queueQ;//创建一个普通队列(先进先出)，里面存放指针类型
Q.push(T);//根指针入队
while(!Q.empty())//如果队列不空
{
p=Q.front();//取出队头元素作为当前扩展结点livenode
Q.pop();//队头元素出队
cout<<p->data<<"\t";
if(p->lchild)
Q.push(p->lchild);//左孩子指针入队
if(p->rchild)
Q.push(p->rchild);//右孩子指针入队
}
return true;
}
int main()
{
Btree mytree;
cout<<"按先序次序输入二叉树中结点的值（孩子为空时输入#），创建一棵二叉树"<
Createtree(mytree);//创建二叉树
cout<<"二叉树的层次遍历结果："<
Leveltraverse(mytree);//层次遍历二叉树
return 0;
}
此文来自本人博客http://blog.csdn.net/rainchxy
