//哈夫曼树C语言实现
#include <stdio.h>
#include <stdlib.h>
typedef struct HuffmanNode
{
 char letter;//存储的字符，叶节点为字母，非叶节点为#
 struct HuffmanNode *parent;//父亲结点
 int code;//如果为父亲结点的左孩子，则为0，右孩子为1
}HuffmanNode;
typedef struct HeapNode
{
 int rate;//出现频率
 HuffmanNode *node;//对应于哈夫曼树中的结点
}HeapNode;
/*------------------全局变量----------------------*/
int heapSize;//堆大小
int num;//记录字符数量
HeapNode *heap;//堆数组
char *letter;//字符数组
int *rate;//字符出现频率
HuffmanNode **array; //记录叶节点的数组，打印编码的时候可以从叶结点回溯向上
char ch;
/*----------------------函数声明-------------------------*/
void init(int numOfLetters);//初始化变量
void input();//输入数组
int parent(int i);//求父节点
int left(int i);//求左孩子
int right(int i);//求右孩子
void swap(int i,int j);//交换函数
void heapIfy(int i,int localHeapSize);//维持堆性质函数，使用前提为左右子树均为最小堆
void buildHeap();//初始化堆
HeapNode* extractMin();//去掉并返回堆中最小的元素
void heapInsert(int rate,HuffmanNode *p);//向堆中插入数据（前提：堆已经初始化）
HuffmanNode* buildTree();//构造哈夫曼树
void display();//显示函数
void backPrint(HuffmanNode *p,HuffmanNode *root);//从叶节点回溯打印编码code
/*----------------------函数实现-------------------------*/
void init(int numOfLetters)
{
 heapSize=numOfLetters;//堆大小初始化为字母数
 num=numOfLetters;//记录字符数量
 heap=(HeapNode*)malloc((numOfLetters+1)*sizeof(HeapNode));//分配堆空间，最多只需要字符的个数，因为合并过程中删除两个，插入一个
 letter=(char*)malloc((numOfLetters+1)*sizeof(char));//用于存储字符
 rate=(int *)malloc((numOfLetters+1)*sizeof(int));//用于存储字符出现频率
 array=(HuffmanNode **)malloc((numOfLetters+1)*sizeof(HuffmanNode));//记录叶节点的数组，打印编码的时候可以从叶结点回溯向上
 
}
void input()
{
 int i=1;
 while(i<=heapSize)
 {
  printf("输入第%d个字符\n",i);
  scanf("%c",&letter[i]);ch=getchar();
  printf("输入第%d个字符的频度\n",i);
  scanf("%d",&rate[i]);ch=getchar();
  //向堆中插入各个结点
  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) //交换结构体数组，需要交换结构体内数据
{
 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)//维持堆性质函数，使用前提为左右子树均为最小堆
{
 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("堆中没有元素");
  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;//用于临时存储最小堆结点
 HeapNode *q;//用于临时存储次小堆结点
 int count=heapSize;
 int i;
 for(i=1;i<=count-1;i++)
 {
  HuffmanNode *tree=(HuffmanNode*)malloc(sizeof(HuffmanNode));//生成内结点
  tree->letter='#';//内结点的字符记作#，没有实际意义
  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");//测试
  heapInsert(p->rate+q->rate,tree);//插入堆中
 }
 return extractMin()->node;
}
void display()
{
 HuffmanNode*p=buildTree();////哈夫曼树的根节点地址
 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("++++");//测试
 }
}
int main(int argc ,char* argv[])
{
 int number;
 printf("输入的字符个数为：\n");
 scanf("%d",&number);
 ch=getchar();
 init(number);
 input();
 display();
 system("PAUSE");
 return 0;
}