哈夫曼树的概念以及构造

1、哈夫曼树最优二叉树的概念以及构造哈夫曼树产生的背景在实际生活和生产应用中,我们往往会遇到综合比拟一系列的离散量的问题；比方说车站根据包裹的重量以及旅途的长短来确定携带行李的价格,或者我们根据一定的重量范围来给一箱铁球进行分类.这一类问题的解决思路是：1、 根据实际需要划分出分类的标准；2、 按一定的顺序算法将实际的数据归到相应的类别里.一般情况下,我们所确定的分类标准并不能保证每一类的数据量是平均分配的；也就是说,由于每一类数据出现的概率不同,造成当采用不同的算法时所需的运算次数的不同.当然,在实际生产生活中, 我们更希望得到一种最快,最简洁同时也不会产生歧义的算法.在 这个背景下,哈夫曼树以

2、及哈夫曼算法应运而生.准备概念森林：森林由nn>=2个二叉树组成,它的遍历可以归结为二叉树的遍历,即以其中一 棵二叉树的根结点为森林的“根结点 ,之后每一个二叉树的根结点都依次相连,由此组成 了 一个大的二叉树森林向二叉树的转化.路径和路径的长度：从树中的一个结点到另一个结点之间的分支构成这两个结点之间的 路径,路径上的 分支数目称作路径长度.对于一个二叉树,其在第 n层上的结点到根结点的路径长度为n-1.结点的权：根据应用的需要给树的结点赋的权值.结点的带权路径长度：从根结点到该结点的路径长度与该几点权的乘积.树的带权路径长度WPL：树中所有 叶子的带权路径长度之和.哈夫曼二叉树及其构

3、造有了以上的概念,哈夫曼二叉树的定义就变得水到渠成.所谓哈夫曼二叉树最优二叉树,就是带权路径长度最小的二叉树注意这里的带权路径.由于树的带权路径长度只与所有叶子的带权路径长度有关,所以对于一个哈夫曼树,其真正其作用的数据是存在于叶子上.再回到问题产生的根源.我们说在现实的分类中,每一类数据出现的概率不尽相同；这些数据出现的概率可以被看做哈夫曼树中叶子的权值.为了获取最短的路径, 也就是带权路径长度最短的二叉树,我们希望那些权值低的数据拥有相对较长的对根结点的路径长度.根据这一思路,我们可以从一群离散的数据中构造出一颗哈夫曼树,具体的算法如下：1、根据给定的n个权值w1 ,w2 ,.,wn 构造

4、n棵二叉树的集合 F=T1 ,T2 ,.,Tn , 其中每棵二叉树 Ti中只有一个带权为 wi的根结点,其左右子树均空.2、在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树,且置新 的二叉树的根 结点的权值为其左、右子树上根结点的权值之和.3、在F中删除这两棵树,同时将新得到的二叉树参加F中.4、重复2和3,直到F中只含一棵树为止.这棵树便是最优二叉树.例如,有权值分别为 5、10、15、20、25、40的结点,根据以上算法构造出一个哈夫 曼树.1、 取这六个树中最小的两个树5、10连成一个二叉树,其权值为 15;此时森林里的树变为 15 5、10、15、20、25、40.2、

5、 取这五个树中最小的两个树15 5、10、15,构成一个新的二叉树 305、10、15;此时森立里的树变为20、25、30 5、10、15、40.3、 继续上述过程,得到一个新的二叉树 45 20、25;此时的森林变为 30 5、10、 15、 40、 45 20、 25.4、 继续得到二叉树705、10、15、40;那么森林里只剩下两棵树：705、10、15、40与 45 20、25.5、 最后将这两棵二叉树合并成为一棵二叉树115 5、10、15、40、20、25,完成了哈夫曼树的构造.6、 计算 WPL=5+10*4+15*3+40*2+20+25*2=275 .以上便是哈夫曼树最优二叉树的相关概念和构造方法.根据最后二叉树可以解决类 似于文章开