文档介绍：?构造 Huffman 树的方法—— Huffman 算法?构造 Huffman 树步骤?根据给定的 n个权值{ w1,w2, …… wn },构造 n棵只有根结点的二叉树,令起权值为 wj ?在森林中选取两棵根结点权值最小的树作左右子树,构造一棵新的二叉树,置新二叉树根结点权值为其左右子树根结点权值之和?在森林中删除这两棵树,同时将新得到的二叉树加入森林中?重复上述两步,直到只含一棵树为止,这棵树即哈夫曼树例a 7b 5c 2d 4a 7b 5c 2d 4 6a 7b 5c 2d 4 6 11 a 7b 5c 2d 4 6 11 18 例 w={5, 29, 7, 8, 14, 23, 3, 11} 514 297823311 14 2978231135 887 15 14 292335 8111135 8 19 14 292387 15 1135 8 19 29231487 15 29 291487 15 291135 8 19 23 42 1135 8 19 23 42291487 15 29 58 1135 8 19 23 42291487 15 29 58 100 ? Huffman 算法实现 ?一棵有 n个叶子结点的 Huffman 树有 2 n-1 个结点?采用顺序存储结构——一维结构数组?结点类型定义 typedef struct { int weight; int parent,lchild,rchild ;} HTNode ;4 2 5 7 weight parent lchild rchild 1234567 a 7b 5c 2d 4 6 11 18 例a 7b 5c 2d 4 ht[i ] abcd for(p =HT+1,i=1;i<= n;++i,++p,++w ) * p={ * w,0,0,0}; for(;i <= m;++I,++p ) * p={0,0,0,0}; 0000 0000 0000 0004 0002 0005 0007 weight parent lchild rchild 1234567 a 7b 5c 2d 4 6 11 18 ht[i ] abcd for (i=n+1; i<=m; i++) { // 建哈夫曼树 Select(HT , i-1,s1,s2); HT[s1].parent = i; HT[s2].parent = i; HT[i].lchild = s1; HT[i].rchild = s2; HT[i].weight = HT[s1].weight + HT[s2].weight; }0000 0000 4306 0054 0052 0005 0007 weight parent lchild rchild ********** 520 11 4366 0054 0052 0065 0007 weight parent lchild rchild 1234567a 7b 5c 2d 4 6 11 18 abcd abcd610 18 527 11 4366 0054 0052 0065 0077 weigh