P1382 哈夫曼树 - 题解

登录注册上岸

以下题解仅供学习参考使用。

抄袭、复制题解，以达到刷AC率/AC数量或其他目的的行为，在N诺是严格禁止的。

N诺非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看N诺社区规则。

2022年2月6日 18:46

哈夫曼树的带权路径长度总结

P1382

回复 1 | 赞 1 | 浏览 8.1k

//哈夫曼树的带权路径长度 //总结 //法一：①先对权值从小到大排序。 //②选两个最小的加起来成为一个新结点，而这两个最小的值是新结点的左右子结点。 //③两个老的结点去掉，新的结点放入再次排序然后重复过程②。 //④直到完全生成一棵树。 //⑤计算的时候，只计算那些初始权值里面有的值，把它乘以深度 //（和传统说的深度不一样，是传统说的深度减一）加起来就是路径长度。 //法二：哈夫曼树也可以通过小根堆实现。小根堆每次弹出两个值，然后将二者的和再插入小根堆中。 #include <iostream> #include<stdio.h> ...

2022年2月4日 13:28

哈夫曼树带权路径长度（WPL）的简便算法

P1382

回复 0 | 赞 2 | 浏览 14.9k

首先，结点的带权路径长度 = 从根结点到该结点之间的路径长度 X 该结点的权，但是，计算WPL其实可以不用刻意算出每个结点的到根节点的路径长度，我们只需在构造哈夫曼时除根节点以外的节点权值加和就好了，因为在加和过程中越靠下的节点被加了多次，这个次数其实也就是它离根节点的路径长度，具体的证明可以参考这篇文章：哈夫曼树带权路径长度简便算法 #include<iostream> #include<queue> using namespace std; struct node { int x; // 定义优先队列的比较关系，...

1
2
3

题目哈夫曼树

题解数量22

发布题解在线答疑

热门题解

1 哈夫曼树题解：最简单易懂的思路，AC

2 哈夫曼树题解：优先队列——排坑

3 哈夫曼树题解：求WPL的两种方法，图片详解

4 哈夫曼树题解：哈夫曼树的值等于所有非叶结点值的和+小根堆实现

5 哈夫曼树题解：C题解简单思路

6 哈夫曼树题解(priority_queue解决)：

7 哈夫曼树题解：

8 1382 哈弗曼树树的带权路径+优先级队列两种方法

9 哈夫曼树题解：新手简单易懂

10 哈夫曼树题解：c++ priority_queue实现