typedef struct{
  int weight; //权值
  int parent,lch,rch; //双亲结点，左孩子结点，右孩子结点
}HTNode,*HuffmanTree;

void CreateHuffmanTree(HuffmanTree HT,int n){
  if(n <= 1)  return;
  m = 2*n-1;      //数组共2n-1个元素
  HT = new HTNode[m+1]; //HT[m]表示根节点
  for(i = 1; i < m; i++){ //将2n-1个元素的lch，rch，parent置0
  HT[i].lch = 0;
  HT[i].rch = 0;
  HT[i].parent = 0;
  }
  for(i = 1; i < m; i++){ //输入前n个元素的weight值
  cin >> HT[i].weight;
  }
  for(i = n+1; i < m; i++){ //合并产生n-1个结点
  Select(HT, i-1, s1,s2);     //选择两个双亲为0且权值为最小的结点，返回在HT中的s1,s2序号
  HT[s1].parent = i;HT[s2].parent = i;  //从表中删除s1,s2
  HT[i].lch = s1;HT[i]rlch = s2;    //s1,s2分别作为i的左右孩子
  HT[i].weight = HT[s1].weight +   HT[s2].weight; //i的权值为左右孩子权值之和
  }
}

void CreatHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n){
  //从叶子到跟逆向求每个字符的哈夫曼编码，存储到编码表中
  HC = new char* [n+1]; //分配n个字符编码的头指针矢量
  cd = new char[n];  //分配临时存放编码的动态数组空间
  cd[n-1] = '\0';   //编码结束符
  for(i = 1; i <= n; i++)
  {
  start = n-1;  
  c = i;
  f = HT[i].parent;
  while( f != 0)  //当还不是根节点时一直回溯
  {
    start--；
    if(HT[f].lchild == c) //结点c是f的左孩子，则生成代码0
    cd[start] = '0';
    else      //结点c是f的右孩子，则生成代码1
    cd[start] = '1';
    c = f;      //以下两步是回溯的作用
    f = HT[f].parent;  //自己成为双亲再查找    
  }
  HC[i] = new char[n - start];//为第i个字符串编码分配空间
  strcpy(HC[i],&cd[start]); //将求得的编码从临时空间cd复制到HC的当前行中
  }
  delete cd;    //释放临时空间
}