数据结构作业--哈夫曼树

先用优先队列每次取出两个小的数字，然后变成一个数字，加入队列。建树采用数组实现。

#include <bits/stdc++.h>
#define Pair pair<int,string>
using namespace std;
struct node
{
	int data;
	double a;
	int left;
	int right;
}tree[1005];
map<string, int>mp;
auto cmp = [](int q, int w) {
	if (tree[q].a != tree[w].a)
		return tree[q].a > tree[w].a;
	return tree[q].data < tree[w].data;
};
int n, cnt = 1;
priority_queue<int, vector<int>, decltype(cmp) >q(cmp);
void Init()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d%lf", &tree[cnt].data, &tree[cnt].a);
		q.push(cnt++);
	}
}
void Build()
{
	while (q.size() != 1)
	{
		node rot;
		rot.left = q.top();
		q.pop();
		rot.right = q.top();
		q.pop();
		rot.a = tree[rot.left].a + tree[rot.right].a;
		rot.data = ' ';
		tree[cnt] = rot;
		q.push(cnt++);
	}
}
void BFS(int rot)
{
	//BFS
	queue<int>qq;
	qq.push(rot);
	while (!qq.empty())
	{
		int temp = qq.front();
		qq.pop();
		if (tree[temp].left == 0 && tree[temp].right == 0)
			printf("%d ", tree[temp].data);
		if (tree[temp].left != 0)
			qq.push(tree[temp].left);
		if (tree[temp].right != 0)
			qq.push(tree[temp].right);
	}
}
void Code(int rot)
{
	//BFS
	cout << endl << "哈夫曼编码为:" << endl;
	queue<Pair>qq;
	qq.push(Pair{ rot,"" });
	while (!qq.empty())
	{
		Pair temp = qq.front();
		qq.pop();
		if (tree[temp.first].left == 0 && tree[temp.first].right == 0)
		{
			printf("%d : ", tree[temp.first].data);
			cout << temp.second << endl;
			mp[temp.second] = tree[temp.first].data;
		}
		if (tree[temp.first].left != 0)
			qq.push(Pair{ tree[temp.first].left ,temp.second + '0' });
		if (tree[temp.first].right != 0)
			qq.push(Pair{ tree[temp.first].right,temp.second + '1' });
	}
	cout << endl;
}
void Decode()
{
	cout << "输入一个编码：" << endl;
	string s, t;
	cin >> s;
	int len = s.size();
	for (int i = 0; i < len; i++)
	{
		t += s[i];
		if (mp[t] != 0)
		{
			printf("%d", mp[t]);
			t.clear();
		}
	}
}
int main()
{
	Init();
	Build();
	int rot = q.top();
	q.pop();
	//BFS(rot);
	Code(rot);
	Decode();
}
/*
8
4 25
8 5
5 4
3 20
2 10
6 4
7 2
1 30
11010001001110011010110001111
*/