(8)--第4章 树和二叉树-哈夫曼树.ppt

《(8)--第4章 树和二叉树-哈夫曼树.ppt》由会员分享，可在线阅读，更多相关《(8)--第4章 树和二叉树-哈夫曼树.ppt（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第5章 树和二叉树哈夫曼树哈夫曼树游游戏戏中中主主角角的的生生命命值值d d，有有这这样样的的条条件件判判定定：当当怪怪物物碰碰到到主主角角后后，怪怪物物的的反反应应遵遵从从下下规则规则:5.6 5.6 哈夫曼树及其应用哈夫曼树及其应用if(d100)state=嘲笑，单挑嘲笑，单挑;else if(d200)state=单挑单挑;else if(d300)state=嗜血魔法嗜血魔法;else if(d=200)&(d=300)&(d=100)&(d200)state=单挑单挑;else if(d100)state=嘲笑，单挑嘲笑，单挑;else state=逃跑逃跑;if(d100)sta

2、te=嘲笑，单挑嘲笑，单挑;else if(d200)state=单挑单挑;else if(d300)state=嗜血魔法嗜血魔法;else if(d500)state=呼唤同伴呼唤同伴;else state=逃跑逃跑;在在远程通程通讯中，要将待中，要将待传字符字符转换成二成二进制的字符串，制的字符串，怎怎样编码才能使它才能使它们组成的成的报文在网文在网络中中传得最快？得最快？ABACCDA000110010101100000011010哈夫曼哈夫曼树应用用实例哈夫曼例哈夫曼编码出现次数较多的字符采用尽可能短的编码哈夫曼哈夫曼树应用用实例哈夫曼例哈夫曼编码关关键：要要设计长度不等的度不等的编码

3、，则必必须使任一字符使任一字符的的编码都不是另一个字符的都不是另一个字符的编码的的前前缀前前缀编码0000AAAA ABA BB重码ABACCDA000011010ACBD000111采用二叉树设计前缀编码左分支用“0”右分支用“1”A0B110C10D111 0110010101110 ABACCDA分解接收字符串：遇分解接收字符串：遇“0”向左，遇向左，遇“1”向右；向右；一旦到达叶子一旦到达叶子结点，点，则译出一个字符，反复由根出一个字符，反复由根出出发，直到，直到译码完成。完成。0110010101110ACBD000111ABACCDA特点：每一码都不是另一码的前缀，绝不会错译!称为

4、前缀码哈夫曼哈夫曼编码的的译码过程程路路径径：路径路径长度度：带权路径路径长度度：树的的带权路径路径长度度：哈哈 夫夫 曼曼 树：由一由一结点到另一点到另一结点点间的分支所构成的分支所构成路径上的分支数目路径上的分支数目结点到根的路径点到根的路径长度与度与结点上点上权的乘的乘积debacf g树中所有叶子中所有叶子结点的点的带权路径路径长度之和度之和带权路径路径长度最小的度最小的树ae的路径长度2WPL=wklk k=1n哈夫曼哈夫曼树的构造的构造dcab2475WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=35abcd7524WPL=7*

5、2+5*2+2*2+4*2=36权值分分别为7，5，2，4，构造有，构造有4个叶子个叶子结点的二叉点的二叉树a7b5c2d4a7b5c2d46a7b5c2d411a7b5c2d418a7b5c2d4哈夫曼哈夫曼树的构造的构造过程程操作要点：操作要点：对权值的的合并、合并、删除与替除与替换，总是合并当前是合并当前值最小的两个最小的两个基本思想：基本思想：使使权大的大的结点靠近根点靠近根基本思想：概率大的字符用短基本思想：概率大的字符用短码，小的用，小的用长码，构造哈夫，构造哈夫曼曼树哈夫曼哈夫曼编码的构造的构造例：某系例：某系统在通在通讯时，只出，只出现C，A，S，T，B五种字符，五种字符，其出

