2015_SHI_DS_树和二叉树.ppt

操作要点1：对权值的合并、删除与替换 ——在权值集合{7,5,2,4}中，总是合并当前值最小的两个权 构造Huffman树的步骤： 注：方框表示外结点（叶子，字符对应的权值）， 圆框表示内结点（合并后的权值）。 操作要点2：按左0右1对Huffman树的所有分支编号！ d a i n 1 1 1 0 0 0 Huffman编码结果：d=0, i=10, a=110, n=111 WPL=1bit×7＋2bit×5+3bit(2+4)=35 特点：每一码都不是另一码的前缀，绝不会错译! 称为前缀码 ——将 Huffman树 与 Huffman编码 挂钩 例2（严题集6.26③）：假设用于通信的电文仅由8个字母 {a, b, c, d, e, f, g, h} 构成，它们在电文中出现的概率分别为{ 0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10}，试为这8个字母设计哈夫曼编码。如果用0～7的二进制编码方案又如何？ 霍夫曼编码的基本思想是：概率大的字符用短码，概率小的用长码。由于霍夫曼树的WPL最小，说明编码所需要的比特数最少。这种编码已广泛应用于网络通信中。 解：先将概率放大100倍，以方便构造哈夫曼树。权值集合 w={7, 19, 2, 6, 32, 3, 21, 10}， 按哈夫曼树构造规则（合并、删除、替换），可得到哈夫曼树。 w4={19, 21, 28, 32} 为清晰起见，重新排序为:w={2, 3, 6, 7, 10, 19, 21, 32} 2 3 5 6 w1={5, 6, 7, 10, 19, 21, 32} w2={7, 10, 11, 19, 21, 32} w3={11, 17, 19, 21, 32} 11 10 7 17 28 21 19 40 w5={28,32,40} 32 60 w6={40,60} w7={100} 100 b c a d e g f h 哈夫曼树 × × × × × × × × × × × × × × 对应的哈夫曼编码（左0右1）： 2 3 5 6 11 10 7 32 17 28 21 19 40 60 100 b c a d e g f h 0 0 0 0 0 1 1 1 1 1 1 1 0 0 符 编码 频率 a 0.07 b 0.19 c 0.02 d 0.06 e 0.32 f 0.03 g 0.21 h 0.10 符 编码 频率 a 0.07 b 0.19 c 0.02 d 0.06 e 0.32 f 0.03 g 0.21 h 0.10 Huffman码的WPL＝2(0.19+0.32+0.21) + 4(0.07+0.06+0.10) +5(0.02+0.03) =1.44+0.92+0.25=2.61 WPL＝3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3 1100 00 11110 1110 10 11111 01 1101 000 001 010 011 100 101 110 111 二进制码 另一种结果表示： 例3:设字符集为26个英文字母，其出现频度如下表所示。 51 48 1 15 63 57 20 32 5 1 频度 z y x w v u t 字符 1 16 1 18 8 23 80 频度 p 21 f q 15 g r 47 h s o n m l k j 字符 57 103 32 22 13 64 186 频度 i e d c b a 空格 字符 先建哈夫曼树，再利用此树对报文“This program is my favorite”进行编码和译码。 要求编程实现： 提示1：霍夫曼树中各结点的结构可以定义为如下5个分量： char weight parent lchild Rchild 将整个霍夫曼树的结点存储在一个数组中：HT[1..n]; 将结点的编码存储在HC[1..n]中。 提示3：霍夫曼树如何构造？构造好之后又如何求得各结点对应的霍夫曼编码？——算法参见教材P147。 提示2：霍夫曼树的存储结构可采用顺序存储结构： 二叉树小结 1、定义和性质 2、存储结构 3、遍历 4、线索化：线索树 顺序结构 链式结构 二叉链表 三叉链表 先序线索树 中序线索树 后序线索树 树 二叉树 森林 中序遍历 后序遍历 先序遍历 霍夫曼树 霍夫曼编码 6.4 树和森林 1. 树和森林与二叉树的转换 2. 树和森林的存储方式 3. 树和森林的遍历 1. 树和森林与二叉树的转换 转换步骤： step1: 将树中同一结点的兄弟相连; step2: 保留结点的