数据结构——哈夫曼树

哈夫曼树就是树的带权路径长度（即WPL）最小的树，WPL等于所有叶节点的带权路径长度之和。

而叶节点的带权路径长度等于该结点的路径长度与该结点的权值的乘积。

路径长度就是从根节点到该结点所经历的边数。而权值即赋给每个结点的一个数值。

（a）WPL =1*2+3*2+5*2+7*2=32

（b）WPL=1*3+3*3+5*2+7*1=29

（c）WPL=1*2+3*3+5*5+7*1=43

因此，（b）图的WPL最小。

假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：

(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；

(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；

(3)从森林中删除选取的两棵树，并将新树加入森林；

(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。

（1）有n个叶节点的哈夫曼树共有2n-1个结点。

（2）权值越大的叶节点，离根节点越近，权值越小的叶节点，离根节点越远。

（3）哈夫曼树是正则二叉树，只有度为0和2的结点。

（4）哈夫曼树任意非叶节点的左右子树交换后仍是哈夫曼树。因此，哈夫曼树不唯一。

 等长编码：每个对象二进制长度相等。

 不等长编码：每个对象二进制长度不相等。

等长编码虽然容易解码，但编码而成二进制长度太长。常用的子符编码居然也要和不常用的字符编码一样长。

对于不等长编码，对常用的字符进行相对较短的二进制编码表示，不常用的字符进行相对较长的二进制编码表示，减少了解码报文的二进制长度，但容易发生多种解码的方式。

比如说“00”可以表示‘E’，而‘0’可以表示‘G’，那么“00“即可解码成E，也可解码成GG。

因此，有了前缀码，即任何一个字符的编码都不是另一个字符的前缀的编码方式。

我们利用哈夫曼树，结点向左为0，向右为1，这样既能是前缀码易于解码，又能根据字符常用程度赋给其结点权值，其解码任务大大减少。

#pragma once
#include
template
class huffman_tree
{
	struct huffman_node
	{
		//哈夫曼树的字符结点是哈夫曼树的叶节点
		T data;//编码的字符
		int weight;//其权值
		//父节点位序,根据哈夫曼算法，利用parent是否为-1可以分辨一个结点是否已经用上，用上则不为-1
		int parent;
		int left, right;//左右孩子位序
		huffman_node() { weight = INT_MAX; parent = left = right = -1; }
	};
	struct huffman_code
	{
		T data;//编码字符
		std::string code;
		huffman_code() = default;//code初始化为“”
	};
	huffman_node* hf_tree;//顺序结构保存哈夫曼树
	huffman_code* hf_code;//顺序结构保存哈夫曼码
	int size;
	int select_min();//查找最小的结点,返回位序
public:
	huffman_tree(int init_size,const T* d,const int* w);
	~huffman_tree() { delete[]hf_tree; delete[]hf_code; }
	void print_code();
};
template
int huffman_tree::select_min()
{
	int w = INT_MAX;
	int loc = -1;
	for (int i = 0; i < 2*size-1; i++)
	{
		if (hf_tree[i].parent == -1 && hf_tree[i].weight < w)
		{
			w= hf_tree[i].weight;
			loc = i;
		}
	}
	hf_tree[loc].parent = INT_MAX;//该结点已不是在选择的范围内
	return loc;
}
template
huffman_tree::huffman_tree(int init_size, const T* d, const int* w)
{
	//初始化过程
	size = init_size;
	hf_tree = new huffman_node[2 * size - 1];//结点存放处
	hf_code = new huffman_code[size];//编码存放处
	//size-1到2*size-2存放叶节点，0到size-2结点不存放字符
	for (int i = 0; i < size; i++)
	{
		hf_tree[i + size - 1].data = d[i];
		hf_tree[i + size - 1].weight = w[i];
		hf_code[i].data = d[i];
	}
	//进行哈夫曼树的建立,我们保证0位序是根节点便于下面的编码
	for (int i = size-2; i >=0; i--)
	{
		int p = select_min(), q = select_min();
		hf_tree[p].parent = hf_tree[q].parent = i;
		hf_tree[i].weight = hf_tree[p].weight + hf_tree[q].weight;
		//根据第四个性质，以下顺序可以颠倒
		hf_tree[i].left = p;
		hf_tree[i].right = q;
	}
	//进行哈夫曼树的编码
	for (int i = size-1; i < 2*size-1; i++)
	{
		int p = hf_tree[i].parent;
		int s = i;
		while (s)
		{
			if (hf_tree[p].left == s)
				hf_code[i - size + 1].code = '0' + hf_code[i - size + 1].code;
			else
				hf_code[i - size + 1].code = '1' + hf_code[i - size + 1].code;
			s = p;
			p = hf_tree[s].parent;
		}
	}
}
template
void huffman_tree::print_code()
{
	for (int i = 0; i