2014/47 §6.6 Huffman树及其应用 s6.6 Huffman树及其应用 s6.6.1最优二叉树 s6.6.1最优二叉树 。最忧二叉树(Huffman树) 2。 构造最优二叉树 在权为ww2 ,w的叶子所构成的所有的二叉树 显然，权越大应离根越近，Huffman首先提出了构造方法： WPL意小的称为 二叉树 例n=4,a:7,b:5,c:2,d:41 ”魏整权”笑中兴淡除 为叶子结点，其权为w: 2)食并：在F中选两操根的权囊小的三叉树（考不止两，则 任选作为左、有右孩子，将其合并为一棵新制，新根权值 为这两个结点的权值之和： e:合并后F中少了1棵树 若叶子权值相同，完全二叉树一定是量优二叉树，否则不 3)对新森林F重复2，直至只利下一棵树为止。 s6.6 Huffman树及其应用 s6.6 Huffman树及其应用 s6.6.1最优二叉树 86.6.1最优二叉树 2构造最优二叉树 2构造最优二叉树 ·算法特点 ·存储结构 ①初始有n棵树，每树仅有一个立结点 #define n 100 叶子 合并：每合并一次，少一操制，故只需合并-1次 每合并一次产生结点，且新点度为2，故最终的 define m2n-1∥结点总量 Huffman制有2n-1个结点： typedef struct{ float weight; 1权，不妨设20 2”-个结点/个肝子 int Ichild,rchild,parent;/ 一1个度为2的结点}无1度结点严格的2又树】 }HTNode; 实际上任何严格二叉树中，叶子数为时，总结点数为 typedef HTNode HuffmanTree[m]; 2n-1. parent罐作用：找双亲结点 为1时衰示根，区分根与非根 ·构造算法 s6.6 Huffman树及其应用 §6.6.2 Huffman编码 void CreateHuffmanTree(Huffman Tree T)(∥构道量优树，根为Tm-) int i,p1,p2; 绿念 InitHuffmanTree(T:∥初输化将2n-1个结点的3个指针夏空-1，权里为0 ● 数据压缩 InputWeight(T); ∥轴入n个叶子根)的权存于T0.n-们中，初 可将数据文件压缩20%~90%，压缩效率取决于文件特征 始化意林杆0中的根权 编解码 fori=四：i<m:+K山对中的树合并-1次，新根依次放入T可中，囊钱 编鸭压缩， 根为可m-1】 文科中的字将字符集中字狗一程四架西 二进制位用 SelectMin(Ti-1,&p1,8p2外；∥在当前凛琳T0灯的所有结点中，选权 量小和次小的两个根维点Tp1]和Tp习作为合并时像，0sp1P2-1 Tp】parent=Tp以.parent=i:∥合并产生的新根为T) 编码方案（对字符集编码） T[i].lchild p1; 例C={a,b,c,d,e,,设数据文件有10万字符，1C=6 T[i].rchild p2; e 填码总长 T[i].weight=T[p1]-weight+T[p2].weight 频度万4.51.31.21.00.90.5 定长00000101001110010130万 变长01011001111101110022.4万 算法中用到的三个函数略，实例（教材） 节约25%空间 92014/4/7 9 §6.6 Huffman树及其应用 §6.6.1 最优二叉树  最优二叉树（Huffman树） 在权为w1,w2,…,wn的叶子所构成的所有的二叉树， WPL最小的二叉树称为最优二叉树 例 n=4，{a:7, b:5, c:2, d:4} 49  若叶子权值相同，完全二叉树一定是最优二叉树，否则不 一定 §6.6 Huffman树及其应用 §6.6.1 最优二叉树 2. 构造最优二叉树 显然，权越大应离根越近，Huffman首先提出了构造方法： 1）初始森林：根据给定的n个权{w1,w2,…,wn}构成一个包含 n棵二叉树的森林F={T1,T2,…,Tn}. 其中Ti 只有一个根(亦 为叶子)结点，其权为wi ; 2）合并：在F中选两棵根的权最小的二叉树(若不止两棵，则 任选)作为左 右孩子 将其合并为 棵新树 新根权值 50 任选)作为左、右孩子，将其合并为一棵新树，新根权值 为这两个结点的权值之和； 3）对新森林F重复2)，直至只剩下一棵树为止。 §6.6 Huffman树及其应用 §6.6.1 最优二叉树 2. 构造最优二叉树  算法特点 ① 初始有n棵树，每棵树仅有一个孤立结点 ② 合并：每合并一次，少一棵树，故只需合并n-1次 每合并一次产生1新结点，且新结点度为2，故最终的 Huffman树有2n-1个结点： 51 实际上任何严格二叉树中，叶子数为n时，总结点数为 2n-1。 21 ( ) n   −     n 1 2 n1 2 个叶子 个结点 无 度结点 严格的 叉树 - 个度为 的结点 §6.6 Huffman树及其应用 §6.6.1 最优二叉树 2. 构造最优二叉树  存储结构 #define n 100 // 叶子数 #define m 2*n-1 // 结点总数 typedef struct { float weight; // 权 不妨设≥0 52 float weight; // 权，不妨设≥0 int lchild, rchild, parent; // 指针 } HTNode; typedef HTNode HuffmanTree[m]; parent域作用：找双亲结点 为-1时表示根，区分根与非根  构造算法 §6.6 Huffman树及其应用 void CreateHuffmanTree (HuffmanTree T) { // 构造最优树，根为T[m-1] int i, p1, p2; InitHuffmanTree(T); // 初始化, 将2n-1个结点的3个指针置空(-1),权置为0 InputWeight(T); // 输入n个叶子(根)的权存于T[0..n-1]中，初 //始化森林F0中的根权 for (i = n; i < m; i++){ // 对F中的树合并n-1次，新根依次放入T[i]中，最终 //根为T[m-1] SelectMin(T i-1 &p1 &p2); // 在当前森林T[0 i-1]的所有结点中 选权 53 SelectMin(T, i-1, &p1, &p2); // 在当前森林T[0..i-1]的所有结点中，选权 //最小和次小的两个根结点T[p1]和T[p2]作为合并对象，0≤p1,p2≤i-1 T[p1].parent = T[p2].parent = i; // 合并产生的新根为T[i] T[i].lchild = p1; T[i].rchild = p2; T[i].weight = T[p1].weight + T[p2].weight } } 算法中用到的三个函数略，实例（教材） §6.6.2 Huffman编码 1. 概念  数据压缩 可将数据文件压缩20%～90%,压缩效率取决于文件特征  编解码 54  编码方案(对字符集编码) 例 C = {a, b, c, d, e, f}, 设数据文件有10万字符，|C|=6 节约25%空间 a bcde f 编码总长 频度(万) 4.5 1.3 1.2 1.0 0.9 0.5 定长 000 001 010 011 100 101 30万 变长 0 101 100 111 1101 1100 22.4万