数据结构第六章-树解读.ppt

5.哈夫曼算法 例 给定权集合{4,5,3,6,10}，构造哈夫曼树 1.按权值大小排序： 3,4,5,6,10 2.生成森林： 5 3 6 4 10 T1 T2 T3 T4 T5 3.合并两棵权最小的二叉树,并排序,直到成为一棵二叉树： 5 3 6 4 10 7 5 6 10 3 4 7 选择合并 排序 5 3 6 4 10 7 5 6 11 3 4 10 7 3 4 10 7 17 5 6 11 3 4 10 7 17 5 6 11 28 11 5 6 11 3 4 10 7 17 哈夫曼树 选择合并 选择合并 排序 排序 6.最小冗余码/哈夫曼码 ASCII码/定长码 ab12:0110001000110010 97 98 49 50 哈夫曼码/不定长码 能按字符的使用频度,使文本代码的总长度具有最小值。 例. 给定有18个字符组成的文本： A A D A T A R A E F R T A A F T E R 求各字符的哈夫曼码。 (1) 统计： 字符 A D E F T R 频度 7 1 2 2 3 3 (2) 构造Huffman树： 2 1 3 2 3 7 2 1 3 2 3 7 3 2 1 3 2 3 7 3 合并1和2 排序 排序 5 2 1 3 2 3 7 3 合并2和3 5 2 1 3 2 3 7 3 排序 5 2 1 3 2 3 7 3 6 合并3和3 3 3 6 5 2 1 2 3 7 排序 3 3 6 5 2 1 2 3 7 11 合并5和6 3 3 6 5 2 1 2 3 11 7 合并7和11得Huffman树 3 3 6 5 2 1 2 3 11 7 18 叶结点根据权值附上字符，分支标数的Huffman树 字 符 A D E F T R 频 度 7 1 2 2 3 3 编 码 0 1010 1011 100 110 111 (4) 确定Huffman编码： 特点：任一编码不是其它编码的前缀 3 3 6 5 2 1 2 3 11 7 18 0 0 0 0 0 1 1 1 1 1 R T F E D A 如何译码？ Huffman树 例. 给定代码序列： 0 0 1 0 0 0 1 1 1 0 1 0 1 0 1 0 1 1 1 10 文本为：A A F A R A D E T 3 3 6 5 2 1 2 3 11 7 18 0 0 0 0 0 1 1 1 1 1 R T F E D A 7 0 5 0 2 0 4 0 3 0 0 0 0 0 0 0 0 0 0 0 HT[1] HT[2] HT[3] HT[4] HT{5] HT[6] HT[7] HT[8] HT[9] 7 0 5 0 2 6 4 0 3 6 5 0 0 0 0 0 0 0 0 0 0 0 3 5 HT[1] HT[2] HT[3] HT[4] HT{5] HT[6] HT[7] HT[8] HT[9] 7 0 5 7 2 6 4 7 3 6 5 0 9 0 0 0 0 0 0 0 0 0 0 0 3 5 4 2 HT[1] HT[2] HT[3] HT[4] HT{5] HT[6] HT[7] HT[8] HT[9] data parent lchild rchild 算法处理： 结点说明： 7 8 5 7 2 6 4 7 3 6 5 8 9 0 12 0 0 0 0 0 0 0 0 0 0 0 3 5 4 2 6 1 HT[1] HT[2] HT[3] HT[4] HT{5] HT[6] HT[7] HT[8] HT[9] 7 8 5 7 2 6 4 7 3 6 5 8 9 9 12 9 21 0 0 0 0 0 0 0 0 0 0 0 3 5 4 2 6 1 7 8 HT[1] HT[2] HT[3] HT[4] HT{5] HT[6] HT[7] HT[8] HT[9] HT[1]的编码反序列为： 11 则编码为：11 HT[2]的编码反序列为： 10 则编码为：01 同理得： HT[3]：100 HT[4]：00 HT[5]：101 5.线索二叉树的存储结构 (1).结点结构： F A G B D C 二叉树 0/1 0/1 lchild ltag data rtag rchild 左小孩 左标志 结点值 右标志 右小孩 或前趋 或后继 0 A 0 root 中序线