Huffman哈夫曼树思想即代码

• 基础概念：

        路径长度：（以图示二叉树为例）

                结点的路径长度：从树根到分支结点的分支数目。A:1，B:2，C:3

                树的路径长度：从树根到每个结点的路径之和。 A:5 B:15

                带权路径长度：所有叶子结点的带权路径之和。

                                        a=1*5+2*15+3*40+4*10+4*30=315

                                        b=1*15+2*40+3*10+3*30=220

                带权路径最小的为哈夫曼树

                哈夫曼编码：左分支赋值为0，右分支赋值1（前提是待编码的树为哈夫曼树）

                        上图为例（该数不是哈夫曼树，只是进行讲解随便找的树）进行编码：

                        A：0

                        B：10

                        C：110

                        D：1110

                        E：1111

                哈夫曼树特点：不唯一  //因为相同的权值放在左边右边都可以，因此树的结果出来不一样

               哈夫曼树不唯一则哈夫曼编码也不唯一  //哈夫曼编码是根据哈夫曼树来的，树不一样自然编码也不同

---

• 创建哈夫曼树：

        思路：权值大的往上面放、权值小的往下面放

        先找出权值较小的两个，创建一棵树，将它加入集合，继续循环找，直到集合中剩余一个位置。将最小的放在左子树、次小的放在右子树。权值相加得到根节点权值。当两个值相等的时候，左右哪个放都行。

        思路演绎：

         此时形成的该树即为哈夫曼树

---

• 创建哈夫曼树代码：

//创建哈夫曼树
//不先创建根，从下往上走的，根是最后堆出来的
typedef struct node
{
    int weight;//权值
    int parent;//父节点下标
    int left;//左孩子下标
    int right;//右孩子下标
    int flag;//标记当前节点是否被选择过
}HaffNode;
 
void CreateHaff(int* weight, int n, HaffNode* haff)
{
    int i, j;
    int min1, min2;
    int min1x, min2x;//最小和次小的下标
    //初始化haff数组
    for (i = 0; i < 2 * n - 1; i++)
    {
        if (i < n)//前n个值是数组传过来的那n个，赋值
        {
            haff[i].weight = weight[i];
        }
        else//其余的赋初值为0
            haff[i].weight = 0;
        haff[i].parent = 0;
        haff[i].flag = 0;
        haff[i].left = 0;
        haff[i].right = 0;
    }
    //构建haff,其实就是构建数组元素
    for (int i = 0; i < n - 1; i++)
    {
        min1 = min2 = 65535;//65535是假设的一个最大值
        min1x = min2x = 0;
        //查找两个最小值
        for (j = 0; j < n + i; j++) {//j
            {//j
                //找最小的
                if (haff[j].weight < min1 && haff[j].flag == 0)
                {//是最小值并且还没被选则将其赋值给min1
                    min2 = min1;//1.先将现有最小值给min2
                    min2x = min1x;
                    min1 = haff[i].weight;
                    min1x = j;
                }
                //找次小的
                else if (haff[j].weight < min2 && haff[j].flag == 0)
                {
                    min2 = haff[i].weight;
                    min2x = j;
                }
            }
            //用最小的和次小的创建一颗树
            haff[n + i].weight = min1 + min2;
            haff[n + i].left = min1x;
            haff[n + i].right = min2x;
            //将最小的和次小的父结点下标修改
            haff[min1x].parent = n + i;
            haff[min2x].parent = n + i;
            //最小的和次小的flag重置,flag=1时说明结点已使用
            haff[min1x].flag = 1;
            haff[min2x].flag = 1;
        }
    }
}
    int main()
    {
        int weight[] = { 5,15,40,30,10 };
        int n = sizeof(weight) / sizeof(weight[0]);
        HaffNode* phaff = (HaffNode*)malloc(sizeof(HaffNode) * (2 * n - 1));//n个节点最终生成2n-1个结点
        CreateHaff(weight, n, phaff);
        return 0;
    }