最优二叉树带权路径长度的最简计算
作者：曹晓霞
来源：《电脑知识与技术》2010年第08期
        摘要:最优二叉树在很多领域有着广泛的应用,它是一种带权路径长度最短的树,该文在哈夫曼提出的构造最优二叉树的基础上进行一些改进,并得出一种最简计算最短带权路径长度的方法。
        关键词:哈夫曼树;带权路径长度;算法
        中图分类号:TP311文献标识码:A文章编号:1009-3044(2010)08-1940-02
哈夫曼编码树的带权路径长度
        数据结构课程中的最优二叉树又称哈夫曼树,是一类带权路径长度最短的树[1],在很多领域都有着广泛的应用。其中哈夫曼编码就是一种应用广泛且非常有效的数据压缩技术,该技术一般可将数据文件压缩掉20%至90%,其压缩效率主要取决于被压缩文件的特征。利用哈夫曼树的最短路径长度还可以很容易地求出给定字符集及其概率(或频度)分布的最优前缀码。另外,哈夫曼树还经常应用在最佳判断过程中,利用哈夫曼树的最短带权路径长度,使程序中的比较次数
尽可能少而使程序的运行效率提高。而且在各类计算机专业的考试中,哈夫曼树也作为经典算法常常出现。但笔者在多年的教学经验中发现,学生在哈夫曼树的建立和计算带权路径长度中经常出现很多问题,一是无法很快地构建哈夫曼树,而且对于最小带权路径长度的计算更是不知所措,同时编写出的哈夫曼树的算法时间复杂度很大。为此,本文介绍一种最简的建立哈夫曼树的过程和计算带权路径长度的简单方法。
        1 最优二叉树的建立和算法
        1.1 最优二叉树的概念
        设一棵二叉树有n个叶子结点,每个叶子结点拥有一个权值W1,W2, …,Wn,从根结点到每个叶子结点的路径长度分别为L1, L2,…, Ln,那么树的带权路径长度为每个叶子的路径长度与该叶子权值乘积之和, 通常记作:
        而在有相同叶子结点权值构成的二叉树中,带权路径长度各不相同,在n个带树叶子结点构成的所有二叉树中,带权路径长度WPL最小的二叉树称为最优二叉树。
        1.2 最优二叉树的建立
        最优二叉树的构造思想是由哈夫曼得出的,下面先介绍哈夫曼提出的思想方法:
        对于已知的一组叶子的权值W1,W2,…,Wn:
        1) 首先把n个叶子结点看作n棵树,每棵树的树根为叶子结点的权值,把这n棵树看做一个森林。
        2) 在森林中把权值最小和次小的两棵树合并成一棵树,该树根结点的权值是两棵子树权值之和。这时森林中还有n-1棵树。
        3) 重复第(2)步直到森林中只有一棵树为止[2]。此树就是最优二叉树,也称哈夫曼树。
        为了能方便快速地计算出带权路径长度,现要求叶子结点用方框表示,树根结点用圆圈表示,圆圈中的数值是叶子结点权值的总和,现给一组(n=4)具体权值为2,4,5,8的序列,下边是构造哈夫曼树的具体过程:首先,将2,4,5,8看成是4棵只有根结点的子树,构成一个森林,如图1(a)所示。然后将最小的权值2和次小的权值4组合成一棵子树,根结点为2+4=6,这时还有三棵子树,根结点分别为6,5,8,如图1(b)所示。再将图中最小的权值5和次小的权值6组合成一棵子树,根结点为11,如图1(c)所示。最后只剩下两棵子树,权值分别为8和11,将它们组合成一棵子树,根
结点的权值为19,此时,森林中只剩下最后一棵树,这棵树就是哈夫曼树。
        上面所构造的哈夫曼树是不唯一的,它的形状可以发生变化,但是它的最短路径长度只有一个,且每个根结点都有两棵子树,是一棵严格的二叉树,在这棵二叉树中,权值越大的叶子结点离根结点就越近。
        1.3 构造最优二叉树的算法
        为了简化程序,本文采用顺序存储结构的方法给出最优二叉树的存储结构。
        typedef struct
        {int data;
        int lch,rch;
        itn tag;
        } Nodeh;
        设t为指哈夫曼树的根结点(在此是数组元素)的指针,算法如下:
        int huffmah (struct node r[20])
        { scanf("n=%d", &n); /* n为叶子结点的个数 */
        for(j=1; j
        { scanf("%d", &r[j].data);
        r[j].tag=0; r[j].lch=0;r[j].rch=0;
        }
        i=0;
        while (i
        { x1=0; m1 =32767;/* m1是最小值单元, x1为下标号 */
        x2 =0; m2 =32767;/* m2为次小值单元, x2为下标号 */
        for(j=1;j
        { if ((r[j].data
        {m2 = m1; x2 = x1;
        m1 =r[j].data; x1 =j;}
        else if ((r[j].data
        { m2=r[j].data;
        x2 =j;
        }
        }
        r[x1].tag=1;r[x2].tag=1;i++;
        r[n+i].data=r[x1].data+r[x2].data; /* m1 + m2 */
        r[n+i].tag=0;r[n+i].lch=x1;r[n+i].rch= x2 ;
        }
        t=2*n-1;
        return (t);
        } /*end */
        该程序采用了数组的存储方式,是因为最优二叉树中没有度为1的结点。由二叉树的性质可以知道度为0的结点的个数等于度为2的结点的个数加1,即为n0=n2+1,所以总的结点数为n0+n2,也就是2n0-1,所以定义数组的大小就为2n-1。在这个程序中有一个二重循环,内循环的平均循环次数为O(n),外循环大约为n次,所以该算法的时间复杂度为O(n2)。
        2 最短带权路径长度的计算
        设一棵二叉树有n个叶子结点,每个叶子结点拥有一个权值W1,W2,…,Wn,从根结点到每个叶子结点的路径长度分别为L1,L2,…,Ln,那么树的带权路径长度为每个叶子的路径长度与
该叶子权值乘积之和[1],记为WPL。则上面构造的最优二叉树的最短带权路径长度为:WPL=(2+4)*3+5*2+8*1=36。
        在上面的计算过程中,要求学生掌握关于路径和路径长度的概念。树中两个结点之间的路径由一个结点到另一个结点的分支构成。两结点之间的路径长度是路径上分支的数目。树的路径是从根结点到每一个结点的路径长度之和。对于这些概念,在计算带权路径长度的过程中,学生又经常会将它们与树的深度、层次等概念混淆在一起,因此,在计算带权路径长度的过程中也就经常出现错误。
        事实上,上面所构造的这棵哈夫曼树的最短带权路径长度可以很简便的算出结果,也就是将圆圈当中的数值累加起来就可以,而不必理解关于路径和路径长度的概念。比如2和4的叶子结点的权值,在哈夫曼树当中第一次被累加成了7,在第二次时被累加成了11,第三次被累加成了19,所以2和4的叶子结点的权值被累加了3次,刚好相当于(2+4)*3的结点,其它的叶子权值也依此类推计算。所以哈夫曼树的简单计算如下:WPL=19+11+6=36。
        3 结束语
        本文给出了一种静态建立哈夫曼树的方法和算法,并提出一种最简计算最小带权路径长度的方法,在实际的教学过程中学生接受快,容易理解,而且计算方便,比书本上常用的方法更简单。
        参考文献:
        [1] 严蔚敏,吴伟民.数据结构(C语言版)[M].北京:清华大学出版社,2007:144-146.
        [2] 杨秀金,张红梅.数据结构[M].2版.西安.西安电子科技大学出版社,2006:128-129.

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。