#include<stdio.h>
#define MAX_SIZE 1000
typedef struct NODE Node;
struct NODE{
   int weight;//節(jié)點的權值
   int parent,lchild,rchild;
};
/*
初始化或者更改節(jié)點的信息，比如，如果這個節(jié)點是一個新節(jié)點，那么
就需要將這個節(jié)點初始化成一個葉子節(jié)點，否則需要修改這個節(jié)點的父節(jié)點
*/
void initNode(Node &node,int weight,int parent,int lchild,int rchild){
    node.weight = weight;
    node.lchild = lchild;
    node.rchild = rchild;
    node.parent = parent;
}
/*
1、有n個葉子節(jié)點，那么構建哈夫曼樹的時候，需要分配n * 2 - 1個內(nèi)存空間，前n
個表示的是新輸入的葉子節(jié)點，后面n - 1表示的是葉子節(jié)點的父節(jié)點
2、遍歷這個數(shù)組，將進行初始化，即給這些節(jié)點的權值賦值，并且將他的左右子節(jié)
點、父節(jié)點賦初始值為-1，從而構建了n個葉子節(jié)點
3、遍歷數(shù)組，從而將從這個數(shù)組中跳出兩個值最小的葉子節(jié)點，同時需要標記他們的下標，從而可以知道當前最小值節(jié)點的父節(jié)點的左右子節(jié)點的下標，方便下次尋找
最小值的葉子結(jié)點的時候不會再找到已經(jīng)找過的葉子節(jié)點
4、將新節(jié)點插入到數(shù)組的最后。
5、重復3，4的操作，直到只有一個節(jié)點，那么這個節(jié)點就是哈夫曼樹的根節(jié)點
*/
void createHuffmanTree(Node *node,int *arr,int n){
    //n表示有n個葉子節(jié)點，arr數(shù)組存放的是所有葉子節(jié)點的值
   int i,j,min1,min2,x1,x2,total;//min1:第一個最小值，min2:第二個最小值,x1:第一個最小值的下標，x2:第二個最小值的下標
   for(i = 0; i < n; i++){
       initNode(node[i],arr[i],-1,-1,-1);//調(diào)用initNode方法，從而將節(jié)點進行初始化
   }
   total = n * 2 - 1;//total表示的是哈夫曼所有節(jié)點的個數(shù)
   for(i = n; i < total; i++){
        //i之所以從n開始，是因為第一個父節(jié)點這個下標（前n個節(jié)點是葉子節(jié)點）
        min1 = 65432;//定義兩個最小值
        min2 = min1;
        x1 = x2 = 0;//假設兩個最小值的下標都是0
        for(j = 0; j < i; j++){
            //判斷當前下標的節(jié)點是否為葉子節(jié)點
           if(node[j].parent == -1){
          //如果當前節(jié)點的parent等于-1，表示這個節(jié)點是一個葉子節(jié)點，那么我們需要判斷他是否一個最小節(jié)點
                if(node[j].weight < min1){
         //如果當前這個節(jié)點的值比min1小，那么我們需要更新min2，min1，同時需要更新兩者對應的下標
                    min2 = min1;
                    x2 = x1;
                    min1 = node[j].weight;
                    x1 = j;
                }else if(node[j].weight < min2){
                 /*
                 如果當前這個節(jié)點比第一個最小值要大，那么我們需要判斷
                 他是否比第二個最小值小，如果是，那么更新min2,并且更新x2
                 */
                   min2 = node[j].weight;
                   x2 = j;
                }
           }
        }
        /*
        找到兩個最小節(jié)點之后，我們需要將這兩個節(jié)點的父節(jié)點指向i，
        然后將i這個節(jié)點進行初始化,并且新節(jié)點的左子節(jié)點比右子節(jié)點小
        從而構建唯一的哈夫曼樹
        */
        node[x1].parent = i;
        node[x2].parent = i;
        initNode(node[i],min1 + min2,-1,x1,x2);//初始化合并之后的新節(jié)點
   }
}
void huffmanCode(Node *node,int child,int *str){
    //str表示的是這個葉子節(jié)點的哈夫曼編碼
    int i,parent,j = 0,e;
    parent = node[child].parent;//獲取當前這個葉子節(jié)點的父節(jié)點
    while(parent != -1){
        if(node[parent].lchild == child){
            //如果當前這個節(jié)點是父節(jié)點的左子節(jié)點，那么就將0壓入到數(shù)組中,否則將1壓入數(shù)組中
            str[j++] = 0;
        }else{
            str[j++] = 1;
        }
        child = parent;
        parent = node[child].parent;
    }
    e = j;//當退出循環(huán)的時候，j表示的是這個數(shù)的哈夫曼編碼的長度，所以需要從下標為j - 1開始逆序輸出，才是這個數(shù)的哈夫曼編碼
    for(j = e - 1; j>= 0; j--)
        printf("%d",str[j]);
    printf("\n");
}
int main(){
  Node node[MAX_SIZE];
  int arr[MAX_SIZE];//定義一個整形數(shù)組，用于存放所有葉子節(jié)點的權值
  int arr2[MAX_SIZE];//arr2用于存放一個數(shù)字的哈夫曼編碼
  int n,i,j,e;
  printf("請輸入葉子節(jié)點的個數(shù):");
  scanf("%d",&n);
  for(i = 0; i < n; i++)
    scanf("%d",&arr[i]);
  createHuffmanTree(node,arr,n);//構建哈夫曼樹
  /*
  獲取哈夫曼編碼:
  1、將遍歷數(shù)組arr，從而獲得各個葉子節(jié)點的權值以及下標
  2、通過這個下標，我們從這個節(jié)點向根節(jié)點走去，如果當前節(jié)點是父節(jié)點的左子
  節(jié)點，那么將0壓入到數(shù)組中，否則將1壓入到數(shù)組arr2中
  3、逆序輸出arr2
  */
  for(i = 0; i < n; i++){
    huffmanCode(node,i,arr2);//調(diào)用這個方法，將當前下標對應的數(shù)字的哈夫曼編碼輸出
  }
  return 0;
}