构建哈夫曼树
题目描述:
根据给定的叶结点字符及其对应的权值创建哈夫曼树。
输入:
第一行为叶子结点的数目n(1<=n<=100)。第二行为一个字符串,包含n个字符,每个字符对应一个叶子结点,第三行为每个叶子结点的概率(即权值),要求根据各叶结点构造哈夫曼树。构造哈夫曼树的原则是先两个最小的,构造一个父结点,其中最小的结点为左孩子,次小的为右孩子,如果两个最小的叶结点相等,则取排在前一个位置的为左孩子。
输出:
哈夫曼树的权值,左孩子,右孩子及其对应的父亲,相邻数据之间用空格隔开;
输入样例:
5
abcde
15 25 15 20 25
输出样例:
15 0 0 6
25 0 0 7
15 0 0 6
20 0 0 7
25 0 0 8
30 1 3 8
45 4 2 9
55 5 6 9
100 7 8 0
代码:
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<string.h>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<map>
using namespace std;
typedef pair<int,int> PII;
const int N = 1e5 + 10;
int w[N],a[N],n;
int l[N],r[N],fu[N];
int cnt,idx = 1;
bool cmp(int x,int y){
if(w[x] != w[y]) return w[x] > w[y];
return x > y;
}
int main(){
cin >> n;
string q;
cin >> q;
for(int i = 1;i <= n;i ++){
cin >> w[i];
a[cnt ++] = i;
idx ++;
}
while(cnt > 1){
sort(a,a + cnt,cmp);
int num1 = a[cnt - 1];
int num2 = a[cnt - 2];
a[cnt - 2] = idx ++;
w[a[cnt - 2]] = w[num1] + w[num2];
l[a[cnt - 2]] = num1;
r[a[cnt - 2]] = num2;
fu[num1] = a[cnt-2];
fu[num2] = a[cnt-2];
cnt --;
}
for(int i = 1;i < idx;i ++)
cout << w[i] << ' ' << l[i] << ' ' << r[i] << ' ' << fu[i] << endl;
return 0;
}
?