题目:
哈弗曼编码大家一定很熟悉吧(不熟悉也没关系,自己查去。。。)。现在给你一串字符以及它们所对应的权值,让你构造哈弗曼树,从而确定每个字符的哈弗曼编码。当然,这里有一些小规定:

1.规定哈弗曼树的左子树编码为0,右子树编码为1;

2.若两个字符权值相同,则ASCII码值小的字符为左孩子,大的为右孩子;

3.创建的新节点所代表的字符与它的左孩子的字符相同;

4.所有字符为ASCII码表上32-96之间的字符(即“ ”到“`”之间的字符)。

输入包含多组数据(不超过100组)
每组数据第一行一个整数n,表示字符个数。接下来n行,每行有一个字符ch和一个整数weight,表示字符ch所对应的权值,中间用空格隔开。
输入数据保证每组测试数据的字符不会重复。

对于每组测试数据,按照输入顺序输出相应的字符以及它们的哈弗曼编码结果

这道题很坑,空格也能作为输入,坑了很长时间……

#include <stdio.h>
#include <math.h>

#include <algorithm>
#include <map>
#include <string>
#include <vector>

using namespace std;

typedef struct BiTNode{
	char data;
	int weight;
	BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

bool compareBiTNode(BiTNode *a, BiTNode *b)
{
	if(a->weight == b->weight) { // 根据题目要求,如果权重一样,那么ascii码小的是左孩子 
		return a->data > b->data;
	}
	
	return a->weight > b->weight;
}

void insertIntoVector(vector<BiTNode*> &a, BiTNode *node) // 这里的a一定要用引用,不然加入没有用 
{
	int i;
	
	// 这句的逻辑表达式有点复杂
	// 是为了保证如果权重一样,那么ascii码小的是左孩子 
	for(i = 0;
			i < a.size()
			&& (a[i]->weight > node->weight || (a[i]->weight == node->weight && a[i]->data > node->data));
				i++);
	a.insert(a.begin() + i, node);
}

// 如果用&a,而不是a,那么a是引用,调用完这个函数后会破坏原来vector里的内容 
BiTree constructHaffmanTree(vector<BiTNode*> a) 
{
	BiTNode *l, *r;
	BiTNode *f;
	
	if(a.size() == 0) {
		return NULL;
	}
	
	sort(a.begin(), a.end(), compareBiTNode); // 从大到小排列 
	
	while(a.size() > 1) {
		// 顺序不能乱,保证如果权重一样,ascii码小的是左孩子 
		l = a[a.size() - 1];
		a.pop_back(); // 删除最后一个元素 
		r = a[a.size() - 1];
		a.pop_back(); // 删除最后一个元素 
		
		f = new BiTNode();
		f->lchild = l;
		f->rchild = r;
		f->data = l->data;
		f->weight = l->weight + r->weight;
		
		insertIntoVector(a, f);
	}
	
	return a[0];
}

void traversalHaffmanTree(BiTree t, string code, map<BiTNode*, string> &m)
{
	if(t == NULL) {
		return;
	}
	
	if(t->lchild == NULL && t->rchild == NULL) { // 遇到叶子节点,保存code 
		m.insert(pair<BiTNode*, string>(t, code));
		return;
	} else {
		traversalHaffmanTree(t->lchild, code + "0", m);
		traversalHaffmanTree(t->rchild, code + "1", m);
	}
}

int main() {
	vector<BiTNode*> a;
	BiTNode *p;
	BiTree t;
	map<BiTNode*, string> m;
	
	int n, w;
	char c;
	
	while(scanf("%d", &n) != EOF) {
		while(n--) {
			getchar(); // 读取换行符,不保存 
			c = getchar(); // 读取真正要计算的字符,因为可能有空格,所以不能用scanf 
			
			scanf("%d", &w);
			
			p = new BiTNode();
			
			p -> data = c;
			p -> weight = w;
			
			a.push_back(p);
		}
		
		// printf("constructing\n");
		t = constructHaffmanTree(a);
		// printf("constructed, t = %d\n", t->weight);
		
		traversalHaffmanTree(t, "", m);
		
		for(int i = 0; i < a.size(); i++) {
			printf("%c:%s\n", a[i]->data, m[a[i]].c_str());
		}
		
		a.clear(); // 每次要记得清空 
	}
	
	return 0;
}