哈夫曼树与哈夫曼编码

哈夫曼树的重要定理
对于具有n个叶子节点的哈夫曼树，一共需要2*n-1个节点。。

因为对于二叉树来说，有3种类型节点，即度数（节点拥有的子树的个数被称为节点的度）为2的节点，和度数为1的节点和度数为0的节点。而哈夫曼树的非叶子节点都是由两个节点合并产生，所以不会出现度数为1的节点。而生成的非叶子节点的个数为叶子节点个数-1，因此n个叶子节点的哈夫曼树，一共需要2*n-1个节点。

#include
using namespace std;
typedef struct
{
	unsigned int weight;      //结点的权值
	unsigned int parent, lcd, rcd;  //结点的双亲，左孩子和右孩子的下标
}HTNode,*HuffmanTree;
typedef char** HuffmanCode;

//在HT[1...i-1]中选择parent=0且weight最小的两个结点
int minl(HuffmanTree t, int i)
{
	 //函数void select()调用
	int j, flag;
	unsigned int k = 1e9;//取K为不小于可能的值
	for (j = 1; j <= i; j++)
	{
		if (t[j].weight < k && t[j].parent == 0)
			k = t[j].weight, flag = j;
		t[flag].parent = 1;
		return flag;
	}
}

void Select(HuffmanTree t, int i, int& s1, int& s2)
{
	//s1为最小的两个值中序号小的那个
	int j;
	s1 = minl(t, i);
	s2 = minl(t, i);
	if (s1 > s2)
	{
		j = s1;
		s1 = s2;
		s2 = j;
	}
}

//w存放n个字符的权值（均>0）构造哈夫曼树HT，并取出n个字符的哈夫曼树编码HC
void HuffmanCoding(HuffmanTree& HT, HuffmanCode& HC, int* w, int n)
{
	if (n <= 1)
		return;
	int m = 2 * n - 1;
	int i, s1, s2;
	HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode));
	HuffmanTree p;
	for (p = HT + 1, i = 1; i <= n; ++i, ++p, ++w)
	{
		p->weight = *w;
		cout << *w << " ";
		p->parent = 0;
		p->lcd = 0;
		p->rcd = 0;
	}
	cout << endl;
	for (i = n + 1; i <= m; ++i, ++p)
	{
		p->weight = 0;
		p->parent = 0;
		p->lcd = 0;
		p->rcd = 0;
	}
	cout << "Try to print the initial huffman Tree table." << endl;

	for (int i = 1; i <= m; ++i)
	{
		cout << HT[i].weight << " " << HT[i].parent << " " << HT[i].lcd << " " << HT[i].rcd << endl;
	}

	for (int i = 1; i <= m; ++i)
	{
		Select(HT, i - 1, s1, s2);
		HT[s1].parent = i;
		HT[s2].parent = i;
		HT[i].lcd = s1;
		HT[i].rcd = s2;
		HT[i].weight = HT[s1].weight + HT[s2].weight;
	}

	cout << "Try to print the created huffman Tree table." << endl;

	for (int i = 1; i <= m; ++i)
	{
		cout << HT[i].weight << " " << HT[i].parent << " " << HT[i].lcd << " " << HT[i].rcd << endl;
	}
	
	HC = (HuffmanCode)malloc((n + 1) * sizeof(char*));
	char* cd = (char*)malloc(n * sizeof(char));
	cd[n - 1] = '';
	int start, c, f;
	for (i = 1; i <= n; i++)
	{
		start = n - 1;
		for (c = i, f = HT[i].parent; f != 0; c = f, f = HT[f].parent)
		{
			if (HT[f].lcd == c)
				cd[--start] = '0';
			else
				cd[--start] = '1';
		}
		HC[i] = (char*)malloc((n - start) * sizeof(char));
		strcpy(HC[i], &cd[start]);
		free(cd);
	}
}

void HuffmanCoding2(HuffmanTree& HT, HuffmanCode& HC, int* w, int n)
{
	//w存放n个字符的权值（均>0）构造哈夫曼树HT，并求出n个字符的哈夫曼树编码HC
	if (n <= 1)
		return;
	int m = 2 * n - 1;
	int i, s1, s2;
	HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode));
	HuffmanTree p;
	for (p = HT + 1, i = 1; i <= n; i++, p++, w++)
	{
		p->weight = *w;
		p->parent = 0;
		p->lcd = 0;
		p->rcd = 0;
	}
	for (i = n + 1; i <= m; i++, p++)
	{
		p->weight = 0;
		p->parent = 0;
		p->lcd = 0;
		p->rcd = 0;
	}

	for (i = n + 1; i <= m; i++)
	{
		Select(HT, i - 1, s1, s2);
		HT[s1].parent = i;
		HT[s2].parent = i;
		HT[i].lcd = s1;
		HT[i].rcd = s2;
		HT[i].weight = HT[s1].weight + HT[s2].weight;
	}
	HC = (HuffmanCode)malloc((n + 1) * sizeof(char*));
	int q = m;
	char* cd = (char*)malloc(n * sizeof(char));
	int cdlen = 0;
	for (i = 1; i <= m; ++i)
		HT[i].weight = 0;
	while (q)
	{
		if (HT[q].weight == 0)
		{
			HT[q].weight = 1;
			if (HT[q].lcd != 0)
			{
				q = HT[q].lcd;
				cd[cdlen++] = '0';
			}
			else if (HT[q].rcd == 0)
			{
				HC[q] = (char*)malloc((cdlen + 1) * sizeof(char));
				cd[cdlen] = '';
				strcpy(HC[q], cd);
			}
		}
		else if (HT[q].weight == 1)
		{
			HT[q].weight = 2;
			if (HT[q].rcd != 0)
			{
				q = HT[q].rcd;
				cd[cdlen++] = '1';
			}
		}
		else
		{
			HT[q].weight = 0;
			q = HT[q].rcd;
			cd[cdlen++] = '1';
		}
	}
}

