利用哈夫曼树写带全路径长度

【算法总结】哈夫曼树在⼀棵树中，从任意⼀个结点到达另⼀个结点的通路被称为路径，该路径上所需经过的边的个数被称为该路径的长度。

若树中结点带有表⽰某种意义的权值，那么从根结点到达该节点的路径长度再乘以该结点权值被称为该结点的带权路径长度。

树所有的叶⼦结点的带权路径长度和为该树的带权路径长度和。

给定 n 个结点和它们的权值，以它们为叶⼦结点构造⼀棵带权路径和最⼩的⼆叉树，该⼆叉树即为哈夫曼树，同时也被称为最优树。

给定结点的哈夫曼树可能不唯⼀，所以关于哈夫曼树的机试题往往需要求解的是其最⼩带权路径长度和。

回顾⼀下我们所熟知的哈夫曼树求法（原理很容易理解，就是把⼩的往下放）。

1.将所有结点放⼊集合 K。

2.若集合 K 中剩余结点⼤于 2 个，则取出其中权值最⼩的两个结点，构造他们同时为某个新节点的左右⼉⼦，该新节点是他们共同的双亲结点，设定它的权值为其两个⼉⼦结点的权值和。

并将该⽗亲结点放⼊集合 K。

重复步骤 2 或 3。

3.若集合 K 中仅剩余⼀个结点，该结点即为构造出的哈夫曼树数的根结点，所有构造得到的中间结点(即哈夫曼树上⾮叶⼦结点)的权值和即为该哈夫曼树的带权路径和。

为了⽅便快捷⾼效率的求得集合 K 中权值最⼩的两个元素，我们需要使⽤堆数据结构。

它可以以 O（logn）的复杂度取得 n 个元素中的最⼩元素。

为了绕过对堆的实现我们使⽤标准模板库中的相应的标准模板——优先队列。

：有4 个结点 a, b, c, d，权值分别为 7, 5, 2, 4，试构造以此 4 个结点为叶⼦结点的⼆叉树。

根据给定的n个权值{w1,w2,…,wn}构成⼆叉树集合F={T1,T2,…,Tn},其中每棵⼆叉树Ti中只有⼀个带权为wi的根结点,其左右⼦树为空.在F中选取两棵根结点权值最⼩的树作为左右⼦树构造⼀棵新的⼆叉树,且置新的⼆叉树的根结点的权值为左右⼦树根结点的权值之和.在F中删除这两棵树,同时将新的⼆叉树加⼊F中.重复,直到F只含有⼀棵树为⽌.(得到哈夫曼树)利⽤语句priority_queue<int> Q;建⽴⼀个保存元素为 int 的堆 Q，但是请特别注意这样建⽴的堆其默认为⼤顶堆，即我们从堆顶取得的元素为整个堆中最⼤的元素。

6.3哈夫曼树6.3.1基本术语1.路径和路径长度若在一棵中存在着一个结点序列k1 ,k2,…,kj，使得ki是k1+i 的双亲(1ji<≤)，则称此结点序列是从k1～kj的路径，因树中每个结点只有一个双亲结点，所以它也是这两个结点之间k 1～kj所经过的分支数称为这两点之间的路径长度，它等于路径上的结点数减1(实际就是边数)。

如在图5-19(a)所示的二叉树中，从树根结点L到叶子结点P的路径为结点序列L、M、S、P，路径长度为3。

(a) (b)(c) (d)图5-19 二叉排序树的删除2.结点的权和带权路径长度在许多应用中，常常将树中的结点赋上一个有着某种意义的实数，我们称此实数为该结点的权。

结点的带权路径长度规定为从树根结点到该结点之间的路径长度与该结点上权的乘积3.树的带权路径长度树的带权路径长度定义为树中所有叶子结点的带权路径长度这和，通常记为：2 WPL = ∑=n i i i lw 1其中n 表示叶子结点的数目，i w 和i l 分别表示叶子结点i k 的权值和根到i k 之间的路径长度 。

4.哈夫曼树哈夫曼(Huffman)树又称最优二叉树。

它是n 个带权叶子结点构成的所有二叉树中，带权路径长度 WPL 最小的二叉树。

因为构造这种树的算法是最早由哈夫曼于1952年提出的，所以被称之为哈夫曼树。

例如，有四个叶子结点a 、b 、c 、d ，分别带权为9、4、5、2，由它们构成的三棵不同的二叉树（当然还有其它许多种）分别如图5-20(a)到图5-20(c)所示。

