|
构造最优二叉树 哈夫曼算法 哈夫曼首先给出了对于给定的叶子数目及其权值构造最优二叉树的方法故称其为哈夫曼算法其基本思想是 ()根据给定的n个权值w l w …w n 构成n棵二叉树的森林F={T T …T n }其中每棵二叉树T i 中都 只有一个权值为w i 的根结点其左右子树均空 ()在森林F中选出两棵根结点权值最小的树(当这样的树不止两棵树时可以从中任选两棵)将这两棵树合并成一棵新树为 了保证新树仍是二叉树需要增加一个新结点作为新树的根并将所选的两棵树的根分别作为新根的左右孩子(谁左谁右无关紧要 )将这两个孩子的权值之和作为新树根的权值 ()对新的森林F重复()直到森林F中只剩下一棵树为止这棵树便是哈夫曼树 用哈夫曼算法构造哈夫曼树的过程见【 动画演示 】 注意 ① 初始森林中的n棵二叉树每棵树有一个孤立的结点它们既是根又是叶子 ② n个叶子的哈夫曼树要经过n次合并产生n个新结点最终求得的哈夫曼树中共有n个结点 ③ 哈夫曼树是严格的二叉树没有度数为的分支结点 哈夫曼树的存储结构及哈夫曼算法的实现 () 哈夫曼树的存储结构 用一个大小为n的向量来存储哈夫曼树中的结点其存储结构为 #define n //叶子数目 #define m *n//树中结点总数 typedef struct { //结点类型 float weight; //权值不妨设权值均大于零 int lchildrchildparent; //左右孩子及双亲指针 }HTNode; typedef HTNode HuffmanTree[m]; //HuffmanTree是向量类型 注意 因为C语言数组的下界为故用表示空指针树中某结点的lchildrchild和parent不等于时它们分别是该结点的左 右孩子和双亲结点在向量中的下标 这里设置parent域有两个作用其一是使查找某结点的双亲变得简单;其二是可通过判定parent的值是否为来区分根与非根结 点 ()哈夫曼算法的简要描述 在上述存储结构上实现的哈夫曼算法可大致描述为(设T的类型为HuffmanTree) ()初始化 将T[m]中n个结点里的三个指针均置为空(即置为)权值置为 ()输人 读人n个叶子的权值存于向量的前n个分量(即T[n])中它们是初始森林中n个孤立的根结点上的权值 ()合并 对森林中的树共进行n次合并所产生的新结点依次放人向量T的第i个分量中(n≤i≤m)每次合并分两步 ①在当前森林T[i]的所有结点中选取权最小和次小的两个根结点[p]和T[p]作为合并对象这里≤pp≤i ② 将根为T[p]和T[p]的两棵树作为左右子树合并为一棵新的树新树的根是新结点T[i]具体操作 将T[p]和T[p]的parent置为i 将T[i]的lchild和rchild分别置为p和p 新结点T[i]的权值置为T[p]和T[p]的权值之和 注意 合并后T[pl]和T[p]在当前森林中已不再是根因为它们的双亲指针均已指向了T[i]所以下一次合并时不会被选中为合并对象 哈夫曼算法模拟演示过程【 参见动画模拟 】 ()哈夫曼算法的求精 void CreateHuffmanTree(HuffmanTree T) {//构造哈夫曼树T[m]为其根结点 int ipp; InitHuffmanTree(T); //将T初始化 InputWeight(T); //输入叶子权值至T[n]的weight域 for(i=n;i SelectMin(T，i-1，&p1，&p2); //在T[0..i-1]中选择两个权最小的根结点，其序号分别为p1和p2 T[p1].parent=T[p2].parent=i; TIi].1child=p1; //最小权的根结点是新结点的左孩子 T[j].rchild=p2; //次小权的根结点是新结点的右孩子 T[i].weight=T[p1].weight+T[p2].weight; } // end for } 上述算法中调用的三个函数【参见练习】。tW.WinGwIt.COm 【例】以7个权值：7，5，1，4，8，10，20为例，执行CreateHuffmanTree求最优二叉树的过程 |