6、其出现频率依次率依次为2，4，2，3，3，试设计Huffman编码。148464220001113301 T B A C ST 00B 01A 10 C 110 S 111例例5.2根据根据给定的定的n个个权值 w1,w2,wn，构造构造n棵只有根棵只有根结点的二叉点的二叉树。在森林中在森林中选取两棵根取两棵根结点点权值最小的最小的树作左右子作左右子树，构，构造一棵新的二叉造一棵新的二叉树，置新二叉，置新二叉树根根结点点权值为其左右子其左右子树根根结点点权值之和。之和。在森林中在森林中删除除这两棵两棵树，同，同时将新得到的二叉将新得到的二叉树加入森加入森林中。林中。重复上述两步，重复上述两步，

7、直到只含一棵直到只含一棵树为止止，这棵棵树即即哈夫哈夫曼曼树。哈夫曼哈夫曼树的构造的构造过程程对n(n大于等于大于等于2)个个权值均不相同的字符构成哈夫均不相同的字符构成哈夫曼曼树，关于，关于该树的叙述中，的叙述中，错误的是（的是（）该树一定是一棵完全二叉一定是一棵完全二叉树树中一定没有度中一定没有度为1的的结点点树中两个中两个权值最小的最小的结点一定是兄弟点一定是兄弟结点点树中任一非叶中任一非叶结点的点的权值一定不小于下一一定不小于下一任一任一结点的点的权值ABCD提交提交单选题2分2024/2/8下面下面给出的从根分出的从根分别到达两个叶子到达两个叶子结点路径上的点路径上的权值序列，能属于

8、同一序列，能属于同一颗哈夫曼哈夫曼树的是（）。的是（）。24,10,5和和24,10,724,10,5和和24,12,724,10,10和和24,14,1124,10,5和和24,14,6ABCD提交提交单选题2分typedef struct int weght;int parent,lch,rch;*HuffmanTree;哈夫曼哈夫曼树构造算法的构造算法的实现（算法（算法5.10）采用采用顺序存序存储结构构一一维结构数构数组结点点类型定型定义一棵有一棵有n个叶子个叶子结点的点的Huffman树有有个个结点点2n-11)初始化初始化HT1.2n-1：lch=rch=parent=02)输入初

9、始入初始n个叶子个叶子结点：置点：置HT1.n的的weight值3)进行以下行以下n-1次合并，依次次合并，依次产生生HTi，i=n+1.2n-1：3.1)在在HT1.i-1中中选两个未被两个未被选过的的weight最小的两个最小的两个结点点HTs1和和HTs2(从从parent=0 的的结点中点中选)3.2)修改修改HTs1和和HTs2的的parent值：parent=i 3.3)置置HTi：weight=HTs1.weight+HTs2.weight,lch=s1,rch=s2哈夫曼哈夫曼树构造算法的构造算法的实现例例:设n=4,w=70,50,20,40试设计 huffman code(

10、m=2*4-1=7)weightparentlchrch170000250000320000440000567weightparentlchrch17070025060032050044050056063461107257180016a70b50c20d40 2024年年2月月8日日 算法算法void CreatHuffmanTree(HuffmanTree HT,int n)if(n=1)return;m=2*n-1;HT=new HTNodem+1;/0号单元未用，号单元未用，HTm表示根结点表示根结点 for(i=1;i=m;+i)HTi.lch=0;HTi.rch=0;HTi.pare