int main()
{
	HuffmanTree HT;
	HuffmanCode HC;
	int n;
	int data[1000];

	while (scanf("%d", &n) != EOF)
	{
		for (int i = 1; i <= n; ++i)
		{
			scanf("%d", &data[i]);
		}
		cout << endl;
		HuffmanCoding2(HT, HC, data + 1, n);
		for (int i = 1; i <= n; ++i)
		{
			printf("%sn", HC[i]);
		}
		delete(HC);
		delete(HT);
	}
	return 0;
}

构建哈夫曼树

原理

 构造思路

1.初始化：首先申请2n个单元，然后循环2n-1次，从1号单元开始，依次将1至2n-1所有单元中的双亲，左右孩子的下标都初始化为0；最后循环n次，输入前n个单元中叶子结点的权值

2.创建树：循环n-1次，通过n-1次的选择、删除与合并来创建哈夫曼树。选择是从当前森林中选择双亲为0且权值最小的两个树根结点s1和s2的权值和作为一个新结点的权值依次存入到数组的第n+1之后的单元中，同时记录这个新结点左孩子的下标为s1，右孩子的下标为s2。

void CreateHuffmanTree(HuffmanTree& HT, int n)
{
	//构造哈夫曼树HT的初始化工作
	if (n <= 1)return;
	int m = 2 * n - 1;
	int i, s1, s2;
	HT = new HTNode[m + 1];   //0号单元未用，所以需要动态分配m+1个单元，HT[m]表示根结点
	for (i = 1; i <= m; ++i)
	{
		HT[i].parent = 0;
		HT[i].lcd = 0;
		HT[i].rcd = 0;
	}
	for (int i = 1; i <= n; ++i)  //输入前n个单元中叶子结点的权值
		cin >> HT[i].weight;

	//构造哈夫曼树
	for (i = n + 1; i <= m; ++i)
	{
		Select(HT, i - 1, s1, s2);
		//在HT[k](1<=k<=i-1)中选择两个其双亲域为0且权值最小的结点，并返回它们在HT中的序号s1和s2
		HT[s1].parent = i;
		HT[s2].parent = i;
		//得到新结点i，从森林中删除s1,s2，将s1和s2的双亲域由0改为i
		HT[i].lcd = s1;
		HT[i].rcd = s2;  //s1，s2分别作为i的左右孩子
		HT[i].weight = HT[s1].weight + HT[s2].weight;  //i的权值作为左右孩子权值之和

	}
}

根据哈夫曼树求哈夫曼编码

①分配存储n个字符编码的编码表空间HC，长度为n+1; 分配临时存储每个字符编码的动态数组空间cd，cd[n-1]置为'（哈夫曼树最高n-1层，最多只有n-1个分支，即编码最多只有n-1位）。
②逐个求解n个字符的编码，循环n次，执行以下操作：
●设置变量start用于记录编码在cd中存放的位置，start初始时指向最后，即编码结束符位置n-1；
●设置变量c用于记录从叶子结点向上回溯至根结点所经过的结点下标，c初始时为当前待编码字符的下标i，f用于记录i的双亲结点的下标；
●从叶子结点向上回溯至根结点，求得字符i的编码，当f没有到达根结点时，循环执行以下操作：

回溯一次start向前指一个位置，即--start；
若结点c是f的左孩子，则生成代码0，否则生成代码1，生成的代码0或1保存在cd[start]中；
继续向上回溯，改变c和f的值。

●根据数组cd的字符串长度为第i个字符编码分配空间HC[i]，然后将数组cd中的编码复制到HC[i]中。
③释放临时空间cd

void CreatHuffmanCode(HuffmanTree HT, HuffmanCode& HC, int n)
{
	char* cd = (char*)malloc(n * sizeof(char));
	HC = new char* [n + 1];        //分配存储n个字符编码的编码表空间
	cd = new char[n];              //分配临时存放每个字符编码的动态数组空间
	cd[n - 1] = '';              //编码结束符
	int start, i,c,f;
	for (i = 1; i <= n; ++i)              //逐个字符求哈夫曼编码
	{
		start = n - 1;             //start开始时指向最后，即编码结束符位置
		c = i; f = HT[i].parent;   //f指向结点c的双亲结点
		while (f != 0)                //从叶子结点开始向上回溯，直到根结点
		{
			--start;               //回溯一次,start向前指一个位置
			if (HT[f].lcd == c)cd[start] = '0';  //结点c是f的左孩子，则生成代码0
			else cd[start] = '1';                //结点c是f的右孩子，则生成代码1
			c = f; f = HT[f].parent;             //继续向上回溯
		}                                        //求出第i个字符的编码
		HC[i] = new char[n - start];             //为第i个字符编码分配空间
		strcpy(HC[i], &cd[start]);               //将求得的编码从临时空间cd复制到HC的当前行中
	}
	delete cd;                    //释放临时空间
}

文件的编码和解码