//哈夫曼樹(shù)C語(yǔ)言實(shí)現(xiàn)
#include <stdio.h>
#include <stdlib.h>
typedef struct HuffmanNode
{
 char letter;//存儲(chǔ)的字符，葉節(jié)點(diǎn)為字母，非葉節(jié)點(diǎn)為#
 struct HuffmanNode *parent;//父親結(jié)點(diǎn)
 int code;//如果為父親結(jié)點(diǎn)的左孩子，則為0，右孩子為1
}HuffmanNode;
typedef struct HeapNode
{
 int rate;//出現(xiàn)頻率
 HuffmanNode *node;//對(duì)應(yīng)于哈夫曼樹(shù)中的結(jié)點(diǎn)
}HeapNode;
/*------------------全局變量----------------------*/
int heapSize;//堆大小
int num;//記錄字符數(shù)量
HeapNode *heap;//堆數(shù)組
char *letter;//字符數(shù)組
int *rate;//字符出現(xiàn)頻率
HuffmanNode **array; //記錄葉節(jié)點(diǎn)的數(shù)組，打印編碼的時(shí)候可以從葉結(jié)點(diǎn)回溯向上
char ch;
/*----------------------函數(shù)聲明-------------------------*/
void init(int numOfLetters);//初始化變量
void input();//輸入數(shù)組
int parent(int i);//求父節(jié)點(diǎn)
int left(int i);//求左孩子
int right(int i);//求右孩子
void swap(int i,int j);//交換函數(shù)
void heapIfy(int i,int localHeapSize);//維持堆性質(zhì)函數(shù)，使用前提為左右子樹(shù)均為最小堆
void buildHeap();//初始化堆
HeapNode* extractMin();//去掉并返回堆中最小的元素
void heapInsert(int rate,HuffmanNode *p);//向堆中插入數(shù)據(jù)（前提：堆已經(jīng)初始化）
HuffmanNode* buildTree();//構(gòu)造哈夫曼樹(shù)
void display();//顯示函數(shù)
void backPrint(HuffmanNode *p,HuffmanNode *root);//從葉節(jié)點(diǎn)回溯打印編碼code
/*----------------------函數(shù)實(shí)現(xiàn)-------------------------*/
void init(int numOfLetters)
{
 heapSize=numOfLetters;//堆大小初始化為字母數(shù)
 num=numOfLetters;//記錄字符數(shù)量
 heap=(HeapNode*)malloc((numOfLetters+1)*sizeof(HeapNode));//分配堆空間，最多只需要字符的個(gè)數(shù)，因?yàn)楹喜⑦^(guò)程中刪除兩個(gè)，插入一個(gè)
 letter=(char*)malloc((numOfLetters+1)*sizeof(char));//用于存儲(chǔ)字符
 rate=(int *)malloc((numOfLetters+1)*sizeof(int));//用于存儲(chǔ)字符出現(xiàn)頻率
 array=(HuffmanNode **)malloc((numOfLetters+1)*sizeof(HuffmanNode));//記錄葉節(jié)點(diǎn)的數(shù)組，打印編碼的時(shí)候可以從葉結(jié)點(diǎn)回溯向上
 
}
void input()
{
 int i=1;
 while(i<=heapSize)
 {
  printf("輸入第%d個(gè)字符\n",i);
  scanf("%c",&letter[i]);ch=getchar();
  printf("輸入第%d個(gè)字符的頻度\n",i);
  scanf("%d",&rate[i]);ch=getchar();
  //向堆中插入各個(gè)結(jié)點(diǎn)
  heap[i].rate=rate[i];
  heap[i].node=(HuffmanNode *)malloc(sizeof(HuffmanNode));
  array[i]=heap[i].node;
  heap[i].node->parent=NULL;
  heap[i].node->letter=letter[i];
  i++;
 }
}
int parent(int i)
{
 return i/2;
}
int left(int i)
{
 return 2*i;
}
int right(int i)
{
 return 2*i+1;
}
void swap(int i,int j) //交換結(jié)構(gòu)體數(shù)組，需要交換結(jié)構(gòu)體內(nèi)數(shù)據(jù)
{
 int rate;
 HuffmanNode *p;
 rate=heap[i].rate;
 p=heap[i].node;
 heap[i].rate=heap[j].rate;
 heap[i].node=heap[j].node;
 heap[j].rate=rate;
 heap[j].node=p;
}
void heapIfy(int i,int localHeapSize)//維持堆性質(zhì)函數(shù)，使用前提為左右子樹(shù)均為最小堆
{
 int l=left(i);
 int r=right(i);
 int least=i;
 //找出heap成員rate 的i,left(i),right(i)的最小值
 if(l<=localHeapSize&&heap[least].rate>heap[l].rate)
 {
  least=l;
 }
 if(r<=localHeapSize&&heap[least].rate>heap[r].rate)
 {
  least=r;
 }
 if(least!=i)
 {
  swap(i,least);
  heapIfy(least,localHeapSize);
 }
}
void buildHeap()//初始化堆
{
 int i=0;
 for(i=heapSize/2;i>=1;i--)
 {
  heapIfy(i,heapSize);
 }
}
HeapNode* extractMin()
{
 if(heapSize>=1)
 {
  HeapNode *min;
  swap(1,heapSize);
  min=&heap[heapSize];
  --heapSize;
  heapIfy(1,heapSize);
  return min;
 }
 else
 {
  printf("堆中沒(méi)有元素");
  return NULL;
 }
}
void heapInsert(int rate,HuffmanNode *p)
{
 ++heapSize;
 int i=heapSize;
 while(i>1&&heap[parent(i)].rate>rate)
 {
  heap[i].rate=heap[parent(i)].rate;
  heap[i].node=heap[parent(i)].node;
  i=parent(i);
 }
 heap[i].rate=rate;
 heap[i].node=p;
}
HuffmanNode* buildTree()
{
 buildHeap();//初始化堆
 HeapNode *p;//用于臨時(shí)存儲(chǔ)最小堆結(jié)點(diǎn)
 HeapNode *q;//用于臨時(shí)存儲(chǔ)次小堆結(jié)點(diǎn)
 int count=heapSize;
 int i;
 for(i=1;i<=count-1;i++)
 {
  HuffmanNode *tree=(HuffmanNode*)malloc(sizeof(HuffmanNode));//生成內(nèi)結(jié)點(diǎn)
  tree->letter='#';//內(nèi)結(jié)點(diǎn)的字符記作#，沒(méi)有實(shí)際意義
  p=extractMin();
  q=extractMin();
  p->node->parent=tree;
  p->node->code=0;
  q->node->parent=tree;
  q->node->code=1;
  //printf("%c:%d",p->node->letter,p->node->code);
  //printf("\n"); printf("%c:%d",q->node->letter,q->node->code); printf("\n");//測(cè)試
  heapInsert(p->rate+q->rate,tree);//插入堆中
 }
 return extractMin()->node;
}
void display()
{
 HuffmanNode*p=buildTree();////哈夫曼樹(shù)的根節(jié)點(diǎn)地址
 int i=1;
 while(i<=num)
 {
  printf("%c:",array[i]->letter);
  backPrint(array[i],p);
  printf("\n");
  i++;
 }
}
void backPrint(HuffmanNode *p,HuffmanNode *root)
{
 if(p!=root)
 {
  backPrint(p->parent,root);
  printf("%d",p->code);//printf("++++");//測(cè)試
 }
}
int main(int argc ,char* argv[])
{
 int number;
 printf("輸入的字符個(gè)數(shù)為：\n");
 scanf("%d",&number);
 ch=getchar();
 init(number);
 input();
 display();
 system("PAUSE");
 return 0;
}