数据结构第6章(3)

单击此处编辑母版标题样式,北华航天工业学院计算机系 制作,单击此处编辑母版文本样式,第二级,数 据 结 构,第,6,章 树和二叉树,目 标,理解树、二叉树的定义、相关术语；,掌握二叉树的二叉链表存储方式、二叉树性质；,掌握二叉树的四种遍历方式及遍历的实现算法；,理解二叉树的线索化方法；,灵活运用二叉树的遍历方法解决相关的应用问题,理解树、森林和二叉树间的转换,理解树、森林的遍历,本章内容,6.1,树的定义和基本术语,6.2,二叉树,6.3,二叉树的遍历和线索二叉树,6.4,树和森林,6.5,哈夫曼树及其应用,6.5,哈夫曼树及其应用,6.5.1,哈夫曼树,6.5.2,哈夫曼编码,6.5.1,哈夫曼树,1,哈夫曼树的基本概念,路径,路径长度,二叉树的路径长度,二叉树的带权路径长度,最优二叉树,（也称,Haffman,树），指具有最小带权路径长度的二叉树。,6.5.1,哈夫曼树,1,哈夫曼树的基本概念,利用给定的一组权值分别为,1,，,3,，,5,，,7,的叶子结点，构造不同的带权二叉树，并计算其二叉树的带权路径长度。,6.5.1,哈夫曼树,2,构造哈夫曼树方法,由给定的,n,个权值,W1,，,W2,，,，,Wn,构造,n,棵只有,一个叶子结点的二叉树,，从而得到一个二叉树的集合,F,T1,，,T2,，,，,Tn,；,在,F,中选根结点的,权值最小和次小的,两棵二叉树作为左、右子树构造一棵新的二叉树，新二叉树根结点的权值为其左、右子树,权值之和,；,从,集合,F,中,删除,作为左、右子树的两棵二叉树，并将新建立的二叉树,加入,到集合,F,中；,重复前两步，当,F,中只,剩下一棵,二叉树为止。,6.5.1,哈夫曼树,2,构造哈夫曼树方法,根据给定一组权值,2,，,12,，,3,，,5,，,9,，,7,，构造哈夫曼树，并计算其带权路径长度。,3,哈夫曼树的构造算法,设置一个结构体数组,HuffmanTree,保存哈夫曼树中各结点的信息，数组的大小设置为,2n,1,，,数组元素的结构形式如下：,结点初始时,parent,的值为,0,，当结点加入到树中时，该结点,parent,的值为其双亲结点,在数组中的序号,。,6.5.1,哈夫曼树,weight,lchild,rchild,parent,3,哈夫曼树的构造算法,存储类型定义：,typedef,sruct,int,weight;,int,parent,lchild,rchild,;,HTNode,*,HuffmanTree,;,HuffmanTree,HT,;,m=2n-1,;,HT=(HuffmanTree)malloc(,m+1,)*,sizeof(,HTNode,);,/,注意：,0,号单元未用,6.5.1,哈夫曼树,6.5,哈夫曼树及其应用,6.5.1,哈夫曼树,6.5.2,哈夫曼编码,1,哈夫曼树在编码问题中的应用,例：假设要传送的电文为,ABACCDA,，,电文中只含有,A,，,B,，,C,，,D,四种字符。使用,等长编码方法,进行编码。,在传送电文时，总希望,传送时间尽可能短,，这就要求电文代码尽可能短。,在编码时考虑,字符出现的频率,，让出现频率高的字符采用尽可能短的编码，出现频率低的字符采用稍长的编码。,6.5.2,哈夫曼编码,1,哈夫曼树在编码问题中的应用,构造编码总长最短的编码方案：,设编码的,字符集,为,d1,，,d2,，,，,dn,，,它们在电文中出现的,次数或频率集,为,w1,，,w2,，,，,wn,；,以,d1,，,d2,，,，,dn,作为叶子结点,，,w1,，,w2,，,，,wn,作为它们的权值,，构造一棵哈夫曼树；,规定哈夫曼树中的,左分支代表,0,，右分支代表,1,，则从,根结点到每个叶结点,所经过的路径分支组成的,0,和,1,的序列便为该结点对应字符的编码，我们称之为哈夫曼编码。,6.5.2,哈夫曼编码,2,实现哈夫曼编码实现算法,两大部分：,（,1,）构造哈夫曼树；,（,2,）在哈夫曼树上求叶结点的编码。,求哈夫曼编码，实质上就是在已建的哈夫曼树中，从,叶结点开始，沿结点的双亲链回退到根结点,。,由于一个字符的哈夫曼编码是从根结点到相应叶结点所经过的路径上,各分支所组成的,0,，,1,序列,，因此,先得到的分支代码为所求编码的低位码,，后得到的分支代码为所求编码的高位码。,6.5.2,哈夫曼编码,2,实现哈夫曼编码实现算法,设置一指针数组,HuffmanCode,用来存放各字符的哈夫曼编码信息。,每个字符的哈夫曼编码是,0,、,1,序列的字符串。,实现过程：,HC=(HuffmanCode)malloc(n+1)*,sizeof(char,*);,cd,=(char *),malloc(n,*,sizeof(char,);,/,用,cd,存当前叶子结点的哈夫曼编码,HCi,=(char *),malloc(n,-start)*,sizeof(char,);,Strcpy,(HCi,&chstart,);,6.5.2,哈夫曼编码,总 结,哈夫曼树的定义及相关术语,构造哈夫曼树的方法及实现算法,构造哈夫曼编码的方法及实现算法,Thank You！,