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

《叉树的存储结构和遍历算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、五、遍历算法的应用举例1、统计二叉树中叶子结点的个数(先序遍历)2、求二叉树的深度(后序遍历)3、复制二叉树(后序遍历)4、建立二叉树的存储结构作业：6.3,6.5,6.13,6.14,6.33,6.37,6.4311、统计二叉树中叶子结点的个数算法基本思想:先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。由此，需在遍历算法中增添一个“计数”的参数，并将算法中“访问结点”的操作改为：若是叶子，则计数器增1。2voidCountLeaf(BiTreeT,int*count){//求叶子结点的个数，T为根结点的指针if(T){if((!T->lchild)&&(!T->

2、rchild))(*count)++;//若T是叶子结点，对其计数CountLeaf(T->lchild,count);//对左子树中叶结点计数CountLeaf(T->rchild,count);}//if}//CountLeaf（方法1：利用参数返回结果）注：在主调函数中应将count所指单元赋初值为0。3intLeafCount_BiTree(BitreeT)//求二叉树中叶子结点的数目{if(!T)return0;//空树没有叶子elseif(!T->lchild&&!T->rchild)return1;//叶子结点elsereturnLeafCount_BiTree(T->

3、lchild)+LeafCount_BiTree(T->rchild);//左子树的叶子数加上右子树的叶子数}//LeafCount_BiTree（方法2：利用函数返回值得到结果）42、求二叉树的深度(后序遍历)算法基本思想:从二叉树深度的定义可知，二叉树的深度应为其左、右子树深度的最大值加1。由此，需先分别求得左、右子树的深度，算法中“访问结点”的操作为：求得左、右子树深度的最大值，然后加1。首先分析二叉树的深度和它的左、右子树深度之间的关系。5intBiTreeDepth(BiTreeT){//返回二叉树的深度,T为树根的指针if(!T)depthval=0;else{depth

4、Left=BiTreeDepth(T->lchild);depthRight=BiTreeDepth(T->rchild);depthval=1+(depthLeft>depthRight?depthLeft:depthRight);}returndepthval;}后序遍历求深度64、建立二叉树的存储结构不同的定义方法相应有不同的存储结构的建立算法至少掌握一种建树算法7以字符串的形式根左子树右子树定义一棵二叉树例如:ABCD以空白字符“”表示空树ABCD只含一个根结点的二叉树A以字符串“A”表示以下列字符串表示8StatusCreateBiTree(BiTree&T){//按先序

5、次序输入结点信息scanf(&ch);if(ch=='')T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);T->data=ch;//生成根结点CreateBiTree(T->lchild);//构造左子树CreateBiTree(T->rchild);//构造右子树}returnOK;}//CreateBiTree,无头结点//在先序遍历过程中完成，对根结点的访问是“生成一个结点”9ABCD上页算法执行过程举例如下：ATBCD^^^^^看随书光盘DSDemoW演示10由原始表达式建树算法这个算

6、法如有同学感兴趣，可以上网搜索收看严蔚敏本人的教学视频，有详细介绍（其中还有其他一些本书没介绍的建树算法）。同学们可以听听严的教学，补缺补差。由二叉树的广义表表示建立存储结构的算法请参考徐孝凯编写的《数据结构课程实验》第59页。此作为上机操作的一个内容。11对于一个完全二叉树来说，利用先序序列、中序序列和后序序列可以确定此树。然而，对于一个一般的二叉树，仅知二叉树的先序序列“abcdefg”不能唯一确定一棵二叉树。如果同时已知二叉树的中序序列“cbdaegf”，则会如何？由二叉树的先序和中序序列建树二叉树的先序序列二叉树的中序序列左子树左子树右子树右子树根根121.根据先序序列的第

7、一个元素建立根结点；2.在中序序列中找到该元素，确定根结点的左右子树的中序序列；3.在先序序列中确定左右子树的先序序列；4.由左子树的先序序列和中序序列建立左子树；5.由右子树的先序序列和中序序列建立右子树。已知一棵二叉树的先序序列和中序序列，构造该二叉树的过程如下：abcdefgcbdaegf先序序列中序序列13abcdefgcbdaegf例如:abcdefg^^^^^^^^先序序列中序序列14例1.已知树的先序次序为abdcegf中序次序为bdaegc