哈夫曼树及其编码

1、定义

• 树的带权路径长度（WPL）

将树的每一个节点附加一个权值，树中所有叶子节点的带权路径长度之和成为该树的带权路径长度。其计算公式如下：

• 哈夫曼树

带权路径长度WPL最小的二叉树成为哈夫曼树（或最优二叉树）。

• 哈夫曼编码

规定哈夫曼树种左分支为0，右分支为1，则从根节点到每个叶子节点所经过的分支对应的0和1组成的序列便为该节点对应字符的编码，这样的编码成为哈夫曼编码。

详细定义可查看博客：https://blog.csdn.net/l494926429/article/details/52494926

2、应用

哈夫曼树主要用于哈夫曼编码，可以起到压缩作用。

3、实现

（1）哈夫曼树的类型定义

typedef struct HTNode
{
	char data;
	double weight;
	int parent, left, right;
}HTNode;

（2）哈夫曼树的构造算法

//returns the huffman tree
HTNode* CreateHTNode(char* src, double* weight, int n)
{
	int h_n = 2 * n - 1;
	//init the huffman tree
	HTNode* h = new HTNode[h_n];
	for (int i = 0; i < n; i++)
	{
		h[i].data = src[i];
		h[i].weight = weight[i];
		h[i].parent = h[i].left = h[i].right = -1;
	}
	for (int i = n; i < h_n; i++)
		h[i].parent = -1;
	//create the huffman tree
	int min1_index, min2_index; //the index of the least two weight
	for(int i = n ; i < h_n; i++)
	{
		min1_index = min2_index = -1;
		for (int j = 0; j < i; j++)
		{
			if (h[j].parent == -1)
			{
				if (min1_index == -1 || h[j].weight < h[min1_index].weight)
				{
					min2_index = min1_index;
					min1_index = j;
				}
				else if (min2_index == -1 || h[j].weight < h[min2_index].weight)
				{
					min2_index = j;
				}
			}
		}
		h[i].weight = h[min1_index].weight + h[min2_index].weight;
		h[i].left = min1_index;
		h[i].right = min2_index;
		h[min1_index].parent = h[min2_index].parent = i;
	}
	return h;
}

（3）哈夫曼编码

//returns the huffman code of the huffman tree
map* CreateHCode(HTNode* h, int n)
{
	map* m = new map;
	for (int i = 0; i < n; i++)
	{
		string t = \"\";
		int k = i;
		while (h[k].parent != -1)
		{
			if (h[h[k].parent].left == k)
				t += \'0\';
			else
				t += \'1\';
			k = h[k].parent;
		}
		reverse(t.begin(), t.end());
		(*m)[h[i].data] = t;
	}
	return m;
}

4、测试

        假设用于通信的电文仅由 8 个字母组成,字母在电文中出现的频率分别为 0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10。试为这 8 个字母设计哈夫曼编码。

#include 
#include 
#include