#include <stdio.h>
#include <string.h>
#include <malloc.h>
#define null 0
#define MAXN 100
#define MAXM 300

struct tagTree{//用二叉排序樹保存出現的各個字符
	char optr;    //需要編碼的某個字符
	int n_appear; //當前字符出現的次數
	struct tagTree*lchild;
	struct tagTree*rchild;
}*btree;//btree作為二叉排序樹的根

struct tagHeap{//堆結構
	char optr;    //當前字符，葉子時有效
	int n_appear; //當前子樹出現的次數
	struct tagHeap*lchild;
	struct tagHeap*rchild;
}*heap[MAXM];//開始時最多可以有MAXN棵子樹

int n_heap,n_code;
char code[MAXN];//打印haffman編碼時候用到

void insert_to_heap(struct tagHeap *pt)//插入一個元素到堆，從下到上調整
{
	heap[++n_heap] = pt; //插入節點到最后
	int parent,child=n_heap;
	while(child > 1)
	{
		parent = child >> 1;//獲得child的parent節點的index
		if(heap[parent]->n_appear <= heap[child]->n_appear)break;
		pt = heap[parent];          //child節點和parent節點交換步驟1
		heap[parent] = heap[child]; //child節點和parent節點交換步驟2
		heap[child] = pt;           //child節點和parent節點交換步驟3
		child = child >> 1;
	}
}//inseart_to_heap

void delete_from_heap(struct tagHeap *&pt)//從堆中取出根節點，從上到下調整
{
	if(!n_heap)//堆為空則有pt返回NULL
	{
		pt = null; return;
	}
	pt = heap[1];
	int child,parent=1;
	while(1)
	{
		child = parent << 1;//獲取左孩子的index
		if(child < n_heap)
		{
			if(heap[child]->n_appear <= heap[child+1]->n_appear)
			{
				heap[parent] = heap[child];
				parent = child;
			}
			else
			{
				heap[parent] = heap[child+1];
				parent = child + 1;
			}
		}
		else if(child == n_heap)
		{
			heap[parent] = heap[child];
			--n_heap;
			break;
		}
		else
		{
			heap[parent] = heap[n_heap];
			--n_heap;
			break;
		}
	}
}//delete_from_heap

void insert_to_btree(struct tagTree*&btree,char optr)//新出現的字符插入到二叉樹，已有的則計數器加一
{
	if(btree == null)
	{
		btree = (struct tagTree*)malloc(sizeof(struct tagTree));
		btree->optr = optr;
		btree->n_appear = 1;
		btree->lchild = null;
		btree->rchild = null;
	}
	else if(btree->optr == optr)
	{
		btree->n_appear++;
	}
	else if(btree->optr < optr)
	{
		insert_to_btree(btree->rchild,optr);
	}
	else
	{
		insert_to_btree(btree->rchild,optr);
	}
}//insert_to_btree

void init_data(void)
{
	btree = null;
	n_heap = 0;
	char optr;
	while(scanf("%c",&optr)!=EOF)
	{
		insert_to_btree(btree,optr);
	}
}//init_data

void init_heap(struct tagTree*btree)
{
	if(btree != null)
	{
		struct tagHeap *pt;
		pt = (struct tagHeap *)malloc(sizeof(struct tagHeap));
		pt->lchild = null;
		pt->rchild = null;
		pt->n_appear = btree->n_appear;
		pt->optr = btree->optr;
		insert_to_heap(pt);
		if(btree->lchild != null)
		{
			init_heap(btree->lchild);
		}
		if(btree->rchild != null)
		{
			init_heap(btree->rchild);
		}
	}
}//init_heap

void haffman(void)
{
	init_heap(btree);
	while(n_heap >= 2)//不斷的將出現次數最少的兩棵子樹合并
	{
		struct tagHeap *pt1,*pt2,*pt;
		delete_from_heap(pt1);
		delete_from_heap(pt2);
		pt = (struct tagHeap *)malloc(sizeof(struct tagHeap));
		pt->lchild = pt1;
		pt->rchild = pt2;
		pt->optr = '\0';
		pt->n_appear = pt1->n_appear + pt2->n_appear;
		insert_to_heap(pt);
	}
}//haffman

void print_haffman_code(struct tagHeap *pt,int len)//打印haffman編碼
{
	if(pt != null)
	{
		if(pt->lchild == null)
		{
			code[len] = '\0';
			printf("optr=%c,value=%d,n_appear=%d,haffman code=%s\n",pt->optr,(int)pt->optr,pt->n_appear,code);
		}
		else
		{
			code[len] = '0';
			print_haffman_code(pt->lchild,len+1);
		}
		if(pt->rchild != null)
		{
			code[len] = '1';
			print_haffman_code(pt->rchild,len+1);
		}
	}
}//print_haffman_code

void print_haffman(void)
{
	if(n_heap >= 1)
	{
		print_haffman_code(heap[1],0);
	}
	else
	{
		printf("輸入為空，編碼失敗!\n");
	}
}//print_haffman

int main(void)
{
	freopen("D:\\in.txt","r",stdin); //文件輸入，若要改為手動輸入，請注釋次行
	init_data();
	haffman();
	print_haffman();
	return 0;
}