6.7哈夫曼树Huffman树Huffman编码二、卜带权路径长度最短的树Huffman树最优二叉树是通信中最经Huffman编码不等长编码典的压缩编码
6.7 哈夫曼树 一、Huffman树 二、Huffman编码 Huffman树 最优二叉树 Huffman编码 带权路径 长度最短 的树 不等长编码 是通信 中最经 典的压 缩编码
6.7.1 Huffman树寸（最优二叉树）若干术语：路径：由一结点到另一结点间的分支所构成。路径长度路径上的分支数目。例如：a一→e的路径长度=2二叉树的路径长从二叉树根到所有叶子结点的路径度：长度之和。8树路径长度=从二叉树根结点到所有叶子结点的路径长度与二叉树的带权路径长度：相应叶子结点权值的乘积之和（WPL）即树中所有吐子结点的带权路径长度之和Huffman树：带权路径长度最小的树。Huffman常译为哈夫曼、赫夫曼、霍夫曼等
6.7.1 Huffman树（最优二叉树） 路 径： 路径长度： 二叉树的路径长 度： 二叉树的带权路 径长度： Huffman树： 由一结点到另一结点间的分支所构成。 路径上的分支数目。 从二叉树根到所有叶子结点的路径 长度之和。 从二叉树根结点到所有叶子结点的路径长度与 相应叶子结点权值的乘积之和（WPL） 若干术语： d e b a c f g 即树中所有叶子结点的带权路径长度之和 带权路径长度最小的树。 例如：a→e的路径长度＝ 树路径长度＝ 2 8 Huffman常译为哈夫曼、赫夫曼、霍夫曼等
n树的带权路径长度如何Zwklk树中所有叶子结WPL =计算？k=1点的带权路径长度之和经典之例：2254./d(b)(c)(a)WPL=36WPL=35WPL=46Huffman树是WPL最小的树
树的带权路径长度如何 计算？ WPL = wk lk k=1 n a b c d 7 5 2 4 (a) c d a b 2 4 7 5 (b) b d a c 7 5 2 4 (c) 经典之例： WPL= WPL= WPL= Huffman树是WPL 最小的 树 树中所有叶子结 点的带权路径长 度之和 36 46 35
WPL最小的构造Huffman树的基本思想：权值大的结点用短路径，权值小的结点用长路径。构造Huffman树的步骤（即Huffman算法）：(1)由给定的n个权值Wi，W2，.…Wn)构造n棵二叉树的集合F={Ti,T2，T}（即森林），其中每棵二叉树T,中只有一个带权为w的根结点，其左右子树均空。（2）在F中选取两棵根结点权值最小和次小的树分别做为左右子树构造一棵新的二叉树，且让新二叉树根结点的权值等于其左右子树的根结点权值之和(3）在F中删去这两棵树，同时将新得到的二叉树加入F中重复(2）和(3），直到F只含一棵树为止。这棵树便是Huffman4树
构造Huffman树的基本思想： 权值大的结点用短路径，权值小的结点用长路径。 WPL最小的 树 构造Huffman树的步骤（即Huffman算法）： (1) 由给定的 n 个权值{ w1 , w2 , ., wn }构造n棵二叉树的集合F = { T1 , T2 , ., Tn } （即森林） ，其中每棵二叉树 Ti 中只有一个 带权为 wi 的根结点，其左右子树均空。 (2) 在F 中选取两棵根结点权值最小和次小的树分别做为左右子树 构造一棵新的二叉树，且让新二叉树根结点的权值等于其左右 子树的根结点权值之和。 (3) 在F 中删去这两棵树，同时将新得到的二叉树加入 F中。 (4) 重复(2) 和(3) , 直到 F 只含一棵树为止。这棵树便是Huffman 树
具体操作步骤：对权值进行合并、删除与替换一在权值集合(7,5,2.4)中，总是合并当前值最小的两个权a.初始c. 合并[5) (6)d. 合并(7) (11)F:(7)(11)F:(18)F:171(5)(2)(4)52485hb. 合并[2] (4)F :17)(51(6)25h124245
对权值进行合并、删除与替换 ——在权值集合{7,5,2,4}中，总是合并当前值最小的两个权 具体操作步骤： a. 初始 b. 合并{2} {4} c. 合并{5} {6} d. 合并{7} {11}