11、nt=0;for(i=1;iHTi.weight;weight parent lch rch1155297814233110 0 0 0 0 0 0 00 0 0 0 0 0 0例例:设设n=8,w=5,29,7,8,14,23,3,11试设计试设计 huffman code(m=2*8-1=15)0 0 0 0 0 0 0 00 0 0 0 0 0 00 0 0 0 0 0 0 00 0 0 0 0 0 0for(i=n+1;i=m;+i)/构造构造 Huffman树树 Select(HT,i-1,s1,s2);/在在HTk(1ki-1)中选择两个其双亲域为中选择两个其双亲域为0,/且权值最

12、小的结点且权值最小的结点,/并返回它们在并返回它们在HT中的序号中的序号s1和和s2 HTs1.parent=i;HTs2.parent=i;/表示从表示从F中删除中删除s1,s2 HTi.lch=s1;HTi.rch=s2;/s1,s2分别作为分别作为i的左右孩子的左右孩子 HTi.weight=HTs1.weight+HTs2.weight;/i 的权值为左右孩子权值之和的权值为左右孩子权值之和 weight parent lch rch115529781423311815192942581009 14101012139 111112131415150138562749101112140

13、0 0 0 0 0 0 00 0 0 0 0 0 0 013构造构造Huffman tree后后,HT为:void CreatHuffmanCode(HuffmanTree HT,HuffmanCode&HC,int n)/从叶子到根逆向求每个字符的赫夫曼编码，存储在编码表从叶子到根逆向求每个字符的赫夫曼编码，存储在编码表HC中中HC=new char*n+1;/分配分配n个字符编码的头指针矢量个字符编码的头指针矢量cd=new char n;/分配临时存放编码的动态数组空间分配临时存放编码的动态数组空间cdn-1=0;/编码结束符编码结束符for(i=1;i=n;+i)/逐个字符求赫夫曼编码

14、逐个字符求赫夫曼编码 start=n-1;c=i;f=HTi.parent;while(f!=0)/从叶子结点开始向上回溯，直到根结点从叶子结点开始向上回溯，直到根结点 -start;/回溯一次回溯一次start向前指一个位置向前指一个位置 if(HTf.lchild=c)cdstart=0;/结点结点c是是f的左孩子，则生成代码的左孩子，则生成代码0 else cdstart=1;/结点结点c是是f的右孩子，则生成代码的右孩子，则生成代码1 c=f;f=HTf.parent;/继续向上回溯继续向上回溯 /求出第求出第i个字符的编码个字符的编码 HCi=new char n-start;/为第

15、为第i 个字符编码分配空间个字符编码分配空间 strcpy(HCi,&cdstart)；/将求得的编码从临时空间将求得的编码从临时空间cd复制到复制到HC的当前行中的当前行中 delete cd;/释放临时空间释放临时空间/CreatHuffanCode2/8/2024给定权值：3,12,7,4,2,8,11，构造哈夫曼树，并计算WPL。作答正常使用主观题需2.0以上版本雨课堂可为此题添加文本、图片、公式等解析，且需将内容全部放在本区域内。正常使用需3.0以上版本评分标准：（1）哈夫曼树6分，WPL满分4分。（2）哈夫曼树错一处扣1分（3）WPL计算公式2分，结果2分。错误不得分。主观题10分

16、答案解析哈夫曼编码是哈夫曼编码是不等长编码不等长编码哈夫曼编码是哈夫曼编码是前缀编码前缀编码，即任一字符的编码都不是另一，即任一字符的编码都不是另一字符编码的前缀字符编码的前缀哈夫曼编码树中没有度为哈夫曼编码树中没有度为1 1的结点。若叶子结点的个数的结点。若叶子结点的个数为为n n，则哈夫曼编码树的，则哈夫曼编码树的结点总数为结点总数为 2n-12n-1发送过程：根据由发送过程：根据由哈夫曼树得到的编码表哈夫曼树得到的编码表送出字符数据送出字符数据接收过程：按接收过程：按左左0 0、右、右1 1的规定，从根结点走到一个叶结的规定，从根结点走到一个叶结点，完成一个字符的译码。反复此过程，直到接收数据点，完成一个字符的译码。反复此过程，直到接收数据结束结束哈夫曼编码的几点结论哈夫曼编码的几点结论1、定义和性质2、存储结构3、遍历4、线索化：线索树顺序结构链式结构二叉链表三叉链表树二叉树森林中序遍历后序遍历先序遍历哈夫曼树哈夫曼编码小结