#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);
}