b ac a b cd d c a b d(a) (b) (c)图5-20 由四个叶子结点构成的三棵不同的带权二叉树 每一棵二叉树的带权路径长度WPL 分别为：(a) WPL = 9×2 + 4×2 + 5×2 + 2×2 = 40(b) WPL = 4×1 + 2×2 + 5×3 + 9×3 = 50(c) WPL = 9×1 + 5×2 + 4×3 + 2×3 = 37其中图5-20(c)树的WPL 最小，稍后便知，此树就是哈夫曼树。

最优⼆叉树（哈夫曼树）的构建及编码参考：数据结构教程（第五版）李春葆主编⼀，概述1，概念 结点的带权路径长度： 从根节点到该结点之间的路径长度与该结点上权的乘积。

树的带权路径长度： 树中所有叶结点的带权路径长度之和。

2，哈夫曼树（Huffman Tree） 给定 n 个权值作为 n 个叶⼦结点，构造⼀棵⼆叉树，若该树的带权路径长度达到最⼩，则称这样的⼆叉树为最优⼆叉树，也称为哈夫曼树。

哈夫曼树是带权路径长度最短的树，权值较⼤的结点离根较近。

⼆，哈夫曼树的构建1，思考 要实现哈夫曼树⾸先有个问题摆在眼前，那就是哈夫曼树⽤什么数据结构表⽰？ ⾸先，我们想到的肯定数组了，因为数组是最简单和⽅便的。

⽤数组表⽰⼆叉树有两种⽅法： 第⼀种适⽤于所有的树。

即利⽤树的每个结点最多只有⼀个⽗节点这种特性，⽤ p[ i ] 表⽰ i 结点的根节点，进⽽表⽰树的⽅法。

但这种⽅法是有缺陷的，权重的值需要另设⼀个数组表⽰；每次找⼦节点都要遍历⼀遍数组，⼗分浪费时间。

第⼆种只适⽤于⼆叉树。

即利⽤⼆叉树每个结点最多只有两个⼦节点的特点。

从下标 0 开始表⽰根节点，编号为 i 结点即为 2 * i + 1 和 2 * i + 2，⽗节点为 ( i - 1) / 2，没有⽤到的空间⽤ -1 表⽰。

但这种⽅法也有问题，即哈夫曼树是从叶结点⾃下往上构建的，⼀开始树叶的位置会因为⽆法确定⾃⾝的深度⽽⽆法确定，从⽽⽆法构造。

既然如此，只能⽤⽐较⿇烦的结构体数组表⽰⼆叉树了。

typedef struct HTNode // 哈夫曼树结点{double w; // 权重int p, lc, rc;}htn;2，算法思想 感觉⽐较偏向于贪⼼，权重最⼩的叶⼦节点要离根节点越远，⼜因为我们是从叶⼦结点开始构造最优树的，所以肯定是从最远的结点开始构造，即权重最⼩的结点开始构造。

所以先选择权重最⼩的两个结点，构造⼀棵⼩⼆叉树。

然后那两个最⼩权值的结点因为已经构造完了，不会在⽤了，就不去考虑它了，将新⽣成的根节点作为新的叶⼦节加⼊剩下的叶⼦节点，⼜因为该根节点要能代表整个以它为根节点的⼆叉树的权重，所以其权值要为其所有⼦节点的权重之和。

哈夫曼树带权路径长度怎么算
不知道题主到底想问什么。

不过，我们可以根据哈夫曼树的构造推出一些共有的特性。

哈夫曼树是带权路径长度最短的二叉树，它最初是一堆离散的叶子（可以把它们都看成树），每把两棵树合在一起，就要添加一个分支结点。

因此在哈夫曼树中，只有度为2的分支结点和度为0的叶子结点（即最开始那堆离散的带权结点）。

而对于任意非空二叉树，度为0的结点总是比度为2的结点数多1个。

本题结点有215个，那么分支结点有[215/2]=107个，叶子有108个。

1.一般的,我们是可以用常规的构造哈夫曼树求带权路径长度。

树的带权路径长度
2.
带权路径长度WPL(Weighted Path Length)最小的二叉树,...
3.
在这里简单举个例子说一下: 题目: 给定6个字符
(a,b,c,d,e,f),...
4.
那么其带权路径长度WPL=(9+7+8)×2+4×3+(2+3)×4=80。

先构造哈夫曼树： 17 / \ 8 9 / \ 3 6 / \1 2所以带权路径长度WPL = （1+2）*3 + 6*2 + 8*1 = 29。

1. 数据结构的存储结构包括顺序、、索引和散列等四种。

2. 设关键字序列{7,12,26,30,47,58,66,70,82,90}，当用折半查找方法查找时，所需比较的次数为3次的关键字分别是。

