第六章 树和二叉树(4).ppt

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

1、1 湖南理工学院信息与通信工程学院 数据结构第六章 树和二叉树树的定义与基本操作 二叉树 树和森林 哈夫曼树与哈夫曼编码2 湖南理工学院信息与通信工程学院 数据结构6.4哈夫曼树与哈夫曼编码例：编制一个将百分例：编制一个将百分制转换为五级分制的制转换为五级分制的程序。程序。if(a60)if(a60)b=”bad”;b=”bad”;elseif(a70)elseif(a70)b=”pass”;b=”pass”;elseif(a80)elseif(a80)b=”general”;b=”general”;elseif(a90)elseif(a90)b=”good”;b=”good”;else el

2、seb=”excellent”;b=”excellent”;学生的成绩在五个等级上的分布是不均匀的学生的成绩在五个等级上的分布是不均匀的分数 分数 0 0 5960 5960 6970 6970 7980 7980 8990 8990 100 100比例数 比例数 0.050.150.400.300.10 0.050.150.400.300.1080%80%以上的数据需进行三次或三次以上的比较才能得出结果。以上的数据需进行三次或三次以上的比较才能得出结果。3 湖南理工学院信息与通信工程学院 数据结构相关概念p p叶子结点的权值：叶子结点的权值：对叶子结点赋予的一个有意义的数值量。对叶子结点赋予

3、的一个有意义的数值量。p p路径路径：从树中一个结点到另一个结点之间的分支构成这两个：从树中一个结点到另一个结点之间的分支构成这两个结点间的路径。结点间的路径。p p路径长度：路径长度：路径上的分支数。路径上的分支数。p p树的路径长度：树的路径长度：从树根到每一个结点的路径长度之和。从树根到每一个结点的路径长度之和。p p树的带权路径长度：树的带权路径长度：树中所有带权结点的路径长度之和。树中所有带权结点的路径长度之和。WPLWPL=n nk kk k k kl w1 1第第kk个叶子的权值；个叶子的权值；从根结点到第从根结点到第kk个叶子的路径长度个叶子的路径长度4 湖南理工学院信息与通信

4、工程学院 数据结构p p编码：编码：给每一个对象标记一个二进制位串来表示一组对象。给每一个对象标记一个二进制位串来表示一组对象。p p等长编码：等长编码：表示一组对象的二进制位串的长度相等。表示一组对象的二进制位串的长度相等。p p不等长编码：不等长编码：表示一组对象的二进制位串的长度不相等。表示一组对象的二进制位串的长度不相等。不不等等长长编编码码什什么么情情况下空间效率高？况下空间效率高？等等长长编编码码什什么么情情况况下空间效率高？下空间效率高？5 湖南理工学院信息与通信工程学院 数据结构哈夫曼树又叫最优二叉树，它是由n个带权叶子结点构成的所有二叉树中带权路径长度WPL最短的二叉树。哈夫

5、曼树有4个结点，权值分别为7，5，2，4，构造有4个叶子结点的二叉树a b c d7 5 2 4WPL=7*2+5*2+2*2+4*2=36dca b247 5WPL=7*3+5*3+2*1+4*2=46abc d752 4WPL=7*1+5*2+2*3+4*3=35哈夫曼树的特点：1.权值越大的叶子结点越靠近根结点，而权值越小的叶子结点越远离根结点。2.只有度为0（叶子结点）和度为2（分支结点）的结点，不存在度为1的结点。6 湖南理工学院信息与通信工程学院 数据结构哈夫曼树的构造第第11步：初始化。步：初始化。例：例：WW22，33，44，55哈夫曼树的构造。哈夫曼树的构造。3 524第第2

6、2步：选取与合并。步：选取与合并。325第第33步：删除与加入。步：删除与加入。5 43257 湖南理工学院信息与通信工程学院 数据结构重复第重复第22步步5 43255 49重复第重复第33步步55 49328 湖南理工学院信息与通信工程学院 数据结构重复第 重复第2 2 步 步重复第 重复第3 3 步 步55 493255 4932149 湖南理工学院信息与通信工程学院 数据结构哈夫曼树的类型定义 哈夫曼树是一种二叉树,由于哈夫曼树中没有度为1的结点，则一棵有n个叶子的哈夫曼树共有2n1个结点，可以用一个大小为2n1的一维数组存放哈夫曼树的各个结点。由于每个结点同时还包含其双亲信息和孩子结

7、点的信息，所以构成一个静态三叉链表。静态三叉链表中：每个结点的结构为:权值 双亲序号 左孩子序号 右孩子序号各结点存储在一维数组中，0号单元不使用，从1号位置开始使用。ABCE Ddata parent LChild RChild1 A 0 2 32 B 1 0 03 C 1 4 54 D 3 0 05 E 3 0 0lcdatarcpa(1)10700205003020040400500006000070000lcdatarcpakx1=3,x2=4m1=2,m2=4(2)10700205003020540405536406000070000lcdatarcpakx1=2,x2=5m1=5,

8、m2=6(3)107002050630205404055364662115070000 x1=1,x2=6m1=7,m2=11lcdatarcpak(4)10707205063020540405536466211577118601 1 湖南理工学院信息与通信工程学院 数据结构typedefstructHFTreeNodeintweight;/*结点的权值*/intparent;/*双亲的下标*/intlchild;/*左孩子结点的下标*/intrchild;/*右孩子结点的下标*/HFTreeNode,HuffmanTree;12 湖南理工学院信息与通信工程学院 数据结构voidCreatHuffmanTree(HuffmanTreeTMaxSize,intn)inti,p2,lc,rc;if(n1)printf(结点大小不能小于1);return;intm=2*n;/计算哈夫曼树的结点大小for(i=1;im;i+)/从第1个结点开始用起Ti.parent=0;Ti.lchild=0;Ti.rchild=0;Ti.weight=0;构造哈夫曼树代码