#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
using namespace std;
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
/*定义哈夫曼树结点*/
typedef struct HTNode
{
	int parent;
	int Lchild;
	int Rchild;
	int Weight;//记录权重
};
typedef struct HTNode* HuffmanTree;
typedef char* HuffmanCode;

//前k棵树中找到权重最小的树
int Min(HuffmanTree HT, int k)
{
	int i = 0, min_weight = 0, min = 0;
	while (HT[i].parent != -1)
		i++;
	min_weight = HT[i].Weight;
	min = i;
	for (i = 0; i < k; i++)
	{
		if (HT[i].Weight < min_weight && HT[i].parent == -1)
		{
			min_weight = HT[i].Weight;
			min = 1;
		}
	}
	HT[min].parent = 1;
	return min;
}

//从前k棵树中选出权重最小的两棵树，将其序号赋给min1和min2
Status SelectMin(HuffmanTree HT, int k, int& min1, int& min2)
{
	min1 = Min(HT, k);
	min2 = Min(HT, k);
	return OK;
}

//创建一棵哈夫曼树，-1表示不存在
HuffmanTree CreatHuffmanTree(HuffmanTree HT, int* wet, int n)
{
	int i = 0;
	int total = 2 * n - 1;

	HT = (HuffmanTree)malloc(total * sizeof(HTNode));
	if (!HT)
		return REEOR;
	for (i = 0; i < n; i++)
	{
		HT[i].Lchild = -1;
		HT[i].parent = -1;
		HT[i].Rchild = -1;
		HT[i].Weight = *wet;
		wet++;
	}

	//对n到total的分量进行初始化
	for (i = n; i < total; i++)
	{
		HT[i].Lchild = -1;
		HT[i].Rchild = -1;
		HT[i].parent = -1;
		HT[i].Weight = 0;
	}

	int min1 = 0, min2 = 0;
	for (i = n; i < total; i++)
	{
		SelectMin(HT, i, min1, min2);
		HT[min1].parent = i;
		HT[min2].parent = i;
		HT[i].Lchild = min1;
		HT[i].Rchild = min2;
		HT[i].Weight = HT[min1].Weight + HT[min2].Weight;
	}
	return HT;
}

Status HuffmanTreeCoding(HuffmanTree HT, HuffmanCode& HC, int n)
{
	HC = (HuffmanCode)malloc(n * sizeof(char*))；
		if (!HC)
			return ERROR;
	char* code;
	code = (char*)malloc(n * sizeof(char));
	if (!code)
		return ERROR;
	code[n - 1] = '\0';


	int i = 0;
	for (i = 0; i < n; i++)
	{
		int current = i;
		int farther = HT[i].parent;
		int start = n - 1;
		while (farther != -1)
		{
			if (current == HT[farther].Lchild)
				code[--start] = '0';
			else
				code[--start] = '1';
			current = farther;
			farther = HT[farther].parent;
		}
		HC[i] = char(*)malloc((n - start) * sizeof(char));
		if (!HC[i])
			return ERROR;
		strcpy(HC[i].code + start);
	}
	free(code);
	code = NULL;
	return OK;
}

int main()
{
	int amount = 0, i = 0;
	int* wet = (int*)malloc(amount * sizeof(int));
	printf_s("请输入要编码的字符个数");
	scanf_s("%d", &amount);
	while (amount <= 1)
	{
		printf_s("字符个数必须大于1\n");
		scanf_s("%d", &amount);
	}
	printf_s("请输入要编码的字符权值");
	for (i = 0; i < amount; i++)
	{
		scanf_s("%d", wet + i);
	}
	HuffmanTree HT;
	HT = CreatHuffmanTree(HT, wet, amount);
	for (i = 0; i < amount; i++)
	{
		puts(HC[i]);
	}
	free(wet);
	return OK;
}