#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define Max 100
 
typedef struct HTNode{
	int weight;
	int parent, rchild, lchild;
}HTNode, *HuffmanTree;

// 指向指針類型的 指針 
typedef char* *HuffmanCode;

void Select(HuffmanTree HT, int n, int &s1, int &s2){
	int min;
	//找第一個最小值
	for(int i = 1; i <= n; i++){
		if (HT[i].parent == 0){
			min = i;
			break;
		}
	}
	for(int i = min + 1; i <= n; i++){
		if(HT[i].parent == 0 && HT[i].weight < HT[min].weight){
			min = i;
		}	
	}
	s1 = min; //第一個最小值給s1
	
	//找第二個最小值
	for(int i = 1; i <= n; i++){
		if(HT[i].parent == 0 && i != s1){
			min = i;
			break;
		}
	}
	for (int i = min + 1; i <= n; i++){
		if(HT[i].parent == 0 && HT[i].weight < HT[min].weight && i != s1){
			min = i;
		}	
	}
	s2 = min; //第二個最小值給s2
}

void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int w[], int n){
	int i;

	if(n <= 1){
		return;
	}
	// n 個葉子結(jié)點的哈夫曼樹共 2*n - 1 個結(jié)點 
	int m = 2*n - 1; 
	// 多分配一個空間，0 號單元未使用 
	HT = (HTNode*) malloc((m + 1)*sizeof(HTNode));
	
	// HuffTree數(shù)組初始化為 0.
	for(i = 1; i <= n; i++){
		HT[i].weight = w[i];
		HT[i].parent = 0;
		HT[i].lchild = 0;
		HT[i].rchild = 0; 
	} 

	// 構建哈夫曼樹.
	for(i = n + 1; i <= m; i++){
	 ? ?int s1, s2;
	 ? ?// 在 HT[1 ~ i-1]選擇 parent 為 0 且 weight 最小的兩個結(jié)點，其序號分別為 s1 和 s2。 
		Select(HT, i - 1, s1, s2);
		HT[i].weight = HT[s1].weight + HT[s2].weight;
		HT[s1].parent = i;
		HT[s2].parent = i;
		HT[i].lchild = s1; 
		HT[i].rchild = s2;
	} 
	
	// 從 葉子到根逆向 求每個字符的哈夫曼編碼 
	
	// 分配 n 個字符編碼的頭指針向量 
	HC = (HuffmanCode) malloc( (n + 1) * sizeof(char*) );
	// 分配求編碼的工作空間 
	char* temp = (char*) malloc( n * sizeof(char) );
	// 編碼結(jié)束符 
	temp[n - 1] = '\0';
	// 每一個字符求哈夫曼編碼 
	int start, pos, parent;
	for(i = 1; i <= n; i++){
		start = n - 1;
		pos = i;
		parent = HT[i].parent;
		
		while(parent != 0){
			if(HT[parent].lchild == pos){
				// 左子樹：置 0 
				temp[--start] = '0';
			}
			else{
				// 右子樹：置 1 
				temp[--start] = '1';
			}
			pos = parent;
			parent = HT[parent].parent;
		}
		// 為每一個字符編碼分配空間，分配的空間大小不同 
		HC[i] = (char*) malloc( (n - start) * sizeof(char) );
		// 從 temp 復制編碼到 HC 
		strcpy(HC[i], &temp[start]);
	}
	// 釋放工作空間 
	free(temp);
}

// 輸出哈夫曼樹、哈夫曼編碼 
void printfHTAndHC(HuffmanTree HT, HuffmanCode HC, int n){
	for(int i = 1; i <= 2*n - 1; i++){
		printf("i = %d, weight = %d, parent = %d, lchild = %d, rchild = %d\n",
		 i, HT[i].weight, HT[i].parent, HT[i].lchild, HT[i].rchild);
	}
	
	for(int i = 1; i <= n; i++){
		printf("%d 的 哈夫曼編碼為：%s\n",HT[i].weight, HC[i]);
	}
}

int main() {
	
	int n;
	int w[Max];
	HuffmanTree HT;
	HuffmanCode HC; 
	 
	printf("請輸入葉子結(jié)點個數(shù)：");
	scanf("%d", &n);
	for(int i = 1; i <= n; i++){
		printf("請輸入第 %d 個葉子結(jié)點的權值：", i);
		scanf("%d", &w[i]);
	}
	
	HuffmanCoding(HT, HC, w, n);
	
	printfHTAndHC(HT, HC, n);
	
	return 0;
}