《数据结构 C++版 普通高等教育“十一五”国家级规划教材 教学课件 ppt 杨秀金 第6章 树与二叉树-6》由会员分享，可在线阅读，更多相关《数据结构 C++版 普通高等教育“十一五”国家级规划教材 教学课件 ppt 杨秀金 第6章 树与二叉树-6（30页珍藏版）》请在金锄头文库上搜索。
1、1,第6章 树与二叉树,第6讲,第6章 树与二叉树,2,本章分为56讲( 每讲2学时),第4讲 6.5 二叉树、树和森林 6.6 树和森林的孩子兄弟表示及遍历 -6.6.1,第5讲 6.6 树和森林的孩子兄弟表示及遍历-6.6.2 6.7 树的应用 -6.7.1,第6讲 6.7 树的应用 -6.7.2,3,6.7.2 哈夫曼树及应用,哈夫曼树（Huffman）又称最优二叉树，是一类带权路径长度最短的树。 有着广泛的应用。压缩技术在数据存储、数据通信和数据保密方面有着重要的意义。目前，各种压缩技术都是建立在哈夫曼编码的基础上，并加以各种改进而形成的。,4,1. 哈夫曼树的基本概念,树中两个结点之
2、间的路径由一个结点到另一结点的分支构成。 两结点之间的路径长度是路径上分支的数目。 树的路径长度是从根结点到每一个结点的路径长度之和。,5,树的带权路径长度,设一棵二叉树有n个叶子结点，每个叶子结点拥有一个权值1，2，n，从根结点到每个叶子结点的路径长度分别为L1，L2，Ln，那么树的带权路径长度为每个叶子的路径长度与该叶子权值乘积之和。通常记作:,6,二叉树以及它们的带权路径长,为了直观起见，在图中把带权的叶子结点画成方形，其他非叶子结点仍为圆形。,7,哈夫曼树的定义,上图的三棵二叉树叶子结点数相同，它们的权值也相同，但它们的WPL带权路径长不相同（38,49,36）。图(c)中WPL最小（
3、36），它就是哈曼树，最优树。 哈夫曼树是在具有同一组权值的叶子结点的不同二叉树中，带权路径长度最短的树，也称最优树。,8,2哈夫曼树的构造,本节介绍，根据给出的一组权值怎样构造生成哈夫曼树。 （1）构造哈夫曼树的方法 （2）哈夫曼树类 （3）哈夫曼算法实现,9,（1）构造哈夫曼树的方法,对于一组叶子的权值:1 ,2 ，,n： 首先把n个叶子结点看做n棵树（仅有一个结点的二叉树），把它们看做一个森林； 在森林中把权值最小和次小的两棵树合并成一棵树，该树根结点的权值是两棵子树权值之和，这时森林中就会减少一棵树； 重复第步直到森林中只有一棵二叉树为止。此树就是哈夫曼树。,10,（1）构造哈夫曼树的
4、方法,现给一组（n=4）具体的权值: 2，4，5，8，其构造过程如图所示。,11,特别注意：,每次总是从森林中的子树根结点中，选出最小、次小值，将两者合并得到一棵子树，根结点值是两者之和。 森林中的子树越来越少，最后森林仅有一棵树，就是哈夫曼树。 值得注意的是，并非每次都是从左到右逐一合并，合并的原则是选最小、次小值。 例如，另有一组（n=4）权值20，40，43，58。请读者务必自行画出合并的过程。,12,进一步讨论：,n个权值（叶子）构成的哈夫曼树其带权路径长度唯一吗？确实唯一，而树形不唯一。 因为将森林中两棵权值最小和次小的子树合并，哪棵做左子树哪棵做右子树并不严格限制。 前面的做法是把
5、权值较小的当做左子树,权值较大的当做右子树。反过来也可以，画出的树形就会有所不同，但WPL值仍然相同。 为了便于讨论交流，在此提倡将权值较小的做左子树、权值较大的做右子树。,13,（2）哈夫曼树类,现选用顺序存储结构，数组容量怎样设置？由哈夫曼树构造过程可知，树中没有度为1的结点。 由二叉树性质可知n0=n2+1，可写成n2=n0-1 而现总结点数为n0+n2，也即2*n01。 如果权值的个数（叶子数）n0用n来代替，则二叉树结点总数为2*n1，数组的大小就是2*n1。假设n10，数组的最大容量为20。 树的每个结点作为数组的一个元素。,14,结点结构如下：,ypedef int ElemTy
6、pe; struct HuffNode /结点结构 ElemType data; /权值数据域 int par; /par=0结点独立，par0为它的双亲下标 int lch,rch; /左右孩子结点在数组中的下标 ;,需教师详细解释 Par， lch，rch,15,哈夫曼树的类定义：,const int MAXSIZE=20; /数组的容量 class HuffTree /哈夫曼树的类 private: HuffNode rMAXSIZE; /保存二叉树结点的数组 int n; /最初权值（叶子）的个数 int t; /哈夫曼树根结点的位置 public: HuffTree(int n0);
7、 /构造函数，n0为权值的个数 void CreatHtree(); /建立哈夫曼树函数 void PrintOutHtree(); /输出函数 void HtreeCode(); /哈夫曼编码函数 ;,16,构造函数和输出函数：,HuffTree:HuffTree(int n0) /构造函数,初始化一个空树 int i; n=n0; for(i=0;i2*n-1;i+) ri.lch=0; ri.rch=0; ri.data=0; ri.par=0; void HuffTree:PrintOutHtree() /输出函数 int j; cout“n “序“setw(5)“权值“setw(5)
8、 “双亲“setw(5)“左孩“ setw(5)“右孩“; for(j=0;j2*n-1;j+) /树根结点的下标是2*n-2 cout“n “jsetw(5)rj.datasetw(5)rj.par setw(5)rj.lchsetw(5)rj.rchendl; ,17,（3）哈夫曼算法实现,算法6.20 void HuffTree:CreatHtree() /建立哈夫曼树 int i,j,x1,x2,m1,m2; for(i=0;i ri.data; i=0; while ( in-1) /合并n1次 m1=m2=32 767; /m1最小值,m2次小值 x1=x2=-1; /x1,x2为
9、最小值、次小值的下标,18,for(j=0;jn+i;j+) /从par=0的数组元素中选最小、次小值 if(rj.datam1) /while ,19,一组权值为（20，40，50，80）,哈夫曼树的根结点（在此是数组元素）的下标位置是2*n2=6。输出函数显示整个r向量，以便查看哈夫曼的构造是否正确。,20,哈夫曼算法的时间复杂度为O(n2),通过下列主函数可以创建一棵哈夫曼树。 int main() int num; coutnum; HuffTree ht(num); ht.CreatHtree(); ht.PrintOutHtree(); _getch(); return 0; ,2
10、1,3哈夫曼树的应用,（1）用于最佳判断过程 （2）用于通信编码,22,（1）用于最佳判断过程,在记分时常把百分制转换成: 优（x=90）、良（80x90）、 中（70x80）、及格（60x70）、 不及格（x60) 5个等级。 若不考虑分数的分布概率，程序判定过程很容易写成图（a）的方法。 而一般考分大多分布在7080分，从图看出这种情况的x值要比较23次才能确定等级。而考试不及格的人数很少，x值比较一次即可定等级。,23,提高程序的运行效率：,能否使出现次数多的在7080分之间的x值比较次数减少些，而使很少出现的低于60分的x值比较次数多一些呢？ 假设成绩对于不及格、及格、中等、良好和优秀
11、的分布概率分别为5%，15%，40%，30%，10%，以它们作为叶子的权值来构造哈夫曼树，如图（b）所示，其值为205%。 针对这些分布概率，如按图（a）的方法计算，带权路径长度为315%。显然第2种方法更好写。,24,但是，事务往往不是绝对的，此时每个判断框内的条件较为复杂，比较两次，反而降低运行效率。因此，采用折衷做法，调整后得到图（c）所示的判定树，它更加切合实际。,25,（2）用于通信编码,哈夫曼树用于通信编码，实质上是一种数据压缩技术。在数据存储、数据通信和数据保密方面有着重要的意义。在通信及数据传输中多采用二进制编码。 为了使电文尽可能的缩短，可以对电文中每个字符出现的次数进行统计
12、。设法让出现次数较多的字符的二进制码短些，而让那些很少出现的字符的二进制码长一些。,26,（2）用于通信编码,设有一段电文，仅用到4个不同字符：A、C、S、T。它们在电文中出现的次数分别为7、2、4、5。把它们当做4个叶子权值所构造的哈夫曼树如图（b）。,令所有左分支取编码为0，令所有右分支取编码为1。将从根结点起到某个叶子结点路径上的各左、右分支的编码顺序排列，就得该叶子结点所代表的字符的二进制编码如图（a）。,27,前缀编码,这些编码拼成的电文不会混淆，因为每个字符的编码均不是其他编码的前缀，这种编码称为前缀编码。 信息编码是一个复杂的问题，还应考虑其他一些因素，如前缀编码每个编码的长度不
13、相等，译码时较困难。还有检测、纠错问题都应考虑在内。这里仅对哈夫曼树举了一个应用实例。哈夫曼编码的方法可设计成哈夫曼树类的成员函数，在建好的哈夫曼树上进行处理，见6.8.2小节。,28,小 结,二叉树有着的重要应用，本节主要介绍了哈夫曼树及应用。熟练掌握哈夫曼树基本概念和算法思想。,29,6.9 小 结,非线性结构主要研究树和图，本章是非线性结构的重要基础介绍了树，特别是二叉树的存储结构和典型遍历算法。 要求熟练掌握树的基本概念和术语。 熟练掌握二叉树的基本概念和5个重要性质。熟练掌握二叉树的二叉链表存储结构，以及在此基础上的先根、中根和后根递归遍历算法。熟悉二叉树的中根非递归遍历和按层遍历算
14、法和特点。重点在于掌握二叉树的各种遍历算法的实质，这是基本要求。同时，应该能够运用遍历的思路和原理写出其他处理二叉树的算法。,30,6.9 小 结,了解线索二叉树的基本概念，这部分内容以中根线索化二叉树为重点。 熟悉树、森林的存储结构和遍历思想。重点掌握孩子兄弟链表存储结构，熟练掌握在此基础上的树、森林与二叉树的转换。理解树和森林在孩子兄弟链表前提下的遍历算法。由此可见二叉树又是研究树和森林的基础。 二叉树有着的重要应用，本章主要介绍了哈夫曼树和二叉排序树。熟练掌握哈夫曼树基本概念和算法思想。掌握二叉排序树的基本概念、特性和二叉排序树的建立算法。 本章的重点和核心是二叉树。对下一章图的存储结构和遍历方法有十分重要的作用。,
