#include?
#include?
#include?
#include?

#define?MAX_CHAR_KINDS?128//字符種類最大值。。
#define?MAX_NUM?1000//字符串最大長度。。
FILE?*in?*ou;

typedef?struct?TreeNode
{
	int?weight;
	int?id;
	short?isLeaf;
	char?data;
	char?bin;//0或者1。。?
	struct?TreeNode?*parent;
	struct?TreeNode?*lChild?*rChild;
}?TreeNode;

typedef?struct
{
	char?data;
	char?code[MAX_CHAR_KINDS];
}?Code;

//字符串倒置。。?
void?ReverseStr（char?*str）
{
????int?i;
????char?c;
????int?length;
????length?=?strlen（str）;
????for?（i?=?0;?i?????{
????????c?=?str[length?-?1?-?i];
????????str[length?-?1?-?i]?=?str[i];
????????str[i]?=?c;
????}
}

void?PreOrderTraverse（TreeNode?*t）
{
????if?（（t->rChild?==?NULL）?&&?（t->lChild?==?NULL））
????{
????????t->isLeaf?=?1;
????}
????else
????{
????????t->isLeaf?=?0;
????}
????if?（t->parent?!=?NULL）
????{
????????t->id?=?2?*?t->parent->id?+?（int）t->bin?-?48;
????}
????else
????{
????????t->id?=?1;
????????t->bin?=?‘?‘;
????}
????if?（t->isLeaf?==?1）
????{
????????fprintf（ou?“%6d%5c%8d???‘%c‘\n“?t->id?t->bin?t->isLeaf?t->data）;
????}
????else
????{
????????fprintf（ou?“%6d%5c%8d\n“?t->id?t->bin?t->isLeaf）;
????}
????if?（t->lChild?!=?NULL）
????{
????????PreOrderTraverse（t->lChild）;
????}
????if?（t->rChild?!=?NULL）
????{
????????PreOrderTraverse（t->rChild）;
????}
}

int?main（）
{
	char?str[MAX_NUM];
	char?pwd[MAX_NUM];
	TreeNode?*HFTree;
	int?i?j;
	int?length;//字符串長度。。
	int?count;//不同字符個數。。
	TreeNode?*tree[MAX_CHAR_KINDS];//初始的幾個小樹。。
	TreeNode?*eachChar[MAX_CHAR_KINDS];
	TreeNode?*temp?*p;
	Code?*HFCode;
	int?codeBit;
	short?existed;

	//輸入，初始化。。
	printf（“Input?string?to?encode:\n“）;?
	gets（str）;
	printf（“\n“）;
	length?=?strlen（str）;
	count?=?0;

	//開始統計字符串中各個字符出現的次數。。
	for?（i?=?0;?i?	{
		existed?=?0;
		for?（j?=?0;?j?		{
			if?（str[i]?==?tree[j]->data）
			{
				tree[j]->weight++;
				existed?=?1;
				break;
			}
		}
		//如果不是現有的字符，拿個新盒子裝。。
		if?（existed?==?0）
		{
			tree[count]?=?（TreeNode?*）malloc（sizeof（TreeNode））;
			tree[count]->weight?=?1;
			tree[count]->data?=?str[i];
			tree[count]->parent?=?NULL;
			tree[count]->lChild?=?NULL;
			tree[count]->rChild?=?NULL;
			eachChar[count]?=?tree[count];//備份。。?
			count++;
		}
	}
	
	//非法輸入。。?
	if?（count?==?0）
	{
????????printf（“No?char!\n“）;?
????????getch（）;
????????return?（0）;
????}
????else?if?（count?==?1）
????{
????????printf（“At?least?2?kinds?of?char!\n“）;?
????????getch（）;
????????return?（0）;
????}

	//冒泡，升序。。
	for?（i?=?0;?i?	{
		for?（j?=?0;?j?		{
			if?（tree[j]->weight?>?tree[j+1]->weight）
			{
				temp?=?tree[j];
				tree[j]?=?tree[j+1];
				tree[j+1]?=?temp;
			}
		}
	}

	//生成Huffman樹。。
	for?（i?=?1;?i?	{
????????temp?=?（TreeNode?*）malloc（sizeof（TreeNode））;
????????temp->lChild?=?tree[i-1];
?