数据结构（赫夫曼树）

赫夫曼树

最优二叉树，WPL值最小（效率最高）；

• 结点的路径长度：从根节点到该结点的路径上的连接数
• 树的路径长度：：树中每个叶子结点的路径长度之和
• 结点带权路径长度：结点路径长度与结点权值的乘积
• WPL树的带权路径长度：是树中所有结点带权路径长度之和

　　利用结点的权重规划二叉树（权重大表示访问频繁），遍历二叉树的时让这些权重大的尽量早的被遍历到；有效的提高了遍历二叉树访问结点的效率

例如：判断成绩优，良，差；根据成绩分布情况规划最优判断结构树

根据赫夫曼树的定义，可以计算出未规划的二叉树：WPL=5+15*2+70*3+10*3=275

规划后WPL=10+70*2+15*3+5*3=210

构造赫夫曼树的过程：

1. 在森林中选出两颗根节点权值最小的二叉树（初始化，时候森林中的二叉树都是只有根节点）
2. 合并两颗二叉树，两二叉树为叶子结点，增加虚拟根结点，权重为左右孩子权之和
3. 再在森林中找出最小的权值的树，放在根节点旁边（整个过程都保持：权值小的放左边，权值大的放右边）
4. 重复 ③ 步骤直到森林取完

赫夫曼编码

可以有效的压缩数据，节省20%到90%的空间；

• 定长编码：像ASCII编码，每个字符都标准用两个字节（8个二进制位表示）
• 变长编码：单个编码的长度不一致，可根据整体出现的频率来调节
• 前缀码：没有任何码子是其他码字的前缀（赫夫曼编码就是最优的前缀名）

过程

1. 首先创建一个有序字符队列（以字符出现的频率从小到大排序）
2. 从队列中取出两个权值最小的结点，合并成一棵树，构造出虚拟根节点，权值为两子树的权和，最后把这个结点放入队列，保持队列有序
3. 重复3步骤，直到队列中只只剩下一个结点（即构建出的赫夫曼树）
4. 编码：根据赫夫曼树为叶子结点所代表的字符编码，向左一成编 0，向右一成编 1；直到到达叶子结点即为该字符编码完成；（将所有的字符写进一个编码表文件）
5. 解码：根据赫夫曼编码表，从赫夫曼树根节点出发，为0从根节点走向左子树，为1走向右子树；走到叶子结点时表示解码一个字符

#include<iostream>  
#include<string>  
using namespace std;
 
struct Node
{
    double weight;  
    string ch;  
    string code; 
    int lchild, rchild, parent;
};

void Select(Node huffTree[], int *a, int *b, int n)//找权值最小的两个a和b  
{
    int i;
    double weight = 0; //找最小的数
    for (i = 0; i <n; i++)
    {
        if (huffTree[i].parent != -1)     //判断节点是否已经选过
            continue;
        else
        {
            if (weight == 0)
            {
                weight = huffTree[i].weight;
                *a = i;
            }
            else
            {
                if (huffTree[i].weight < weight)
                {
                    weight = huffTree[i].weight;
                    *a = i;
                }
            }
        }
    }
    weight = 0; //找第二小的数
    for (i = 0; i < n; i++)
    {
        if (huffTree[i].parent != -1 || (i == *a))//排除已选过的数
            continue;
        else
        {
            if (weight == 0)
            {
                weight = huffTree[i].weight;
                *b = i;
            }
            else
            {
                if (huffTree[i].weight  < weight)
                {
                    weight = huffTree[i].weight;
                    *b = i;
                }
            }
        }
    }
    int temp;
    if (huffTree[*a].lchild < huffTree[*b].lchild)  //小的数放左边
    {
        temp = *a;
        *a = *b;
        *b = temp;
    }
}

void Huff_Tree(Node huffTree[], int w[], string ch[], int n)
{
    for (int i = 0; i < 2 * n - 1; i++) //初始过程
    {
        huffTree[i].parent = -1;    
        huffTree[i].lchild = -1;    
        huffTree[i].rchild = -1;  
        huffTree[i].code = "";
    }
    for (int i = 0; i < n; i++)       
    {
        huffTree[i].weight = w[i];  
        huffTree[i].ch = ch[i];     
    }
    for (int k = n; k < 2 * n - 1; k++)
    {
        int i1 = 0;
        int i2 = 0;
        Select(huffTree, &i1, &i2, k); //将i1，i2节点合成节点k
        huffTree[i1].parent = k;   
        huffTree[i2].parent = k;
        huffTree[k].weight = huffTree[i1].weight + huffTree[i2].weight;
        huffTree[k].lchild = i1;
        huffTree[k].rchild = i2;
    }
}
 
void Huff_Code(Node huffTree[], int n)
{
    int i, j, k;
    string s = "";
    for (i = 0; i < n; i++)  
    {
        s = "";         
        j = i;                
        while (huffTree[j].parent != -1) //从叶子往上找到根节点
        {
            k = huffTree[j].parent;
            if (j == huffTree[k].lchild) //如果是根的左孩子，则记为0
            {
                s = s + "0";
            }
            else               
            {
                s = s + "1";
            }
            j = huffTree[j].parent; 
        }
        cout << "字符 " << huffTree[i].ch << " 的编码：";
        for (int l = s.size() - 1; l >= 0; l--)    
        {
            cout << s[l];
            huffTree[i].code += s[l]; //保存编码
        }
        cout << endl;
    }
}

string Huff_Decode(Node huffTree[], int n,string s)
{
    cout << "解码后为：";
    string temp = "",str="";//保存解码后的字符串
    for (int i = 0; i < s.size(); i++)
    {
        temp = temp + s[i];
        for (int j = 0; j < n; j++)
        {    
            if (temp == huffTree[j].code)
            {
                str=str+ huffTree[j].ch;
                temp = "";
                break;
            }    
            else if (i == s.size()-1&&j==n-1&&temp!="")//全部遍历后没有
            {
                str= "解码错误！";
            }
        }
    }
    return str;
}

int main()
{
    //编码过程
    const int n=5;
    Node huffTree[2 * n];
    string str[] = { "A", "B", "C", "D", "E"};
    int w[] = { 30, 30, 5, 20, 15 };
    Huff_Tree(huffTree, w, str, n);
    Huff_Code(huffTree, n);
    //解码过程
    string s;
    cout << "输入编码：";
    cin >> s;
    cout << Huff_Decode(huffTree, n, s)<< endl;;
    system("pause");
    return 0;
}

赫夫曼编码