《第5章树和二叉树--4》由会员分享，可在线阅读，更多相关《第5章树和二叉树--4（35页珍藏版）》请在金锄头文库上搜索。
1、第6章树和二叉树Tree and Binary Tree 主讲：顾为兵(4)第六章 树和二叉树目录6.1 树的定义和基本术语6.2 二叉树6.3 遍历二叉树和线索二叉树6.4 树和森林6.5 哈夫曼树及其应用6.5 哈夫曼树及其应用6.5.1 哈夫曼树的定义6.5.2 哈夫曼树的构造6.5.3 哈夫曼编码哈夫曼树及其应用6.5.1 哈夫曼树的定义路径：从一个结点到另一个结点所经过的分支路径长度L：路径上分支的数目树的路径长度PL：根到每个结点的路径长度之和 n结点个数EFDCBAEFCBADh=3, PL=0+1+1+2+2+2=8h=5, PL=0+1+2 +3+4+4=13哈夫曼树及其应用
2、 哈夫曼树的定义树的带权路径长度WPL：树中所有叶子带权路径长度之和n树叶个数哈夫曼树：由权值为 w1,w2,.,wn)的n片叶子构成的所 有二叉树中，WPL值最小的二叉树。哈夫曼树又被称为最优二叉树结点的带权路径长度：结点的权值乘结点到根的路径长度wili哈夫曼树及其应用 哈夫曼树的定义CBAD7 5 2 4ADCBWPL=71+52+23+43=35ABCDWPL=72+52+22+42=36BACDWPL=46CDABWPL=351. 哈夫曼树不一定是最矮的树2. 哈夫曼树形态可能不唯一哈夫曼树及其应用 哈夫曼树的定义6.5 哈夫曼树及其应用6.5.1 哈夫曼树的定义6.5.2 哈夫曼树
3、的构造6.5.3 哈夫曼编码哈夫曼树及其应用6.4.2 哈夫曼树的构造1952年，Huffman提出了一个构造最优二叉树的一个精巧算法，被人们称为Huffman算法。哈夫曼树及其应用 哈夫曼树的构造Huffman算法思想：1. 将权值为w1, w2, ., wn的n个叶子构成一个具有n棵 树的森林：2. 从森林F中选取根权值最小的两棵树，分别作为左子树和右子树，再新添一个结点做为根，合并成一棵新的二叉树，新二叉树根的权值等于左、右子树根权值之和。3. 重复2，直到F中只剩下一棵树为止，这棵树就是所求的Huffman树。w1w2w3wnF哈夫曼树及其应用 哈夫曼树的构造a6b1f4c5d4e2e
4、2b13哈夫曼树及其应用 哈夫曼树的构造a6f4c5d4d4e2b13e2b137哈夫曼树及其应用 哈夫曼树的构造a6f4c5 d4e2b137c5f49哈夫曼树及其应用 哈夫曼树的构造a6a6d4e2b13713c5f49d4e2b137哈夫曼树及其应用 哈夫曼树的构造c5f49a613d4e2b137 22a613d4e2b137c5f49哈夫曼树及其应用 哈夫曼树的构造c5f4922a613d4e2b137WPL=(1 + 2 )4 + 43 + (4 + 5 + 6)2=54哈夫曼树及其应用 哈夫曼树的构造8 构造n个叶子的哈夫曼树需要经过n-1次合并，每次合并都要增加一个新结点。所以
5、n个叶子的哈夫曼树上有且仅有2n-1个结点8 哈夫曼树上不存在度为1的结点。我们把这种不存在度为1的结点的二叉树称为严格二叉树或正则二叉树。n0=n2+1n=n0 + n1 + n2 = n0 + n2 = n0 + (n0-1) = 2 * n0 - 1哈夫曼树及其应用 哈夫曼树的构造哈夫曼树的存储结构：weight parent lchildrchild 0610-1-1117-1-1259-1-1348-1-1427-1-1549-1-16382577107489116391311181022-1910chars 0a 1b 2c 3d4e5fc5f4922a613d4e2b1372n2
6、哈夫曼树及其应用 哈夫曼树的构造huffman树的类型定义：typedef structunsigned int weight;int parent,lchild,rchild;HTNode;typedef structHTNode *Htree;int root;HuffmanTree;哈夫曼树及其应用 哈夫曼树的构造在这种存储结构上设计Huffman算法：weight parent lchildrchild 06-1-1-111-1-1-125-1-1-134-1-1-142-1-1-154-1-1-16 -1-1-17-1-1-18-1-1-19-1-1-110-1-1-1 2n11.初
7、始化2. 进行n1次合并：8在parent-1的结点中选权值最小的两个结点s1和s2；8填写s1和s2的双亲；8填写新结点的权和左、右孩子s1s2哈夫曼树及其应用 哈夫曼树的构造void Create_Huffman ( HuffmanTree HT = T.Htree = new HTNodem; /申请huffman数 组for(i=0;in;i+) HTi=wi,-1,-1,-1;/初始 化for(i=n;im;i+) HTi=-1,-1,-1,-1; for(i=n;im;i+)select(HT,i-1,s1); /在T.HTree0i-1选parent=-1的最小权值根HTs1.p
8、arent=i; select(HT,i-1,s2); HTs2.parent=i ; HTi.weight = HTs1.weight + HTs2.weight;HTi.lchild=s1; HTi.rchild=s2; H.root=m-1; 6.5 哈夫曼树及其应用6.5.1 哈夫曼树的定义6.5.2 哈夫曼树的构造6.5.3 哈夫曼编码哈夫曼树及其应用6.4.3 哈夫曼编码和解码编码 发送 ： 电文 0,1 序列 (比特流)接收： 0, 1序列 电文解码例如： 电文“abcdedacafcfadcacfdaef”字符集 a, b, c, d, e, f 字符出现次数 6, 1, 5,
9、 4, 2, 4 哈夫曼树及其应用 哈夫曼编码和解码等长编码：000001010011100011000010000101010000.不等长编码：010001101101000011001100100.电文“abcdedacafcfadcacfdaef”字符集 a, b, c, d, e, f 编码方案：abcdef串长特点等长编码00000101001110010166串长太大不等长编码010001101137有多义性前缀码101100011101 1110056好前缀码：任何字符的编码都不是其他字符编码的前缀前缀码：101100011101111110110011011.哈夫曼树及其应用
10、 哈夫曼编码和解码电文“abcdedacafcfadcacfdaef”字符集 a, b, c, d, e, f 利用二叉树可以获得前缀码：以字符集中的字符为叶子，构造一棵二叉树; 在左树枝上标0码，右树枝上标1码。从树根到树叶所经历的分支构成了相应叶子字符的前缀码：cfadeb0100111001a: 10 b: 1100 c: 01 d: 111 e: 1101f: 00哈夫曼树及其应用 哈夫曼编码和解码由于n个叶子能够构造出很多形态各异的二叉树，因而会有多种前缀码方案，取那种呢？当然是使得电文比特流为最短的编码方案。 cfadeb0100111001a: 10 b: 1100 c: 01
11、d: 111 e: 1101f: 00哈夫曼树及其应用 哈夫曼编码和解码8 显然，如果ci是权，比特流长度就是二叉树的WPL。8 哈夫曼树的WPL是最小的，故用哈夫曼树产生前缀码是最优前缀码，又称为哈夫曼编码。n字符个数ci字符在电文中重复出现次数li串长，根到叶子的路径长度哈夫曼树及其应用 哈夫曼编码和解码在哈夫曼树上获得前缀码的方法是：先序遍历哈夫曼树,用一个栈保存遍历时“采集”到的0码和1码：向左拐时0进栈，向右拐时1进栈。遍历到树叶时将栈中保存的编码序列复制到HC中。回溯时做出栈操作。cfadeb0100111001哈夫曼树及其应用 哈夫曼编码和解码f: 00 c: 01 a: 10
12、b: 1100 e: 1101 d: 111HTweight parent lchildrchild0610-1-1 117-1-1259-1-1348-1-1427-1-1549-1-1 63825 771074 891163 9131118 1022-1910chars 0a1b2c3d4e5fcfadeb0100111001哈夫曼树及其应用 哈夫曼编码和解码HC 0123451 0 0 1 100 0 0 1 0 1 1 1 0 1 100 100 0void HuffmanCoding(HuffmanTree T,HuffmanCode /初始化一个空栈S，S中保留遍历时收集的0码和1
13、码HC=new (char *)n; /coding(T, HT.root, S, HC);for(i=0;in;i+) printf(“%c: %sn”, charsi,HCi);哈夫曼树及其应用 哈夫曼编码和解码void Coding(HuffmanTree T, int i, SqStack /字符串结束标志0进栈 HCi=new charStackLength(S)strcpy(HCi, S.base); /复制叶子i的huffman码Pop(S, ch); /字符串结束标志0出栈 else Push(S,0); /向左转前0进栈 coding(T, T.Htreei.lchild,
14、HC); /遍历左子树Pop(S, ch); /遍历空左子树时入栈的0出栈 Push(S,1); /向右转前1进栈 coding(T, T.Htreei.rchild, HC); /遍历右子树Pop(S, ch); /遍历空右子树时入栈的1出栈pop(S,ch); /一棵子树遍历结束，出栈 Huffman解码：将比特流还原成电文也是在哈夫曼树上实现的：8 从左至右扫描比特流；8 自树根开始，逢0沿左链向下，逢1沿右链向下，直到遇到到叶子；8 还原叶子字符；8 再回到树根；重复上述过程，直至比特流被扫描完。哈夫曼树及其应用 哈夫曼编码和解码cfadeb0100111001电文“abcdedaca
15、f”1 0 1 1 0 0 0 1 1 1 1 1 1 0 1 1 1 1 1 0 0 1 1 0 0 0abcd哈夫曼树及其应用 哈夫曼编码和解码void Decoding(HuffmanTree T, char *bits, char *chars) /Huffman解码，bits是比特流串，chars存放字符集字符char *p=bits;int i=T.root;while(*p!=0)if(*p=0)i=T.HTreei.lchild;/逢0左拐 else i=T.HTreei.rchild;，/逢1右拐if(T.HTreei.lchild=-1)printf(“%c”, charsi); /打印叶子字符i=T.root; /回到树根/ifp+;/whileif(i!=T.root)printf(“Er
