#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 100
#define M 2*N-1
typedef char *HuffmanCode[2*M];
typedef struct
{
 int weight;//权值
 int parent;//父节点
 int Lchild;//左
 int Rchild;//右
}HTNode,Huffman[M+1];//huffman树
typedef struct Node
{
 int weight;//叶子权值
 char c;//叶子
 int num;//叶子的2进制码长度
}WNode,WeightNode[N];
void CreatWeight(char ch[],int *s,WeightNode CW,int *p)//生成叶子节点字符与权值
{
 int i,j,k;
 int tag;
 *p=0;//叶子节点数
 for(i=0;ch[i]!='\0';i++)//记录字符个数放入CW
 {
  tag=1;
  for(j=0;j<i;j++)
   if(ch[j]==ch[i])
   {
    tag=0;
    break;
   }
   if(tag)
   {
    CW[++*p].c=ch[i];
    CW[*p].weight=1;
    for(k=i+1;ch[k]!='\0';k++)
    {
     if(ch[i]==ch[k])
      CW[*p].weight++;//权值++
    }
   }
 }
 *s=i;//字符串长
}
void CreateHuffmanTree(Huffman ht,WeightNode w,int n)//建立huffmantree
{
 int i,j;
 int s1,s2;
 for(i=1;i<=n;i++)//初始化
 {
  ht[i].weight=w[i].weight;
  ht[i].parent=0;
  ht[i].Lchild=0;
  ht[i].Rchild=0;
 }
 for(i=n+1;i<=2*n-1;i++)
 {
  ht[i].weight=0;
  ht[i].parent=0;
  ht[i].Lchild=0;
  ht[i].Rchild=0;
 }
 for(i=n+1;i<=2*n-1;i++)
 {
  for(j=1;j<=i-1;j++)
   if(!ht[j].parent)
    break;
   s1=j;//找第一个双亲!=0节点
   for(;j<=i-1;j++)
    if(!ht[j].parent)
     s1=ht[s1].weight>ht[j].weight?j:s1;
    ht[s1].parent=i;
    ht[i].Lchild=s1;
    for(j=1;j<=i-1;j++)
     if(!ht[j].parent)
      break;
     s2=j;//找第二个双亲!=0节点
     for(;j<=i-1;j++)
      if(!ht[j].parent)
       s2=ht[s2].weight>ht[j].weight?j:s2;
    //  printf("s2=%d\n",s2);
      ht[s2].parent=i;
      ht[i].Rchild=s2;
               //  intf("rchild=%d\n",ht[i].Rchild);
      ht[i].weight=ht[s1].weight+ht[s2].weight;//权值++
 }
}
void CrtHuffmanNodeCode(Huffman ht,char ch[],HuffmanCode h,WeightNode weight,int m,int n)//叶子节点编码
{
 int i,c,p,start;
 char *cd;
 cd=(char*)malloc(n*sizeof(char));
 cd[n-1]='\0';//末尾=0
 for(i=1;i<=n;i++)
 {
  start=n-1;//cd从末尾开始
  c=i;
  p=ht[i].parent;//p在n+1——2n-1
  while(p)//沿父方向遍历至0
  {
   start--;//向前
   if(ht[p].Lchild==c)//与lchild相同=0
    cd[start]='0';
   else//=1
    cd[start]='1';
   c=p;
   p=ht[p].parent;
  }
  weight[i].num=n-start;//二进制码长度
  h[i]=(char*)malloc((n-start)*sizeof(char));
  strcpy(h[i],&cd[start]);//二进制字符复制到h
 }
 free(cd);
 //system("pause");
}
void CrtHuffmanCode(char ch[],HuffmanCode h,HuffmanCode hc,WeightNode weight,int n,int m)//所有字符编码
{
 int i,k;
 for(i=0;i<m;i++)
 {
  for(k=1;k<=n;k++)//从weight[k].c中找与ch[i]相等下标k*
   if(ch[i]==weight[k].c)
    break;
   hc[i]=(char*)malloc((weight[k].num)*sizeof(char));
   strcpy(hc[i],h[k]);//复制二进制码
 }
}
void TrsHuffmanTree(Huffman ht,WeightNode w,HuffmanCode hc,int n,int m)//译码
{
 int i=0,j,p;
 while(i<m)
 {
  p=2*n-1;//从父亲遍历到叶子
  for(j=0;hc[i][j]!='\0';j++)
  {
   if(hc[i][j]=='0')
    p=ht[p].Lchild;
   else
    p=ht[p].Rchild;
  }
  printf("%c",w[p].c);
  i++;
 }
}
void main()
{
 int i;
 int n=0;//叶子数
 int m=0;//ch长度
 char ch[N];//输入字符
 Huffman ht;//huffman二叉树
 HuffmanCode h;//叶子编码
 HuffmanCode hc;//所有节点编码
 WeightNode weight;//叶子信息
 printf("Huffman\n  please intput inf\n");
 gets(ch);
 CreatWeight(ch,&m,weight,&n);
 for(i=1;i<=n;i++)//输出叶子字符和权
  printf("%c",weight[i].c);
 printf("\nweight");
 for(i=1;i<=n;i++)
  printf("%d",weight[i].weight);
 CreateHuffmanTree(ht,weight,n);
 printf("\ti\tweight\tparent\tLChild\tRChild\n");
 for(i=1;i<=2*n-1;i++)
  printf("\t%d\t%d\t%d\t%d\t%d\n",i,ht[i].weight,ht[i].parent,ht[i].Lchild,ht[i].Rchild);
 CrtHuffmanNodeCode(ht,ch,h,weight,m,n);
 for(i=1;i<=n;i++)
 {
  printf("\t%c ",weight[i].c);
  printf("%s\n",h[i]);
 }
 CrtHuffmanCode(ch,h,hc,weight,n,m);
 printf("code");
 for(i=0;i<m;i++)
  printf("%s",hc[i]);
 printf("\n");
 TrsHuffmanTree(ht,weight,hc,n,m);
}