数据结构——哈夫曼树

1.介绍

哈夫曼树就是树的带权路径长度（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最小。

2.算法

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

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

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

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

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

 3.特点

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

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

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

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

 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 

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/langs/798485.html