P1382 哈夫曼树 - 题解

登录注册上岸

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

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

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

2024年3月13日 17:09

哈夫曼树题解：最小栈做法

P1382

回复 0 | 赞 1 | 浏览 1.5k

#include <bits/stdc++.h> using namespace std; int main() { int n, x; while(cin>>n){ priority_queue<int, vector<int>, greater<int>> q; // 定义存储整数的最小堆 for (int i = 0; i < n; i++) { &n...

2024年2月14日 20:40

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

P1382

回复 2 | 赞 14 | 浏览 2.0k

先排序，最小的两个数在前面，weight权值为非叶子节点值的总和 #include <stdio.h> void Sort(int a[],int n) { int i,j,t; for(i = 0; i < n-1; i++) for(j = 1; j < n-i; j++) if(a[j] < a[j-1]) { t = a[j]; a[j] = a[j-1]; a[j-1] = t; } } int main() { int t,i,n,a[...

DestinyCares+++

2024年2月23日 15:37

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

P1382

回复 0 | 赞 5 | 浏览 1.8k

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

2024年1月20日 10:27

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

P1382

回复 0 | 赞 2 | 浏览 1.4k

#include <bits/stdc++.h> using namespace std; int main(){ //迭代求带权路径和 int n,leaf; while(cin>>n){ priority_queue<int> q; for(int i=0;i<n;i++) { cin>>leaf; q.push(-leaf);//存入相反数 } int res=0; while(q.size()>1){ int leaf1 = q.top(); ...

2023年8月22日 14:36

哈夫曼树题解：C++ priority_queue

P1382

回复 3 | 赞 1 | 浏览 1.8k

C++ #include <iostream> #include <queue> #include <vector> using namespace std; int main(){ int n; while(cin >> n){ priority_queue<int, vector<int>, greater<int>> q; int num; for(int i = 0; i < n; i++){ ...

2023年8月9日 19:58

哈夫曼树题解：优先队列

P1382

回复 0 | 赞 0 | 浏览 1.3k

合并果子同个思路 #include<bits/stdc++.h> using namespace std; int main() { int n; while(cin>>n) { int x; priority_queue<int,vector<int>,greater<int> > q;//优先队列从小到大排序，从小输出。 for(int i=0;i<n;i++) { ...

2023年6月15日 13:15

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

P1382

回复 0 | 赞 0 | 浏览 1.7k

没有使用运算符重载和优先队列来维护树集合的有序性，用了笨办法实现有序插入（先排序后逐个对比） #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 | 浏览 3.2k

#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 | 赞 8 | 浏览 7.4k

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

2022年3月16日 21:23

P1382

回复 0 | 赞 1 | 浏览 6.2k

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

1
2
3

题目哈夫曼树

题解数量22

发布题解在线答疑

热门题解

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

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

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

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

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

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

7 哈夫曼树题解：

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

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

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