说起哈夫曼树及其思想，最经典也是最早接触的当属合并果子了。哈夫曼反映的经典贪心思想与其数学逻辑在初学者中独占一席，虽然其思想简单易懂，但其代码实现起来并不简单易懂，网上的代码大多都是用指针、内定义函数、地址符等来实现的，像我这种蒟蒻总是容易看得一头雾水，十分的不友好，考虑到哈夫曼树通常是静态的，所以我就敲出来了稍微易于理解一点的静态实现代码。
以下以哈夫曼编码为例
题目链接
上代码：
#include <bits/stdc++.h>
using namespace std;
int n,cnt;
struct haf{//哈夫曼树的每个节点
int f;//指向父亲
int num;//权值
int xh;//序号（在tr数组中的下标）
int l,r;//左右孩子
string ans;//用于存储哈夫曼编码
inline bool operator < (const haf &b)const{//重载运算符，以便使用优先队列
if(num!=b.num)return num>=b.num;
return ch>b.ch;
}
}tr[10005];
void dfs(int p,string now){//深搜遍历得出编码，p为当前节点，now为以记录了的编码
if(tr[p].l==-1&&tr[p].r==-1){
tr[p].ans=now;
return ;
}
dfs(tr[p].l,now+"0");
dfs(tr[p].r,now+"1");
}
int main() {
while(cin>>n){
priority_queue <haf> q;
cnt=n;
for(int i=1;i<=n;i++){
cin>>tr[i].ch>>tr[i].num;
tr[i].xh=i;
tr[i].l=tr[i].r=tr[i].f=-1;//f,l,r,全部初始化为-1
q.push(tr[i]);
}
for(int i=1;i<n;i++){
haf x=q.top();
q.pop();
haf y=q.top();
q.pop();//这里满足：y.num>x.num
tr[++cnt].num=x.num+y.num;
tr[cnt].xh=cnt;
if(x.num==y.num&&x.ch>y.ch)swap(x,y);//题目要求：x.ch<=y.ch
tr[cnt].r=y.xh;
tr[cnt].l=x.xh;
tr[cnt].ch=y.ch;
tr[y.xh].f=cnt;
tr[x.xh].f=cnt;
tr[cnt].f=-1;
q.push(tr[cnt]);//q里的元素为从大到小
/*
q2=q;
while(q2.size()){
cout<<q2.top().num<<' ';
q2.pop();
}
cout<<endl;
*/
//上面的代码是可视化模拟哈夫曼合并过程功能的代码段
}
/*
for(int i=1;i<=cnt;i++)cout<<"序号："<<i<<" ch:"<<tr[i].ch<<" num:"<<tr[i].num<<" l:"<<tr[i].l<<" r:"<<tr[i].r<<" f:"<<tr[i].f<<endl;
*/
//上面一段是检查哈夫曼树各个节点的情况的功能的代码段
dfs(cnt,"");
for(int i=1;i<=n;i++){
if(i!=1)cout<<endl;
cout<<tr[i].ch<<":"<<tr[i].ans;
}
cout<<endl;
}
return 0;
}
补充：
静态化的哈夫曼这里用到了优先队列来选择权值最小的两个结点，优点是代码短，但要重载运算符，还要去学priority_queue。还有种方法是用小根堆，优点是复杂度比优先队列忧、不需要拓展其它知识（除非你没学过堆），但这样的话代码又要多一倍，而且实现起来十分麻烦。
代码中的dfs函数（也就是求哈夫曼编码的函数）使用了自顶向下的方法遍历，得到编码的遍历方法也可以是自底向上，两种方法各有优劣（想想具体是哪些优劣？），根据实际情况而定。