您当前位置：首页 > 数据库 > 数据库应用 > 数据结构－赫夫曼树及其应用

数据结构－赫夫曼树及其应用

来源：程序员人生发布时间：2015-05-12 09:18:06 阅读次数：3477次

赫夫曼树及其利用

    赫夫曼(Huffman)树又称最优树，是1类带权路径长度最短的树，有着广泛的利用。

1 基本概念
① 结点路径：从树中1个结点到另外一个结点的之间的分支构成这两个结点之间的路径。
② 路径长度：结点路径上的分支数目称为路径长度。
③ 树的路径长度：从树根到每个结点的路径长度之和。
④ 结点的带权路径长度：从树的根结点到该结点的的路径长度与结点的权(值)的乘积。
权(值)：各种开消、代价、频度等的抽象称呼。
⑤ 树的带权路径长度：树中所有叶子结点的带权路径长度之和，记做：
WPL=w1?l1+w2?l2+?+wn?ln=∑wi?li (i=1,2,?,n)
其中：n为叶子结点的个数；wi为第i个结点的权值； li为第i个结点的路径长度。
⑥ Huffman树：具有n个叶子结点(每一个结点的权值为wi) 的2叉树不止1棵，但在所有的这些2叉树中，一定存在1棵WPL值最小的树，称这棵树为Huffman树(或称最优树) 。

Huffman树的构造

根据n个权值 {w1, w2, ?,wn}，构造成n棵2叉树的集合F={T1, T2, ?,Tn}，其中每棵2叉树只有1个权值为wi的根结点，没有左、右子树；
② 在F当选取两棵根结点权值最小的树作为左、右子树构造1棵新的2叉树，且新的2叉树根结点权值为其左、右子树根结点的权值之和；
③ 在F中删除这两棵树，同时将新得到的树加入F中；
④ 重复②、③，直到F只含1颗树为止。
构造Huffman树时，为了规范，规定：
F={T1,T2, ?,Tn}中权值小的作为新构造的2叉树的左子树，权值大的作为右子树；在取值相等时，深度小的作为新构造的2叉树的左子树，深度大的作为右子树。

例：构造权值集合为W={8, 3, 4, 6, 5, 5}的 Huffman树。

赫夫曼编码及其算法

1 Huffman编码
在电报收发等数据通讯中，常需要将传送的文字转换成由2进制字符0、1组成的字符串来传输。为了使收发的速度提高，就要求电文编码要尽量地短。
要设计长短不等的编码，须保证任意字符的编码都不是另外一个字符编码的前缀，这类编码称为前缀编码。
Huffman树可以用来构造编码长度不等且译码不产生2义性的编码。
设电文中的字符集C={c1,c2, ?,ci, ?,cn}，各个字符出现的次数或频度集W={w1,w2, ?,wi, ?,wn}。
Huffman编码方法
以字符集C作为叶子结点，次数或频度集W作为结点的权值来构造 Huffman树。规定Huffman树中左分支代表“0”，右分支代表“1” 。
从根结点到每一个叶子结点所经历的路径分支上的“0”或“1”所组成的字符串，为该结点所对应的编码，称之为Huffman编码。
由于每一个字符都是叶子结点，不可能出现在根结点到其它字符结点的路径上，所以1个字符的Huffman编码不多是另外一个字符的Huffman编码的前缀。
若字符集C={a, b, c, d, e, f}所对应的权值集合为W={8, 3, 4, 6, 5, 5}，如图6⑵5所示，则字符a,b, c,d, e,f所对应的Huffman编码分别是：10，010，011，00 ，110，111。

Huffman编码算法实现

(1) 数据结构设计
Huffman树中没有度为1的结点，有n个叶子结点的Huffman树共有2n⑴个结点，则可存储在大小为2n⑴的1维数组中。实现编码的结点结构如图6⑵6所示。
缘由：
◆ 求编码需从叶子结点动身走1条从叶子到根的路径；
◆ 译码需从根结点动身走1条到叶子结点的路径。

结点类型定义：
#define  MAX_NODE  200     /*   Max_Node>2n⑴  */ 
typedef struct
{    char  elem;     // 待编码字符     
      unsigned int Weight ;    /*  权值域  */
unsinged int Parent , Lchild , Rchild ;
} HTNode, *HuffmanTree ;
typedef char **HuffmanCode; 
typedef struct Node
{
           char elem; 
           unsigned int m_weight; 
}Node; // 字符及其权值

(2) Huffman树的生成
算法实现
  待编码字符的输入：
         cout<<"输入要编码字符个数:" ; 
        cin>>n; 
        w=(Node *)malloc(n*sizeof(Node)); 
        cout<<"输入字符及其对应的权值："<<endl; 
        for(i=0;i<n;i++)
        { 
            cin>>c>>wei; 
            w[i].elem=c; 
            w[i].m_weight=wei; 
        }


从前n个结点中，选取权值比较小的两个：最小的下标为s1，次小的下标s2
void Select(HuffmanTree HT,int n,int &s1,int &s2) 
{ int i;    s1=s2=0; 
for(i=1;i<=n;i++)
{   if((HT[i].m_weight<HT[s2].m_weight)&&(HT[i].parent==0)&&(s2!=0))
    {   if(HT[i].m_weight<HT[s1].m_weight)
        {   s2=s1; s1=i;    }
        else         s2=i; 
    }
     if((s1==0||s2==0)&&HT[i].parent==0)
    {   if(s1==0) s1=i; 
        else if(s2==0)
        {   if(HT[i].m_weight<HT[s1].m_weight)
            {       s2=s1; s1=i;    } 
            else s2=i; 
        } // end of else if 
    } // end of if
} // end of for 
    return; 
}

新结点的构造
    for(i=n+1;i<=m;++i)
    { 
        Select((*HT),i-1, s1,s2); 
        (*HT)[s1].parent=i; (*HT)[s2].parent=i; 
        (*HT)[i].lchild=s1;
        (*HT)[i].rchild=s2; 
        (*HT)[i].m_weight=(*HT)[s1].m_weight+(*HT)[s2].m_weight; 
    }

(3) Huffman编码算法
根据出现频度(权值)Weight，对叶子结点的Huffman编码有两种方式：
① 从叶子结点到根逆向处理，求得每一个叶子结点对应字符的Huffman编码。
② 从根结点开始遍历整棵2叉树，求得每一个叶子结点对应字符的Huffman编码。
由Huffman树的生成知，n个叶子结点的树共有2n⑴个结点，叶子结点存储在数组HT中的下标值为1∽n。
① 编码是叶子结点的编码，只需对数组HT[1…n]的n个权值进行编码；
② 每一个字符的编码不同，但编码的最大长度是n。

编码
    (*HC)=(HuffmanCode)malloc(n*sizeof(char*)); 
    cd = (char *)malloc(n*sizeof(char)); 
    cd[n-1]=''; 
    for(i=1;i<=n;++i)
    { 
        start=n⑴; 
        for(c=i,f=(*HT)[i].parent;f!=0;c=f,f=(*HT)[f].parent)
        { 
            if((*HT)[f].lchild==(unsigned int)c) 
                         cd[--start]='0'; 
            else cd[--start]='1'; 
        } 

        (*HC)[i]=(char *)malloc((n-start)*sizeof(char));
        strcpy((*HC)[i],&cd[start]); 
    }

生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生