频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
最优二叉树&&哈夫曼编码
2013-01-04 13:15:00           
收藏   我要投稿
树的路径长度

树的路径长度是从树根到树中每一结点的路径长度之和。在结点数目相同的二叉树中,完全二叉树的路径长度最短。

 

树的带权路径长度(weighted path length of tree,wpl)

结点的权值:在一些应用中,赋予树中结点的一个有某种意义的实数、

结点的带权路径长度:结点到树根之间的路径长度与该结点上权的乘积

树的带权路径长度(wpl):定义为树中所有结点的带权路径长度之和

 

最优二叉树

在权为w1,w2,...,wn的n个叶子结点所构成的所有二叉树中,带权路径长度最小(即代价最小)的二叉树成为最优二叉树。

注意:

叶子上的权值均相同时,完全二叉树一定是最优二叉树,否则完全二叉树不一定是最优二叉树。

最优二叉树中,权值越大的叶子结点离根越近

最优二叉树的形态不唯一,wpl最小

 

构造最优二叉树

 

哈夫曼算法

根据给定的n个权值w1,w2,...,wn构成n棵二叉树的森林F={T1,T2,..,Tn},其中每棵二叉树Ti中只有一个权值为wi的根节点,其左右子树均为空。

在森林F中选出两棵根结点权值最小的树(当这种的树不止两棵时,可以从中任选两棵),将这两棵树和并称一棵新树,为了保证新树仍是二叉树,需要增加一个新结点作为新树的根,并将所选的两棵树根分别作为新树的左右孩子,将这两个孩子的权值之和作为新树根的权值

对新的森林F重复2,直到森林F只剩一棵树为止。

注意

初始森林中的n棵二叉树,每棵树都有一个孤立的结点,它们既是根,又是叶子

n个叶子结点的哈夫曼树需要经过n-1次合并,产生n-1个新结点。最终求得的哈夫曼树共有2n-1个结点

哈夫曼树是严格的二叉树,没有度数为1的分支结点

 

哈夫曼树存储结构

[cpp] 

#include <stdio.h>  

#include <stdlib.h>  

#include <string.h>  

#define MAX_SIZE 100  

#define MIN_NUM 1000000  

  

struct hfmcode  

{  

    int weight;  

    int lchild;  

    int rchild;  

    int parent;  

};  

 

注意:

因此数组下界为0,因此用-1表示空指针。树中某结点的lchild,rchild,parent不等于-1时,它们分别是该结点的左、右孩子和双亲结点在向量中的下标。

parent域的作用:其一是查找双亲结点更为简单。其二是可通过判定parent值是否为-1来区分根和非根结点。

 

实现代码

(1)初始化,将T[0..m-1]中的2n-1个结点里的三个指针均置空(==-1),权值置为0.

[cpp] 

void initHuffmantree(struct hfmcode *tree, int len)  

{  

    int i;  

  

    for(i = 0; i < len; i ++)  

    {  

        tree[i].weight = 0;  

        tree[i].lchild = -1;  

        tree[i].rchild = -1;  

        tree[i].parent = -1;  

    }  

}  

 

 

(2)输入,读入n个叶子的权值存于向量的前n个分量(即T[0..n-1])中。

[cpp]  

int main()  

{  

    int n, m, i;  

    struct hfmcode hfmtree[MAX_SIZE];  

  

    while(scanf("%d", &n) != EOF)  

    {  

        /*哈夫曼树总共结点数*/  

        m = 2 * n - 1;  

  

        /*初始化哈夫曼树*/  

        initHuffmantree(hfmtree, m);  

  

        /*权限赋值*/  

        for(i = 0; i < n; i ++)  

        {  

            scanf("%d", &hfmtree[i].weight);  

        }  

  

        /*构造哈夫曼树*/  

        createHuffmantree(hfmtree, n, m);  

  

        printf("%d\n", hfmtree[m - 1].weight);  

    }  

  

    return 0;  

}  

 

 

(3)合并,对森林中的树共进行n-1次合并,所产生的新结点依次放入向量T的第i个分量中(n<=i<=m-1).每次合并分两步:

在当前森林T[0..i-1]的所有结点中,选取权最小和次小的两个根节点T[p1]和T[p2]作为合并对象,这里0<=p1,p2<=i-1

将根为T[p1]和T[p2]的两棵树作为左右子树合并为一棵新的树,新的树根是新节点T[i].具体操作是:将T[p1]和T[p2]的parent置为i,将T[i]的lchild和rchild分别置为p1和p2.新结点T[i]的权值置为T[p1]和T[p2]的权值之和。

合并后,T[p1]和T[p2]在当前森林中已不再是根,因为它们的双亲指针均已指向了T[i],所以下次合并时不会被选中为合并对象。

[cpp]  

void createHuffmantree(struct hfmcode *tree, int n, int m)  

{  

    int m1, m2, i, loc1, loc2, k;  

  

    for(i = n; i < m; i ++)  

    {  

        /*初始化最小值、次小值*/  

        m1 = m2 = MIN_NUM;  

        loc1 = loc2 = -1;  

        /*在尚未构造二叉树的节点中查找权值最小的两棵树*/  

        for(k = 0; k < i; k ++)  

        {  

            if(tree[k].parent == -1)  

            {  

                if(tree[k].weight < m1)  

                {  

                    m2 = m1;  

                    loc2 = loc1;  

                    m1 = tree[k].weight;  

                    loc1 = k;  

                }else if(tree[k].weight < m2)  

                {  

                    m2 = tree[k].weight;  

                    loc2 = k;  

                }  

            }  

        }  

  

        /*修改2个小权重节点的双亲*/  

        tree[loc1].parent = i;  

        tree[loc2].parent = i;  

  

        /*修改parent的权重*/  

        tree[i].weight = tree[loc1].weight + tree[loc2].weight;  

  

        /*修改parent的孩子*/  

        tree[i].lchild = loc1;  

        tree[i].rchild = loc2;  

    }  

}  

 

哈夫曼编码

 

编码和解码

数据压缩的过程成为编码。即将文件中的每个字符均转换为一个唯一的二进制位串

数据解压过程成为解码。即将二进制位串转换位对应的字符

 

前缀码&&最优前缀码

对字符集进行编码时,要求字符集中任一字符的编码都不是其它字符的编码的前缀,这种编码成为前缀编码

 

平均码长或文件总长最小的前缀编码成为最优前缀编码,最优前缀编码对文件的压缩效果亦最佳。

点击复制链接 与好友分享!回本站首页
相关TAG标签 哈夫曼 编码
上一篇:设置CoreText基本属性
下一篇:select函数详解
相关文章
图文推荐
文章
推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站