哈夫曼树

哈夫曼树（Huffman Tree）是最优二叉树。给定n个权值作为n个叶子的结点，构造一棵二叉树，若树的带权路径长度达到最小，这棵树则被称为哈夫曼树

1.路径和长度

定义：在一棵树中，从一个结点往下可以达到的孩子和孙子结点之间的通路称为路径。路径中分支的数目称为路径长度，若根节点的的层数为 1，则从根节点到L层结点的路径长度为L-1
例：100和80的路径长度是1，50和30的路径长度是2，20和10的路径长度是3

2.结点的权及带权路径长度

定义：若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。
例：节点20的路径长度是3，它的带权路径长度= 路径长度 * 权 = 3 * 20 = 60。

3.树的带权路径长度

定义：树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL
例：树的WPL= 1100 + 280 + 320 + 310 = 100 + 160 + 60 + 30 = 350

哈夫曼编码

构造哈夫曼树的目的是为了完成哈夫曼编码，哈夫曼编码是一种变长、极少多余编码方案。相对于等长编码，将文件中每个字符转换为固定个数的二进制位，变长编码根据字符使用频率的高低，使用了不同长度的二进制位与不同字符进行映射，使得频率高的字符对应的二进制位较短，频率低的字符对应的二进制位较长。使得源文件利用哈夫曼编码后的二进制序列大小，相对于原编码方案能够有较大缩小，如此即完成了文件的压缩。哈夫曼编码能够用于实现文件的无损压缩，自然保证了文件解压缩过程的正确性，即二进制序列向字符的映射过程不会发生错乱。解码过程的正确性通过哈夫曼树的结构可以得到证明，以哈夫曼树中的每个叶子节点作为一个字符，则从根节点到每个叶子的路径都是唯一的，即不存在一个叶子节点的路径是另一个叶子节点的路径前缀。满足该特性的编码称之为前缀编码，所以哈夫曼编码中能够实现二进制到字符的正确映射。

哈夫曼树的构造规则

假设哈夫曼树有n个权值，n个权值分别时w1,w2,w3...wn

1. 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
2. 在森林中选出根结点的权值最小的两棵树进行合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
3. 从森林中删除选取的两棵树，并将新树加入森林；
4. 重复(02)、(03)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。
   例：{7，8，9，10，19}构造哈夫曼树
   第一步：
   第二步：
   第三步：
   第四步：
   第五步：
   第1步：创建森林，森林包括5棵树，这5棵树的权值是7，8，9，10，19
   第2步：在森林中，选择根节点权值最小的两棵树7和8进行合并，将它们作为一颗新树的左右孩子，新树的权值是左右孩子的权值之和，新树的权值是15。 然后，将树7和树8从森林中删除，并将新的树(树11)添加到森林中。
   第3步：在森林中，选择根节点权值最小的两棵树9，10进行合并。得到的新树的权值是19， 然后，将树9和树10从森林中删除，并将新的树19添加到森林中。
   第4步：在森林中，选择根节点权值最小的两棵树15，19进行合并。得到的新树的权值是34。 然后，将树15和树19从森林中删除，并将新的树34添加到森林中。
   第5步：在森林中，选择根节点权值最小的两棵树19和34进行合并。得到的新树的权值是53。 然后，将树19和树34从森林中删除，并将新的树53添加到森林中。
   此时，森林中只有一棵树53。

Void CreateHuffmanTree(HuffmanTree &HT,int n)
{
    if(n<1)
    return ;
    m=2*n-1;
    HT=new HTNode[m+1];  //0号单元未用，需动态分配m+1个单元，HT[m]表示根结点
    for(i=1;i<m;++i)     //将1到m号单元的双亲，左孩子，右孩子的下标初始化为0
    {
        HT[i].parent=0;
        HT[i].lchild=0;
        HT[i].rchild=0;
    }
    for(i=1;i<m;++i) //输入前n个单元中叶子结点的权值
    {
        cin>>HT[i].weight;
    }  

    for(i=n+1;i<m;++i)
    {
        //通过n-1次的选择删除合并来创建哈夫曼树
        Select(HT,i-1,s1,s2);
        //在HT[k](l<=k<=i-1)中选择两个双亲域为0且权值最小的结点，并返回在HT中的序号s1和s2
        HT[si].parent=i;
        HT[s2].parent=i;
        //得到新结点i,从森林中删除s1,s2，将s1,s2的双亲0改为1
        HT[i].lchild=s1;
        HT[i].rchild=s2;//s1,s2分别为i的左右孩子
        HT[i].weight=HT[s1].weight+HT[s2].weight;//i的权值为左右孩子之和
    }   
}