构造赫夫曼树和赫夫曼编码

//哈夫曼树
#include
#include
using namespace std;
typedef struct {
	int weight;
	int parent, lchild, rchild;
}HTNode,*HuffmanTree;
typedef char ** HuffmanCode;
void Select(HuffmanTree HT, int len, int& s1, int& s2)
{
	int min1 = 0x3f3f3f3f, min2 = 0x3f3f3f3f; //赋予最大值
	for (int i = 1; i < len; i++)
	{
		if (HT[i].weight < min1 && HT[i].parent == 0)
		{
			min1 = HT[i].weight;
			s1 = i;
		}
	}
	int temp = HT[s1].weight;
	HT[s1].weight = 0x3f3f3f3f;
	for (int i = 1; i <= len; i++)
	{
		if (HT[i].weight < min2 && HT[i].parent == 0)
		{
			min2 = HT[i].weight;
			s2 = i;
		}
	}
	HT[s1].weight = temp;  //恢复原来的值
}
//构造哈夫曼树
void CreatHuffmanTree(HuffmanTree& HT, int n)
{
	int m, s1, s2;
	if (n <= 1)
	{
		return;
	}
	m = 2 * n - 1;  // 哈夫曼树没有度为1的结点，所以n个叶子结点的哈夫曼树有2n-1个结点
	HT = new HTNode[m + 1]; // 0号单元未用，动态分配m+1单元，HT[m]表示根结点
	for (int i = 1; i <= m; i++)
	{
		HT[i].parent = 0;
		HT[i].lchild = 0;
		HT[i].rchild = 0;
	}
	cout << "请输入叶子结点的权值：" << endl;
	for (int i = 1; i <= n; i++)
	{
		cin >> HT[i].weight;
	}
	for (int 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;
	}
}
void CreatHuffmanCode(HuffmanTree HT, HuffmanCode& HC, int n)
{
	int start, c, f;
	HC = new char* [n + 1];
	char* cd = new char[n];
	cd[n - 1] = '';
	for (int i = 1; i <= n; i++)
	{
		start = n - 1;
		c = i;
		f = HT[i].parent;
		while (f != 0)
		{
			start--;  //从叶子结点开始向上回溯，直到根结点，回溯一次start向前指一个位置
			if (HT[f].lchild == c)
			{
				cd[start] = '0';  //结点c是f的左孩子，则生成0
			}
			else
			{
				cd[start] = '1';  //结点c是f的右孩子，则生成1
			}
			c = f;
			f = HT[f].parent;
		}
		HC[i] = new char[n - start];
		strcpy(HC[i], &cd[start]);
	}
	delete []cd;  //释放临时空间
}
void show(HuffmanTree HT, HuffmanCode HC, int n)
{
	for (int i = 1; i <= n; i++)
	{
		cout << HT[i].weight << "编码为" << HC[i] << endl;
	}
}
int main()
{
	HuffmanTree HT;
	HuffmanCode HC;
	int n;
	cout << "请输入叶子的结点个数：n";
	cin >> n;
	CreatHuffmanTree(HT, n);
	CreatHuffmanCode(HT,HC, n);
	show(HT, HC, n);
	return 0;
}