哈夫曼树总结习题[2学时].ppt

6.6 Huffman树 基本概念 ? 构造 ? 编码 ? ; 1. 基本概念 路径:从一个结点到另一个结点之间的分支. 路径长度:路径上分支数目. 结点的路径长度:从根结点到该结点的路径长度. 树的路径长度:树中每个结点的路径长度之和. 完全二叉树这种长度最短的二叉树. 结点的带权路径长度:该结点的路径长度*结点的权值 树的带权路径长度:树中所有叶子结点的带权路径长度之和.记作:WPL=∑wklk 例如 最优二叉树：在所有含n个叶子结点、并带相同权值的二叉树中，必 存在WPL最小的二叉树.又叫Huffman树;W={7，2，4，5，9}; 在解决某些判定问题时,利用Huffman树可得 到最佳判定算法 例如,某厂生产螺钉,要求直径为d,误差σ.现测量某螺钉直径,方法与标准的比较,判定树?; 2. Huffman树的构造(自底向上) ; 接上页:; 构造过程(Huffman算法) (1) n个权值构成n棵独立二叉树的??林F={T1,…Tn} (2)在森林中选出两棵根权值最小的二叉树作为左右子树,构造二叉树,根权值为左右子树的和 (3) 在F中删除这两棵,新构成的添加到F中 (4)重复(2)和(3),直到F中含一棵二叉树为止.; 两个结论: (1) 在Huffman树中没有度为1的结点. (2) 一棵有n个叶子结点的Huffman树共有2n-1个结点.证明? ; 3. Huffman编码 (1) 等长编码 (2) 不等长编码:出现多的字符采用短码,总长短了! 但出现二义性! (3) 前缀编码:一个字符的编码都不是另一个字符的编码的前缀.; (4) Huffman编码:设计Huffman树而得到的编码. 例如:有8种字符,概率如下: {0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11} 解:同时扩大100倍,得权值集合: {5，29，7，8，14，23，3，11}; 作业:;本章小结 1. 掌握树的定义,表示形式和术语(二叉树通用) 掌握树的存储结构(孩子-兄弟表示) 掌握树与二叉树的转换 了解树的ADT定义与树和森林遍历 2. 掌握二叉树的ADT定义,特点,结点的形态,性质,存储结构(二叉链表) 掌握二叉树的遍历,线索的方法 掌握遍历算法的应用 掌握二叉树与树和森林的转换 掌握Huffman树概念,构造和编码