Huffman编码

最优二叉树(Huffman树)

首先给出路径和路径长度的定义:
从树的一个结点到另一个结点之间的分支构成这两点之间的路径,路径上的分支数目叫路径长度,树的路径长度为从根到每一个结点的路径长度之和。
带权路径长度:为该结点到跟的路径长度和结点上权的乘积。
树的带权路径:根到每一个结点的路径长度和结点上权的乘积之和。
其中带权路径长度WPL最小的二叉树称为最优二叉树或赫夫曼树.

如何构造Huffman树:
  1.根据给定的n个权值{w1,w2,w3,w4....wn}构造n颗二叉树集合f(t1,t2,t3...tn}
其中每颗二叉树ti中只有一个带权w1的根结点，其左右子树为空。
  2.在f中选取两颗权值最小的二叉树作为左右子树构造一棵新的二叉树,新二叉树的根的权值为左右子树权值之和
  3.在f中删除权值最小的二叉树,同时把新构造的二叉树加入到f中.
  4.重复2、3步骤直到f中只有一棵树为止。

以权值:5 6 3 8 7为例:




C代码实现：

#include <iostream>
using namespace std;

typedef struct{
	unsigned int weight;
	unsigned parent, lchild, rchild;
}HTNode, *HuffmanTree;

typedef char ** HuffmanCode;

//选取其中权值最小的两棵树
void Select(HuffmanTree &HT, int n, int &s1, int &s2)
{
	int i, min;
	min = 99999;
	for(i = 1; i <= n; i++)
	{
		if(min > HT[i].weight && HT[i].parent == 0)
		{
			s1= i;
			min = HT[i].weight;
		}
	}
	min = 99999;
    for(i = 1; i <= n; i++)
	{
		if(min > HT[i].weight && HT[i].parent == 0 && i != s1)
		{
			s2 = i;
			min = HT[i].weight;
		}
	}
}

void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n)
{
	int i, s1, s2, m;
	int start = 0, c, f;
	char *cd;
	if(n <= 1) return;
	m = (n << 1) - 1;
	HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode));
	for(i = 1; i <= n; ++i, ++w)  //构造n颗二叉树集合F={T1, T2, .... Tn},其中每颗树都只有一个带权为wi的根
	{
		HT[i].weight = *w;
		HT[i].parent = HT[i].lchild = HT[i].rchild = 0;
	}
	for( ;i <= m; ++i)
		HT[i].parent = HT[i].lchild = HT[i].rchild = HT[i].weight = 0; //初始化
	//构造Huffman中的2、3步。
	for(i = n + 1; i <= m; ++i)
	{
		Select(HT, i - 1, s1, s2);
		HT[s1].parent = i; HT[s2].parent = i;
		HT[i].lchild = s1; HT[i].rchild = s2;
		HT[i].weight = HT[s1].weight + HT[s2].weight;
	}
	HC = (HuffmanCode)malloc((n + 1) * sizeof(char *));
	cd = (char *)malloc(n * sizeof(char));
	cd[n - 1] = '\0';
	for(i = 1; i <= n; ++i)
	{
		int start = n - 1;
		for(c = i, f = HT[i].parent; f != 0; c = f, f = HT[f].parent)
			if(HT[f].lchild == c) cd[--start] = '0';
			else cd[--start] = '1';
		HC[i] = (char *)malloc((n - start) * sizeof(char)); //开辟内存空间
		strcpy(HC[i], &cd[start]);
	}
	free(cd);
	free(HT);
}

int main()
{
	HuffmanTree HT = NULL;
	HuffmanCode HC;
	int w[] = {5, 6, 3, 8, 7};
	HuffmanCoding(HT, HC, w, 5);
	for(int i =1; i <= 5; i++)
		cout<<HC[i]<<endl;
	return 0;
}