数据结构-怀化学院期末题（1321）

构建哈夫曼树

题目描述：

根据给定的叶结点字符及其对应的权值创建哈夫曼树。
输入：
第一行为叶子结点的数目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;
}

?