前言

写哈夫曼树太 suffering 了，还好有 dp 。

哈夫曼树理论部分

详见： 树论 、哈夫曼树&二叉搜索树

哈夫曼树代码部分

意外的死机故障不可避。

这是原版（未完成）：

#include <map>
#include <queue>
#include <iostream>
using namespace std;

struct node
{
	int t;
	int c;
	node* fa;
	node* lc;
	node* rc;
	bool operator<(const node& other) const {
        return t > other.t; // 注意：这是为了创建最小堆
    }
};
string str;
priority_queue <node> q;

void make()
{
	while (q.size() > 1)
	{
        node fst = q.top(); q.pop();
        node sec = q.top(); q.pop();

        node* nw = new node;
        nw->t = fst.t + sec.t;
        nw->c = -1; 
        nw->lc = new node(fst);
        nw->rc = new node(sec);
        nw->lc->fa = nw;
        nw->rc->fa = nw;

        q.push(*nw);
    }
}

int main()
{
	cin >> str;
	string snt = str;
	map <int, int> used;
	for (char ch : str)
	{
		used[static_cast<int>(ch)]++;
	}
	for (auto i : used)
	{
		node nd = {};
		nd.c = i.first;
		nd.t = i.second;
		nd.fa = nd.lc = nd.rc = NULL;
		q.push(nd);
	}
	make();
	cout << q.top().t;
	return 0;
}

本来想重写的，但是既然找到了，为什么不用呢？

这是最终版：

#include <map>
#include <queue>
#include <iostream>
using namespace std;

struct node
{
	int t;
	int c;
	node* fa;
	node* lc;
	node* rc;
	bool operator<(const node& other) const {
        return t > other.t;
    }
};
string str, code[1005];
priority_queue <node> q;

void make()
{
	while (q.size() > 1)
	{
        node fst = q.top(); q.pop();
        node sec = q.top(); q.pop();

        node* nw = new node;
        nw->t = fst.t + sec.t;
        nw->c = -1; 
        nw->lc = new node(fst);
        nw->rc = new node(sec);
        nw->lc->fa = nw;
        nw->rc->fa = nw;

        q.push(*nw);
    }
}

void dfs(node* u, string bit)
{
	if (u -> lc == nullptr && u -> rc == nullptr)
	{
		code[u -> c] = bit;
	}
	if (u -> lc)dfs(u -> lc, bit + '0');
	if (u -> rc)dfs(u -> rc, bit + '1');
}

int main()
{
	int n = 0;
	cin >> str;
	string snt = str;
	map <int, int> used;
	for (char ch : str)
	{
		used[static_cast<int>(ch)]++;
	}
	for (auto i : used)
	{
		n++;
		node nd = {};
		nd.c = i.first;
		nd.t = i.second;
		nd.fa = nd.lc = nd.rc = NULL;
		q.push(nd);
	}
	make();
	node root = q.top();
	dfs(&root, "");
	for (int i = 1; i <= 256; i++)
	{
		if (code[i] != "")
		{
			cout << char(i) << " : " << code[i] << "\n";
		}
	}
	for (char ch : str)
	{
		cout << code[static_cast<int>(ch)];
	}
	return 0;
}

太好了，以后就用哈夫曼编码发消息

原理：

1. 先将输入的字符串按照出现次数存储；
2. 每次取出最小的两个节点，合并权值；
3. DFS 生成编码；
4. 输出编码。