#include<iostream>

#include<queue>

#include<map>

#include<string>

using namespace std;

class Node		//创建Node结点 

{

public:

	//构造函数：

	Node(char c,int count,Node *l=NULL,Node *r=NULL)		//默认子树为空 

	//当我们构建哈夫曼编码才进行设置子节点 

	:m_c(c),m_count(count),left(l),right(r)

	{} 

	

	bool operator <(const Node& node)const

	//重载'<' 在实现优先队列的时候 count 出现次数小的优先 

	{

		return m_count>node.m_count;

	}

	char m_c;			//存放字符 

	int m_count;		//字符出现的次数 依照此来排序 

	Node *left;

	Node *right;

};

void init(int nodenum,priority_queue<Node>&q)

{

	//现在开始初始化nodenum个结点

	char ch;

	int frequent;

	for(int i=0;i<nodenum;i++)

	{

	cout<<"请输入字符以及出现的次数（用空格分隔）TuT \n";

	cin>>ch;

	cin>>frequent;

	Node newnode(ch,frequent);		///创建结点 左右结点初始化为空  

	q.push(newnode);		//放进队列  结点值最小的优先 

	} 

}

void makehuffman(priority_queue<Node>&q)

{

	while(q.size()!=1)		//每次需要将两个结点来创建 

	{

		//创建树 每次取出来frequent最小的两个结点

		//然后创建他们的父节点放进queue中去

		Node *left=new Node(q.top());		//拷贝赋值 

		q.pop();  //最小的出队

		Node *right=new Node(q.top());

		q.pop();

		Node father('#',left->m_count+right->m_count,left,right);

		q.push(father); 

	}

}

void huffmancode(Node *root,string &curstr,map<char,string>& fins)

{

	string now=curstr;		//存储用于回溯

	 if(root->left==NULL||root->right==NULL)		//到达叶子节点了就return掉 

	 return ;

	//左子树

	curstr+="0"; 

	if(root->left->left!=NULL)

	{

		//下一个结点不是叶子结点

		huffmancode(root->left,curstr,fins); 

	}else {

		//左节点是叶子结点

		//放进fins哈希表中

		fins[root->left->m_c]=curstr;

		huffmancode(root->left,curstr,fins); 

	}

	//回溯 

	curstr=now;

	curstr+="1";

	if(root->right->right!=NULL)

	{

		//下一个结点不是叶子结点

		huffmancode(root->right,curstr,fins); 

	}else {

		//左节点是叶子结点

		//放进fins哈希表中

		fins[root->right->m_c]=curstr;

		huffmancode(root->right,curstr,fins); 

	}	

}

void print(map<char,string>& fins)

{

	//打印哈夫曼编码

	map<char,string>::iterator it=fins.begin();

	for(it=fins.begin();it!=fins.end();it++)

	{

		cout<<it->first<<":"<<it->second<<endl;	

	} 

}

int main()

{

	priority_queue<Node>q;		//直接用优先队列取最小值 

	cout<<"请输入总的需要编码的字符个数 TuT :\n";

	int nodenum;

	cin>>nodenum;

	init(nodenum,q);		//传引用过去 

	makehuffman(q);			//创建好树了 

	//下面实现编码

	//需要从根节点回溯搜索构建字符创 遇到叶子结点就退出

	//用map存储

	Node root=q.top();

	string curstr="";

	map<char,string>fins;		//创建哈希进行存储

	huffmancode(&root,curstr,fins); 	//传地址进去

	print(fins); 

}