#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;


#define NO 100//最多no個葉子,編碼、譯碼最大長度
#define MO 2*NO-1 //最多mo個結點

struct HT
{
	int weight;
	int lch, rch, parent;
};

HT ht[NO+1];//0單元不用

struct HNode
{
	char ch;
	char bit[NO];
	int start;
};

struct HNode ha[MO+1];
int n, m;
//判斷次數

void select(int t, int &s1, int &s2)
{//從1~t里找出parent==0且權重為最小、次小
	int w1, w2, i;
	w1 = 32767;
	w2 = w1;
	s1 = s2 = 0;
	for(i = 1; i <= t; i++)		
	{	if(ht[i].parent == 0 && ht[i].weight < w1)
			{
					s2 = s1;//將最小的編號送給s2當次小編號
					w2 = w1;//將w1送到w2當次小
					w1 = ht[i].weight;
					s1 = i;
			}
		else	
			if(ht[i].parent == 0 && ht[i].weight < w2)
			{
					w2 = ht[i].weight;
					s2 = i;
			}
			
	}
	//for
}//select

void creatHT_HNode()
{
	int i,child, parent, s1, s2;
	struct HNode dx;
	cout << "請輸入葉子數n：" << endl;
	cin >> n;
	m = 2*n-1;
	for(i = 1; i <= m; i++)
	{
		ht[i].lch = ht[i].rch = ht[i].parent = 0;	//初始化
	}

	for(i = 1; i <= n; i++)
	{
		cout << "請輸入字符ch,權值weight: " << endl;
		cin >> ha[i].ch >> ht[i].weight;
	}
	cout << "構造樹的過程" << endl;
	for(i = n+1; i <= m; i++)//生成樹
	{
		{
			select(i-1, s1, s2);
			ht[i].weight = ht[s1].weight + ht[s2].weight;//父親權重
			ht[i].lch = s1;
			ht[i].rch = s2;//父親的左右孩子
			ht[s1].parent = ht[s2].parent = i;//孩子的父親標號
		}

		{
				cout << ht[i].weight << "	" << endl;	
				cout << ht[s1].weight << " " << ht[s2].weight << endl;
				cout << endl;
		}
	}//構造樹


	for( i = 1; i <= n; i++)//進行編碼
	{
		dx.ch = ha[i].ch;
		dx.start = 0;//
		child = i;
		parent = ht[i].parent;
		while( parent != 0)
		{
			if(ht[parent].lch == child)//判斷左孩子為其左子樹
				dx.bit[ dx.start++] = '0';//左標記為0，且記號start+1
			else 
				if(ht[parent].rch == child)//判斷右孩子為其右子樹
				dx.bit[ dx.start++] = '1';//右標記為1，且記號start+1
			child = parent;//動態根結點下移到其子樹
			parent = ht[child].parent;//子樹的父親重新賦值
		}
		ha[i] = dx;//將一個葉子的編碼傳遞給對應的葉子結構體
	}
}

		
void printT(int root,int i)//輸出樹
{
	int j;
	for(j = 0; j <= i; j++)	
		cout << "   ";
	cout << ht[root].weight << " " << ha[root].ch << endl;
	if(ht[root].rch != 0 || ht[root].lch != 0)//判斷左右子樹是否為空
	{
		printT(ht[root].rch, ++i);	//進行遞歸
		printT(ht[root].lch, i++);	//進行遞歸
	}	
}//遍歷構造出來的樹



void print( HNode ha[],HT ht[])
{
	int i,k;
	for(i = 1; i<= m; i++)
	{
		cout << "字符：" << ha[i].ch;
		cout << "     權重：" << ht[i].weight;
		cout << "     編碼：";
		for( k = ha[i].start-1; k >= 0; k--)
		{		
			cout << ha[i].bit[k];
		}
		cout << "     左孩子：" << ht[i].lch << "     右孩子：" << ht[i].rch << "     父親：" << ht[i].parent << endl;
	}
}


void Coding()//進行編碼
{
	int i,k,t,j = NO;
	cout << "請輸入需要編碼的字符串(最長100)：" << endl;
	char c[101];
	cin >> c;
	for(i = 0; i <= j; i++)//查找每個字符數組元素
	{
		for(t = 1;t <= n; t++)//查找葉子
		{
			if(ha[t].ch == c[i])//判斷字符與葉子是否相同
			{
				for( k = ha[t].start-1; k >= 0; k--)//從各個葉子的相應記錄開始輸出
				{		  
					cout << ha[t].bit[k];//輸出相應的編碼
				}//for
			}//if
		}//if
	}//for

	cout<<endl;
}


void HTCoding(HT ht[])//進行譯碼
{
	int i = 0, j = NO;
	int  p;
	char c[NO];//c存放要譯碼的字符
	p = m;//p指向根結點
	cout << "請輸入需要譯碼的字符串(最長100)：" << endl;
	cin >> c;
	while(c[i] != '\0')
	{
			{	
				if(c[i] == '0')	p = ht[p].lch;//判斷c[i]中的值:0向左走
				else		p = ht[p].rch;  //1向右走
			}

			if(ht[p].rch == 0 && ht[p].rch == 0)//判斷
			{	
				cout << ha[p].ch << " ";
				p = m;//p繼續從根結點開始
			}

			i++;
	}

	cout<<endl;

}
void main()
{
	cout << "開始規定相應的字符 " << endl;
	creatHT_HNode();//建立相應的哈弗曼樹
	cout << endl << "樹為：" << endl;
	printT(m,0);//輸出樹
	cout << endl;
	print(ha,ht);//輸出各個結點信息
	cout << endl << endl;
	while(1)
	{
		cout << "		主程序		" << endl;
		cout << "請輸入想進行的操作：1.編碼	      2.譯碼		3.退出" << endl;
		char z;
			cin >> z;
			switch(z)
			{
			case '1':
				Coding();   //編碼
				continue;
			case '2':
				HTCoding(ht);  //譯碼
				continue;
			case '3':
				exit(1);
			default:;
			}
	}
}