P1382 哈夫曼树 - 题解

登录注册上岸

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

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

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

2023年6月15日 13:15

哈夫曼树题解：构建哈夫曼树（笨办法）

P1382

回复 0 | 赞 0 | 浏览 1.1k

没有使用运算符重载和优先队列来维护树集合的有序性，用了笨办法实现有序插入（先排序后逐个对比） #include<bits/stdc++.h> using namespace std; #define rep(i,s,e) for(int i=s;i<e;i++) #define per(i,s,e) for(int i=s;i>e;i--) typedef struct Tnode { int data; Tnode* lchild=NULL; Tnode* rchild=NULL; } Tnode; ...

2023年3月21日 00:48

构建哈夫曼树

P1382

回复 0 | 赞 0 | 浏览 2.6k

#include<bits/stdc++.h> using namespace std; typedef struct Node { int weight; int parent, lchild, rchild; }Node,HaffumanTree[20000]; void createHaffumanTree(int weight[],int n,HaffumanTree t) { for (int i = 0; i < 2 * n...

2022年7月31日 20:08

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

P1382

回复 0 | 赞 5 | 浏览 6.4k

首先需要明确哈弗曼树的几个概念：权：节点的值；出现的概率的大小节点路径长度：从0开始，根节点长度为0，根节点的子节点路径长度为1，以此类推树的路径长度：所有叶节点路径长度之和节点带权路径长度：该节点路径长度*该节点权树的带权路径长度：所有节点路径长度*该节点权这题的目标是求树的带权路径长度。计算树的带权路径长度，本来是计算是所有节点深度*权的和，但是这里通过迭代累加，也能实现乘法的效果。在最下面的节点，累加次数最多，即相当于乘的数值最大。关键代码： ...

2022年3月16日 21:23

P1382

回复 0 | 赞 1 | 浏览 5.4k

#include<iostream> #include<queue> using namespace std; int main() { int n, val, total; priority_queue<int, vector<int>,greater<int> > qu; while (cin >> n) { ...

2022年2月6日 18:46

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

P1382

回复 1 | 赞 1 | 浏览 7.3k

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

2022年2月4日 13:28

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

P1382

回复 0 | 赞 2 | 浏览 13.9k

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

1
2

题目哈夫曼树

题解数量16

热门题解

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

2 哈夫曼树题解：优先队列 + 迭代求带权路径和

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

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

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

6 哈夫曼树

7 哈夫曼树题解：直接优先队列

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

9 哈夫曼树题解：优先队列

10 构建哈夫曼树