二叉树的应用-哈夫曼编码

哈夫曼树

哈夫曼树是带权路径长度最短的树，又称最优二叉树，权值较大的结点离根较近。

1. 树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。
2. 若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。
3. 结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。
4. 树的路径长度是从树根到每一结点的路径长度之和，记为 ，N个权值 构成一棵有 N 个叶结点的二叉树，相应的叶结点的路径长度为 。

哈夫曼树的构建思路

1. 将 看成是有n棵树的森林(每棵树仅有一个结点)；
2. 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
3. 从森林中删除选取的两棵树，并将新树加入森林；
4. 重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。

哈夫曼编码

哈夫曼编码，完全依据字符出现概率来构造异字头的平均长度最短的码字。

基本原理

    如果一个字符在一段文档当中出现的次数多,它的编码就相应的短,如果一个字符在一段文档当中出现的次数少,它的编码就相应的长.当编码中,各码字的长度严格按照对应符号出现的概率大小进行逆序排列时,则编码的平均长度是最小的.

代码实现

利用得到的概率值创建哈夫曼树

void HaffMan(int weight[],int n ,HaffNode *haffTree){

    int j,m1,m2,x1,x2;
    //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].lChild = -1;
            haffTree[i].rChild = -1;
    }
    for (int i = 0; i < n-1; i++)
    {
    //存储最小的两个值
    m1 = m2 = MaxValue;
    //存储最小的两个值的下标
    x1 = x2 = 0;
    //循环找出所有权重中最小的两个值
    for ( j = 0; j < n + i; j++)
    {
    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;
    }
    }
    //找出两颗权重最小的值合并
    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].lChild = x1;
            haffTree[n + i].rChild = x2;
    }
}

对哈夫曼树进行编码,并把编码后得到的码字存储起来

void HaffmanCode(HaffNode haffTree[], int n, HaffCode haffCode[]){
    //1.创建一个结点cd
    HaffCode *cd = (HaffCode* )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;
    }
}