从零开始养成算法·篇十三：哈夫曼

一、最优树的定义：

结点的路径长度定义为：从根结点到该结点的路径上分支的数目。
　　树的路径长度定义为：树中每个结点的路径长度之和。
　　树的带权路径长度定义为：树中所有叶子结点的带权路径长度之和
　　WPL(T) = (对所有叶子结点)
　　在所有含有n个叶子结点、并带有相同权值的m叉树中，必存在一棵其带权路径长度取最小值的树，称为最优树。

939674-20190401114746895-1473948400.jpg

二、如何构造最优树：

哈夫曼算法，以二叉树为例：
（1）根据给定的n个权值{W1,W2,W3...Wn}，构造n棵二叉树的集合F={T1,T2...Tn},
其中每棵二叉树中均只含一个带权值为Wi的根结点，其左、右树为空树。
（2）在F中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造
一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和。
（3）从F中删去这两棵树，同时加入刚生成的新树。
（4）重复（2）和（3）两步，直至F中只含一棵树为止。

void Haffman(int weight[],int n,HaffNode *haffTree){
   
   int j,m1,m2,x1,x2;
   
   //1.哈夫曼树初始化
   //n个叶子结点. 2n-1
   for(int i = 0; i < 2*n-1;i++){
       
       if(i<n)
           haffTree[i].weight = weight[i];
       else
           haffTree[i].weight = 0;
       
       haffTree[i].parent = 0;
       haffTree[i].flag = 0;
       haffTree[i].leftChild = -1;
       haffTree[i].rightChild = -1;
   }
   
   
   //2.构造哈夫曼树haffTree的n-1个非叶结点
   for (int i = 0; i< n - 1; i++){
        m1 = m2 = MaxValue;
        x1 = x2 = 0;
       //2,4,5,7
       for (j = 0; j< n + i; j++)//循环找出所有权重中，最小的二个值--morgan
       {
           if (haffTree[j].weight < m1 && haffTree[j].flag == 0)
           {
               m2 = m1;
               x2 = x1;
               m1 = haffTree[j].weight;
               x1 = j;
           } else if(haffTree[j].weight<m2 && haffTree[j].flag == 0)
           {
               m2 = haffTree[j].weight;
               x2 = j;
           }
       }
       
       //3.将找出的两棵权值最小的子树合并为一棵子树
       haffTree[x1].parent = n + i;
       haffTree[x2].parent = n + i;
       //将2个结点的flag 标记为1,表示已经加入到哈夫曼树中
       haffTree[x1].flag = 1;
       haffTree[x2].flag = 1;
       //修改n+i结点的权值
       haffTree[n + i].weight = haffTree[x1].weight + haffTree[x2].weight;
       //修改n+i的左右孩子的值
       haffTree[n + i].leftChild = x1;
       haffTree[n + i].rightChild = x2;
   }
   
}

三、哈夫曼编码思想：

1、将构成电文的每个不同字符作为叶子结点，其权值为电文中字符的使用频率或次数，构造哈夫曼树；
2、此哈夫曼树中从根到每个叶子结点都有一条唯一的路径，对路径上各分支约定，做分支标识为0码，右标识为1码；
3、则从根结点到叶子结点的路径上分支的0、1码组成的字符串即为该叶子结点的哈夫曼编码。

void HaffmanCode(HaffNode haffTree[], int n, Code haffCode[])
{
    //1.创建一个结点cd
    Code *cd = (Code * )malloc(sizeof(Code));
    int child, parent;
    //2.求n个叶结点的哈夫曼编码
    for (int i = 0; i<n; i++)
    {
        //从0开始计数
        cd->start = 0;
        //取得编码对应权值的字符
        cd->weight = haffTree[i].weight;
        //当叶子结点i 为孩子结点.
        child = i;
        //找到child 的双亲结点;
        parent = haffTree[child].parent;
        //由叶结点向上直到根结点
        while (parent != 0)
        {
            if (haffTree[parent].leftChild == child)
                cd->bit[cd->start] = 0;//左孩子结点编码0
            else
                cd->bit[cd->start] = 1;//右孩子结点编码1
            //编码自增
            cd->start++;
            //当前双亲结点成为孩子结点
            child = parent;
            //找到双亲结点
            parent = haffTree[child].parent;
        }
        
         int temp = 0;

        for (int j = cd->start - 1; j >= 0; j--){
            temp = cd->start-j-1;
            haffCode[i].bit[temp] = cd->bit[j];
        }
      
        //把cd中的数据赋值到haffCode[i]中.
        //保存好haffCode 的起始位以及权值;
        haffCode[i].start = cd->start;
        //保存编码对应的权值
        haffCode[i].weight = cd->weight;
    }
}