论文投稿_医学论文投稿_核心期刊,职称论文投稿发表_论文部落

　　1951年，正在麻省理工学院求学的哈夫曼需要完成一份学期报告，导师RobertM.Fano给他们的学期报告的题目是，寻找最有效的二进制编码。哈夫曼在研究过已有编码后发现，始终无法证明哪个编码是最有效的，因此他很快放弃了这些研究，而进行了新的探索，最后他终于突破了现有编码的算法，发现了基于有序频率二叉树编码，哈夫曼使用了一种自底向上的方法来构建二叉树，这一方法很快被证明是最有效的。

　　在实际应用中，我们也通常要考虑如何设计一棵二叉树，使得执行路径最短，即算法的效率最高，而这正是哈夫曼所研究的最有效二进制编码，因此最优二叉树又被称为哈夫曼树。

　　一、哈夫曼树的定义

　　哈夫曼树，是指对于一组带有确定权值的叶结点，构造的具有最小带权路径长度的二叉树。论文发表所谓结点带权路径长度，指的是从根结点到某个结点的路径长度与该结点所带的权值的乘积，而树的带权路径长度则指的是树中所有叶子结点的带权路径长度之和，通常记作：WPL=

　　假设有n个权值{W1，W2，……，Wn}，试构造有n个叶子结点的二叉树，每个叶子结点拥有一个权值W，则其中带权路径长度WPL最小的二叉树，称为最优二叉树或哈夫曼树。

　　二、哈夫曼树的建立

　　根据哈夫曼树的定义，哈夫曼树的构造方法如下：

　　1.根据给定的n个权值{W1，W2，……，Wn}构成n棵二叉树的集合F={T1，T2，……，Tn}，其中每一棵二叉树Ti中只有一个带权为Wi的根结点，其左右子树均空。

　　2.在F中选出两棵根结点权值最小的树作为一棵新的二叉树的左右子树，且置新二叉树根结点的权值为两棵子树根结点的权值之和。

　　3.从F中删去这两棵树，同时把新二叉树加入F中。

　　4.重复2和3，直到F中只有一棵树为止，此树便是哈夫曼树。

　　从哈夫曼树的构造方法，我们可以推导出构造哈夫曼树的算法实现原理：基于哈夫曼树没有度为1的结点，根据二叉树性质，可推导知一棵有n个叶子的哈夫曼树共有2n-1个结点，我们可定义大小为2n-1的一维数组存储哈夫曼树。这个数组的前n个位置存放的为已知的叶子结点，后（n-1）个位置存放的为动态生成的树内结点。在算法的大循环过程中，就是根据位置i前面的已知结点找出结点权值最小的两个结点，然后根据这两个结点构造出位置i的新的父结点，即一棵新树的根结点。

　　三、哈夫曼编码

　　哈夫曼树的一个经典应用就是哈夫曼编码。在数据传输与存储中，经常需要将不同形式的信息转换成二进制字符串，这个转换过程就是编码。在实际应用中，信息的各个字符出现频率是不一样的，有的字符出现频率高，有的字符出现频率低，为了降低所传递信息的编码长度，通常做法是用短的编码来表示高频率字符，用长的编码来表示低频率字符。哈夫曼编码就是这样一种经典编码，哈夫曼编码的优点是任一字符ci的编码不会是另一字符cj（ci≠cj）的编码的前缀，这样电文在译码时不会出现混淆。

　　哈夫曼编码是一种变长的编码方案，编码过程就根据不同字符的频率（相当于权值）构造出哈夫曼树，然后求叶子节点到根节点的路径，其中节点的左孩子路径标识为0，右孩子路径标识为1。

　　哈夫曼编码的算法实现所采用的方法是从叶子节点向上遍历到根结点，从哈夫曼树根结点开始，左孩子路径标示为0，右孩子路径标示为1，一直到达叶子结点为止，然后将从树根沿每条路径到达叶子结点的代码排列起来，便得到了哈夫曼编码。