天津科技大学数据结构树及二叉树.pptVIP

a60 b=‘E’ a70 b=‘D’ a80 b=‘C’ a90 b=‘B’ b=‘A’ 5 15 40 30 a80 b=‘C’ a90 b=‘B’ b=‘A’ a60 b=‘E’ a70 b=‘D’ if(a80) if(a70) if(a60)b=‘E’; else b=‘D’; else b=‘C’; else if(a90)b=‘B’; else b=‘A’; 比较次数=2*(10+30+40)+3*(15+5) =160+60=220 赫夫曼树　给定n个权值作为n个叶子结点的权，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，即赫夫曼树(Huffman tree)。 构造赫夫曼树 (见书P145) (1)根据给定的n个权值{w1,w2,…,wn}，构成n棵二叉树的集合F={T1,T2,…,Tn}，其中每一棵二叉树Ti中只有一个带权为wi的根结点，其左右子树为空。 (2)在F中选取两棵权值最小的树作为左右子树构造一棵新的二叉树，且新二叉树的根结点的权值为其左右子树是根结点权值之和。 (3)在F中删除这两棵树，同时将新得到的二叉树加入F中。 (4)重复(2)和(3)，直到F中只含一棵树为止。该树即为赫夫曼树。 5 2 7 4 A B C D C D 6 5 7 A B C D B A 11 7 C D B A 赫夫曼编码---带权路径长度的应用 数字通信 传输电文 ABACCDA 前缀码编码方案 11 10 01 00 D C B A 电文 00010010101100 14位 前缀码：每一个字符的编码都不是另一个字符编码的前缀 A: 0 B: 00 C: 1 D: 01 不是前缀码引起混淆 6.2 哈夫曼编码 ???通信中，可以采用0,1的不同排列来表示不同的字符，称为二进制编码。 　　在一个字符集中，任何一个字符的编码都不是另一个字符编码的前缀，这种编码称为前缀编码。 可以利用二叉树来设计二进制的前缀编码。约定左分支表示字符‘0’，右分支便是字符‘1’，则可以用从根结点到叶子结点的路径上的分支字符串作为该叶子结点字符的编码。如此得到的编码便是前缀编码。 　　如何得到最短的二进制编码？ 　　求最短的二进制编码实际上就是构造赫夫曼树的过程，由此得到的二进制编码，称赫夫曼编码。 　　哈夫曼编码是一种不等长的二进制编码，而且哈夫曼树是最优二叉树，它的编码也是一种最优编码。 　　在哈夫曼树中得到的叶子结点的编码为从根结点到叶子结点中所有路径中0、1的顺序排列。 用二叉树设计前缀码 电文ABACCDA 01001101101110 14位 111 110 10 0 D C B A B C D A 0 1 0 1 0 1 赫夫曼编码---使电文总长最短的二进制编码 电文 ABACCDA 字符出现的频度 A 3次 B 1次 C 2次 D 1次 构造一棵权为{3，1，2，1} 的赫夫曼树 111 10 110 0 D C B A 电文 0110010101110 13位 C B D A 0 1 0 1 0 1 由于赫夫曼树中没有度为1的结点(这类树又称严格的(strict)(或正则的)二叉树)；则一棵有n个叶子结点的赫夫曼树共有2n-1个结点(因n2=n0-1)，可以存储在一个大小为2n-1的一维数组中。 如何选定结构类型？ （1）编码需要从叶子到根 （2）译码需要从根到叶子 　　对于每个结点，既要含双亲结点的信息，又要含孩子结点的信息。 void TraverseHuffman(PhtTree T, char** HC, int n) { static int codeLen = 0; /* 为什么使用静态变量? */ static char cd[MaxLen]; if(!T) return; if(T.ht[n].rlink = = -1) /* Why ? */ { cd[codeLen] = \0; strcpy(HC[n], cd); } else { cd[codeLen++] = 0; TraverseHuffman(T, HC, T.ht[n].llink); codeLen--; cd[codeLen++] = 1; TraverseHuffman(T, HC, T.