本文共 1982 字,大约阅读时间需要 6 分钟。
数据结构第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中二叉树的先序遍历结果为:ABD##E##CF#G###
调用先序创建二叉树程序,创建二叉树。
2.调用层次遍历函数,对该二叉树进行层次遍历。
运行结果:
按先序次序输入二叉树中结点的值(孩子为空时输入#),创建一棵二叉树
ABD##E##CF#G###
二叉树的层次遍历结果:
A B C D E F G
源码:
#include#include //引入队列头文件using namespace 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=new Bnode; T->data=ch; //生成根结点 Createtree(T->lchild); //递归创建左子树 Createtree(T->rchild); //递归创建右子树 } return;}bool Leveltraverse(Btree T){ Btree p; if(!T) return false; queue Q; //创建一个普通队列(先进先出),里面存放指针类型 Q.push(T); //根指针入队 while(!Q.empty()) //如果队列不空 { p=Q.front();//取出队头元素 Q.pop(); //队头元素出队 cout< data<<"\t"; if(p->lchild) Q.push(p->lchild); //左孩子指针入队 if(p->rchild) Q.push(p->rchild); //右孩子指针入队 } return true;}int main(){ Btree mytree; cout<<"按先序次序输入二叉树中结点的值(孩子为空时输入#),创建一棵二叉树"<