叉树的存储结构和遍历算法.ppt

1,五、遍历算法的应用举例,1、统计二叉树中叶子结点的个数 (先序遍历),2、求二叉树的深度(后序遍历),3、复制二叉树(后序遍历),4、建立二叉树的存储结构,作业：6.3 , 6.5 , 6.13 , 6.14 , 6.33 , 6.37 ,6.43,2,1、统计二叉树中叶子结点的个数,算法基本思想:,先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。由此，需在遍历算法中增添一个“计数”的参数，并将算法中“访问结点”的操作改为：若是叶子，则计数器增1。,3,void CountLeaf (BiTree T, int * count) / 求叶子结点的个数，T为根结点的指针 if (T) if (!T-lchild) / if / CountLeaf,（方法1：利用参数返回结果）,注：在主调函数中应将count所指单元赋初值为0。,4,int LeafCount_BiTree(Bitree T) /求二叉树中叶子结点的数目 if(!T) return 0; /空树没有叶子 else if(!T-lchild /左子树的叶子数加上右子树的叶子数 /LeafCount_BiTree,（方法2：利用函数返回值得到结果）,5,2、求二叉树的深度(后序遍历),算法基本思想:,从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、右子树深度的最大值，然后加 1 。,首先分析二叉树的深度和它的左、右子树深度之间的关系。,6,int BiTreeDepth (BiTree T ) / 返回二叉树的深度, T为树根的指针 if ( !T ) depthval = 0; else depthLeft = BiTreeDepth( T-lchild ); depthRight= BiTreeDepth( T-rchild ); depthval = 1 + (depthLeft depthRight ? depthLeft : depthRight); return depthval; ,后序遍历求深度,7,4、建立二叉树的存储结构,不同的定义方法相应有不同的存储结构的建立算法 至少掌握一种建树算法,8,以字符串的形式 根 左子树 右子树 定义一棵二叉树,例如:,A,B,C,D,以空白字符“ ”表示空树,AB C D,只含一个根结点的二叉树,A,以字符串“A ”表示,以下列字符串表示,9,Status CreateBiTree(BiTree / CreateBiTree ,无头结点,/在先序遍历过程中完成，对根结点的访问是“生成一个结点”,10,A B C D,上页算法执行过程举例如下：,A,T,B,C,D,看随书光盘DSDemoW演示,11,由原始表达式建树算法,这个算法如有同学感兴趣，可以上网搜索收看严蔚敏本人的教学视频，有详细介绍（其中还有其他一些本书没介绍的建树算法）。 同学们可以听听严的教学，补缺补差。,由二叉树的广义表表示建立存储结构的算法请参考徐孝凯编写的数据结构课程实验第59页。此作为上机操作的一个内容。,12,对于一个完全二叉树来说，利用先序序列、中序序列和后序序列可以确定此树。然而，对于一个一般的二叉树，仅知二叉树的先序序列“abcdefg” 不能唯一确定一棵二叉树。 如果同时已知二叉树的中序序列“cbdaegf”，则会如何？,由二叉树的先序和中序序列建树,二叉树的先序序列,二叉树的中序序列,左子树,左子树,右子树,右子树,根,根,13,1. 根据先序序列的第一个元素建立根结点； 2. 在中序序列中找到该元素，确定根结点的左右子树的中序序列； 3. 在先序序列中确定左右子树的先序序列； 4. 由左子树的先序序列和中序序列建立左子树； 5. 由右子树的先序序列和中序序列建立右子树。,已知一棵二叉树的先序序列和中序序列，构造该二叉树的过程如下：,a b c d e f g,c b d a e g f,先序序列,中序序列,14,a b c d e f g,c b d a e g f,例如:,a,b,c,d,e,f,g,先序序列,中序序列,15,例1. 已知树的 先序次序为 abdcegf 中序次序为 bdaegcf 则树为？,a,b,d,c,f,e,g,例2. 已知树的 后序次序为 dbgefca 中序次序为 bdaegcf 则树为？,我们可以利用先序次序和中序次序、后序次序和中序次序、层序序列和中序序列来唯一确定一棵二叉树。,对于例1和例2这样的问题，要能绘出树的形态。习题集中有这类作业，请课下完成,16,层序遍历,遍历序列：,A,A,B,C,B,D,C,E,F,G,D,E,F,G,特点：先访问到的结点，其孩子结点也是先访问。 故：适宜用队列来存储已访问结点的孩子结点,17,层（次）序遍历,队列Q初始化； 2. 如果二叉树非空，将根指针入队； 3. 循环直到队列Q为空 3.1 q=队列Q的队头元素出队； 3.2 访问结点q的数据域； 3.3 若结点q存在左孩子，则将左孩子指针入队； 3.4 若结点q存在右孩子，则将右孩子指针入队；,作业：写出层序遍历算法。,18,/层次遍历算法 void LevelOrd