6第六章 树和森林.ppt

3．树的层次遍历树的层序遍历也称为树的广度遍历,就是从树的第一层(根结点)开始,自上至下逐层遍历,在同一层中,则按从左到右的顺序对结点逐个访问。对于右图所示的树,按层序遍历方式进行遍历所得到的结点序列为:A、B、C、D、E、F、G、H、I、K、L、M、N在进行层序遍历时,对一层结点访问完后,再按照它们的先后访问次序对各个结点的孩子结点依次访问。因此,在进行树的层序遍历时,可以设置一个队列结构,并按下述步骤层序遍历树:(1)初始化队列,并将根结点入队。(2)当队列非空时,取出队头结点p,转步骤3;如果队列为空,则结束遍历。(3)访问取出的结点p;如果结点p有孩子,则依次将它们入队列。(4)转步骤(2)。请比较:ABCDEFGHIABCDEFGHI先根:后根:ABEFGCDHIEFGBCHIDA先序:中序:ABEFGCDHIEFGBCHIDA先根后根先序中序树二叉树根据树与二叉树的转化关系以及树和二叉树的遍历定义可以得知,树的先根遍历与其转化后相应二叉树的前序遍历的结果序列相同;树的后根遍历与其转化后相应二叉树的中序遍历的结果序列相同。因此,树的遍历算法也可采用相应的二叉树的遍历算法实现。先根后根先序中序6.7.4森林的遍历森林的遍历通常有三种方式:先根遍历、中根遍历和后根遍历。下面对它们分别作介绍。1．森林的先根遍历?若森林F为空,返回;否则 ?访问F的第一棵树的根结点;?先根次序遍历第一棵树的子树森林;?先根次序遍历其它树组成的森林对上图所示的森林进行先根遍历,得到的结果序列为:A、B、C、D、E、F、G、H、I2．森林的中根遍历?若森林F为空,返回;否则?中根次序遍历第一棵树的子树森林;?访问F的第一棵树的根结点;?中根次序遍历其它树组成的森林。对下图所示的森林进行中根遍历,得到的结果序列为:B、C、D、A、F、E、H、I、G3．森林的后根遍历?若森林F为空,返回;否则?后根次序遍历第一棵树的子树森林;?后根次序遍历其它树组成的森林;?访问F的第一棵树的根结点。 对下图所示的森林进行后根遍历,得到的结果序列为:D、C、B、F、I、H、G、E、A请比较:森林二叉树先根:中根:后根:ABCDEFGHIBCDAFEHIGDCBFIHGEA先序:中序:后序:先根中根后根先序中序后序ABCDEFGHIABCDEFGHIBCDAFEHIGDCBFIHGEAABCDEFGHIBCDAFEHIGDCBFIHGEA根据森林与二叉树的转化关系以及森林和二叉树的遍历定义可以得知,森林的先根遍历与其转化后相应二叉树的前序遍历的结果序列相同;森林的中根遍历与其转化后相应二叉树的中序遍历的结果序列相同;森林的后根遍历与其转化后相应二叉树的后序遍历的结果序列相同。因此,森林的遍历算法也可采用相应的二叉树的遍历算法实现。等价类和并查集二叉树回顾作业:习题64,11思考题:1,2,7,8等价类和并查集在实际应用中,经常会遇到等价类的问题。例如,在进行软件测试时,需要把测试的数据按条件分类,测试同一功能的数据可以作为一个等价类。在数学上,等价类是一个对象(或成员)的集合,在这个集合中的所有对象应满足等价关系(用符号“?”表示)。等价关系是一个自反的、对称的和传递的关系。一般地,一个集合S中的所有对象可以通过等价关系划分为m个互不相交的子集S1、S2、…、Sm,即：对于S中的任何两个元素x和y(x、y?S),如果x和y是等价的(x?y),则x和y被划分在同一个子集Si中(i=1、2、…、m)。这些子集就被称为等价类。等价关系的例子很多,例如：平面上三角形集合中,三角形的相似关系是一个等价关系;在学校的学生集合中,在同一个班级的关系也是一个等价关系。利用等价关系把集合S划分成若干等价类的算法分两步走:(1)首先把S中的每一个对象看成是一个等价类;(2)依次处理各个等价对(x?y):若x?Si、y?Sj,且Si?Sj,则把集合Si、Sj合并成一个集合。例如,给定集合S＝{a,b,c,d,e,f,g,h,i,j}