|
最优二叉树概念 ．树的路径长度树的路径长度是从树根到树中每一结点的路径长度之和在结点数目相同的二叉树中完全二叉树的路径长度最短 ．树的带权路径长度(Weighted Path Length of Tree简记为WPL) 结点的权在一些应用中赋予树中结点的一个有某种意义的实数 结点的带权路径长度结点到树根之间的路径长度与该结点上权的乘积 树的带权路径长度(Weighted Path Length of Tree)定义为树中所有叶结点的带权路径长度之和通常记为 其中 n表示叶子结点的数目 wi和li分别表示叶结点ki的权值和根到结点ki之间的路径长度 树的带权路径长度亦称为树的代价 ．最优二叉树或哈夫曼树在权为wlw…wn的n个叶子所构成的所有二叉树中带权路径长度最小(即代价最小)的二叉树称为最优二叉树或哈夫曼树 【例】给定个叶子结点abc和d分别带权和构造如下图所示的三棵二叉树(还有许多棵)它们的带权路径长度分别为 (a)WPL=*+*+*+*= (b)WPL=*+*+*+*= (c)WPL=*+*+*+*= 其中(c)树的WPL最小可以验证它就是哈夫曼树 注意 ① 叶子上的权值均相同时完全二叉树一定是最优二叉树否则完全二叉树不一定是最优二叉树 ② 最优二叉树中权越大的叶子离根越近 ③ 最优二叉树的形态不唯一WPL最小 构造最优二叉树 ．哈夫曼算法 哈夫曼首先给出了对于给定的叶子数目及其权值构造最优二叉树的方法故称其为哈夫曼算法其基本思想是 ()根据给定的n个权值wlw…wn构成n棵二叉树的森林F={TT…Tn}其中每棵二叉树Ti中都只有一个权值为wi的根结点其左右子树均空 ()在森林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=ni<mi++){//共进行n次合并新结点依次存于T[i]中 SelectMin(Ti&p&p) //在T[．．i]中选择两个权最小的根结点其序号分别为p和p T[p]parent=T[p]parent=i TIi]child=p //最小权的根结点是新结点的左孩子 T[j]rchild=p //次小权的根结点是新结点的右孩子 T[i]weight=T[p]weight+T[p]weight } // end for } 上述算法中调用的三个函数【参见练习】 【例】以个权值为例执行CreateHuffmanTree求最优二叉树的过程【参见动画模拟】 |
