哈夫曼树怎么画_带权路径长度怎么算_哈夫曼树带权路径长度

摘要:最优二叉树在很多领域有着广泛的应用,它是一种带权路径长度最短的树,该文在哈夫曼提出的构造最优二叉树的基础上进行一些改进,并得出一种最简计算最短带权路径长度的方法。

关键词:哈夫曼树;带权路径长度;算法

中图分类号: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为叶子结点的个数 */

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-31855-1.html