3. 假定一个线性表为 {12, 23, 74, 55, 63, 40, 82, 36}，若按key%3条件进行划分，使得同一余数的元素成为一个子表，则包含74的子表长度为。

4. 和二分查找相比，顺序查找的优点是除了不要求表中数据元素有序之外，对结构也无特殊要求。

5. 设双向循环链表每一个结点结构为(data,llink,rlink),则结点*p的前驱结点的地址为。

6. n个顶点的连通无向图的生成树含有条边。

【答案】n-17. 在一个最大堆中，堆顶结点的值是所有结点中的。

8. 假定对长度n=50的有序表进行折半搜索，则对应的判定树中最底下一层的结点数为个。

9. 对于带头结点的链栈top，取栈顶元素的操作是。

【答案】*y=top->next->data 10. 假定一棵三叉树(即度为3的树)的结点个数为50，则它的最小高度为。

假定树根结点的深度为0。

11. 二维数组是一种非线性结构，其中的每一个数组元素最多有个直接前驱(或者直接后继)。

12. 在堆排序中，对任意一个分支结点进行调整运算的时间复杂度为。

13. 队列的删除操作在进行。

14. 设图G = (V, E)，V = {1, 2, 3, 4}, E = {<1, 2>, <1, 3>, <2, 4>, <3, 4>}，从顶点1出发，对图G进行广度优先搜索的序列有种。

15. 向一棵二叉搜索树中插入一个元素时，若元素的值小于根结点的值，则应把它插入到根结点的上。

16. 快速排序在平均情况下的时间复杂度为。

17. 由关键字序列{42,97,75,23,68,34}建成的最大堆是。

18. 对于关键字序列(12 , 13 , 11 , 18 , 60 , 15 , 7 , 18 , 25 , 100)，用筛选法建堆，必须从关键字为的结点开始。

一、实验目的1. 理解哈夫曼树的概念及其在数据结构中的应用。

2. 掌握哈夫曼树的构建方法。

3. 学习哈夫曼编码的原理及其在数据压缩中的应用。

4. 提高编程能力，实现哈夫曼树和哈夫曼编码的相关功能。

二、实验原理哈夫曼树（Huffman Tree）是一种带权路径长度最短的二叉树，又称为最优二叉树。

其构建方法如下：1. 将所有待编码的字符按照其出现的频率排序，频率低的排在前面。

2. 选择两个频率最低的字符，构造一棵新的二叉树，这两个字符分别作为左右子节点。

3. 计算新二叉树的频率，将新二叉树插入到排序后的字符列表中。

4. 重复步骤2和3，直到只剩下一个节点，这个节点即为哈夫曼树的根节点。

哈夫曼编码是一种基于哈夫曼树的编码方法，其原理如下：1. 从哈夫曼树的根节点开始，向左子树走表示0，向右子树走表示1。

2. 每个叶子节点对应一个字符，记录从根节点到叶子节点的路径，即为该字符的哈夫曼编码。

三、实验内容1. 实现哈夫曼树的构建。

2. 实现哈夫曼编码和译码功能。

3. 测试实验结果。

四、实验步骤1. 创建一个字符数组，包含待编码的字符。

2. 创建一个数组，用于存储每个字符的频率。

3. 对字符和频率进行排序。

4. 构建哈夫曼树，根据排序后的字符和频率，按照哈夫曼树的构建方法，将字符和频率插入到哈夫曼树中。

5. 实现哈夫曼编码功能，遍历哈夫曼树，记录从根节点到叶子节点的路径，即为每个字符的哈夫曼编码。

6. 实现哈夫曼译码功能，根据哈夫曼编码，从根节点开始，按照0和1的路径，找到对应的叶子节点，即为解码后的字符。

7. 测试实验结果，验证哈夫曼编码和译码的正确性。

五、实验结果与分析1. 构建哈夫曼树根据实验数据，构建的哈夫曼树如下：```A/ \B C/ \ / \D E F G```其中，A、B、C、D、E、F、G分别代表待编码的字符。

2. 哈夫曼编码根据哈夫曼树，得到以下字符的哈夫曼编码：- A: 00- B: 01- C: 10- D: 11- E: 100- F: 101- G: 1103. 哈夫曼译码根据哈夫曼编码，对以下编码进行译码：- 00101110111译码结果为：BACGACG4. 实验结果分析通过实验，验证了哈夫曼树和哈夫曼编码的正确性。

最优二叉树带权路径长度的最简计算作者：曹晓霞来源：《电脑知识与技术》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棵树看做一个森林。