《数据结构第15讲赫夫曼树及其应用.ppt》由会员分享，可在线阅读，更多相关《数据结构第15讲赫夫曼树及其应用.ppt（30页珍藏版）》请在三一办公上搜索。
1、第6章 树和二叉树6.1 树的定义和基本术语6.2 二叉树6.3 遍历二叉树和线索二叉树6.4 树和森林6.6 赫夫曼树及其应用,6.6 赫夫曼树及其应用,1.基本术语1）路径和路径长度 若一棵树中存在一个结点序列k1,k2,kj，使得ki是kj的双亲（0ij），则称此结点序列是从ki kj的路径。从k1kj所经过的分支数称为这两点之间的路径长度，它等于路径上的结点数减1。,在许多应用中，常常将树中的结点赋上一个有着某种意义的实数，称其为该结点的权。结点的带权路径长度（WPL)规定为从树根到该结点之间的路径长度与该结点上权的乘积。,例：结点c的路径长度为2，其WPL=2*9=18,2）结点的权
2、和带权路径长度,树中所有叶子结点的带权路径长度之和。通常记为：其中 n 表示叶子结点的数目，wi 和 li分别表示叶子结点ki的权值和根到ki之间的路径长度。,3）树的带权路径长度,4）赫夫曼（Huffman）树 又称最优二叉树。它是 n 个带权叶子结点构成的所有二叉树中，带权路径长度WPL最小的二叉树。,例：有四个叶子结点a,b,c,d，分别带权为9、4、5、2，由它们构成三棵不同的二叉树。,a）WPL=92+42522240b）WPL=4122539350c）WPL=9152432337,a,b,c,1）根据给定的n个权值w1,w2,wn，构造 n棵二叉树的集合 F=T1,T2,Tn，其中
3、每棵二叉树中均只含一个带权值为wi的根结点,其左、右子树为空树；,4)重复(2)和(3)两步，直至F中只含一棵树为止。,3)从F中删去这两棵树，同时加入刚生成的新树；,2)在F中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和;,2.构造最优树,赫夫曼算法：,3.判定树(赫夫曼树的应用之一),在解决某些判定问题时，利用赫夫曼树可以得到最佳判定算法。例：编制一将学生百分成绩按分数段分级的程序。若学生成绩分布是均匀的，可用图(a)二叉树结构来实现。,输入10000个数据，则需进行31500次比较。,学生成绩分布
4、不是均匀的情况：,有没有一种更好的办法来减少比较次数呢？,(b),以比例数为权构造一棵哈夫曼树，如（b)判断树所示。,再将每一比较框的两次比较改为一次，可得到（c)判定树。,输入10000个数据，仅需进行22000次比较。,4.赫夫曼编码（赫夫曼树的应用之二）,1）二进制编码 通信中，可以采用0、1的不同排列来表示不同的字符，称为二进制编码。发送端需要将电文中的字符序列转换成二进制的0、1序列，即编码；接受端需要把接受的0、1序列转换成对应的字符序列，即译码。,字符：A B A C C D A,电文：,A B C D的编码分别为：00、01、10、11,电文总长度为：14,如何能缩短传送电文的
5、总长度，从而节省传送 时间呢？,若采用不等长编码，让出现频率高的字符具有较短的编码，让出现频率低的字符具有较长的编码，这样有可能缩短传送电文的总长度。,字符：A B A C C D AA B C D的编码分别为：0、00、1、01电文：0 0 0 0 1 1 0 1 0电文总长度为：9,?,无法译码！为此引入前缀编码的概念,2）前缀编码,若对某一字符集进行不等长编码，则要求字符集中任一字符的编码都不能是其他字符编码的前缀。符合此要求的编码叫做前缀编码。,如何设计前缀编码？,利用二叉树设计二进制的前缀编码,如何得到电文总长最短的二进制前缀编码呢？,0,1,假设有一棵如左图所示的二叉树，四个叶结点
6、分别表示A、B、C、D四个字符，且约定左分支表示字符0，右分支表示字符1，则可以从根结点到叶子结点的路径上以分支字符组成的字符串作为该叶子结点的编码。可以证明，如此得到的必为二进制前缀编码。,3）赫夫曼编码,设计电文总长最短的二进制前缀编码即：以 n种字符出现的频率作权，设计一棵赫夫曼树的问题，由此得到的二进制前缀编码称赫夫曼编码。,例：设通信用的电文由字符集a,b,c,d,e,f,g,h中的字母构成，这8个字母在电文中出现的概率分别为 0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10，试为这8个字母设计哈夫曼编码。,a=1010b=00c=10000d=1001
7、e=11f=10001g=01h=1011,b g e d a h c f,typedef struct unsigned int weight;unsigned int parent,lchild,rchild;HTNode,*HuffmanTree;/动态分配数组存储赫夫曼树typedef char*HuffmanCode;,建立赫夫曼树及求赫夫曼编码的算法,赫夫曼树没有度为1的结点，则一棵有n个叶子结点的赫夫曼树共有2n-1个结点，可以存储在一个大小为2n-1的一维数组中。由于在构造赫夫曼树之后，为求编码需从叶子结点出发走一条从叶子到根的路径；而为译码需从根出发走一条从根到叶子的路径。所
8、以，每个结点既需知道双亲的信息，又需知道孩子结点的信息。,void HuffmanCoding(HuffmanTree,for(;iweight=0;p-parent=0;p-lchild=0;p-rchild=0;/*p=0,0,0,0;初始化HT中的内部结点 for(i=n+1;i=m;+i)/建赫夫曼树，(建立HT静态链表中的链)Select(HT,i-1,s1,s2);/在HT1i-1中选择parent/为0且weight最小的两个结点，序号分别为s1和s2 HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weig
9、ht=HTs1.weight+HTs2.weight;,/从叶子到根逆向求赫夫曼编码 HC=(HuffmanCode)malloc(n+1)*sizeof(char*);cd=(char*)malloc(n*sizeof(char);cdn-1=0;/编码结束符 for(i=1;i=n;+i)/逐个字符求赫夫曼编码 start=n-1;/编码结束符位置 for(c=i,f=HTc.parent;f!=0;c=f,f=HTf.parent)/从叶子到根逆向求编码 if(HTf.lchild=c)cd-start=0;else cd-start=1;HCi=(char*)malloc(n-star
10、t)*sizeof(char);strcpy(HCi,/释放工作空间/HuffanCoding,例：已知某系统在通信联络中只可能出现八种字符，其概率分别为0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11，试设计Huffman编码。设权w=（5，29，7，8，14，23，3，11），n=8，则m=15 存储结构的初始状态为：,23,11,5,3,29,14,7,8,HC,0,1,0,0,0,0,0,0,1,1,1,1,1,1,cd,0,本章小结1.熟练掌握二叉树的结构特性2.熟练二叉树的各种存储结构的特点和适用范围3.遍历二叉树是二叉树各种操作的基础。要能灵 活运用遍历算法实现对二叉树的其他操作4.熟练掌握二叉树的线索化过程以及在中序线索 化树中找出给定结点的前驱和后继的方法5.熟悉树的各种存储结构及其特点，掌握数与二 叉树的转换方法6.了解最优树的特性，掌握建立最优树和哈夫曼 编码的方法。,
