谈谈哈夫曼树

今天，小编来分享下有关“哈夫曼树”的一些知识点。当然如若有误的话，也请各位江湖好汉指点迷津。在介绍“哈夫曼树”前，我们需要先弄清楚和树有关的3个概念，我们以下图为例子来进行分析。

图1
概念1：什么是“路径”和“路径长度”
在一棵树中，从一个结点到另一个结点所经过的所有结点，被我们称为两个结点之间的路径。
例如上述例子中，从根节点A到叶子节点F的路径就为：A->B->D->F；
在一棵树中，从一个结点到另一个结点所经过的“边”的数量，被我们称为两个结点之间的路径长度。
例如，从根节点A到叶子节点F经过的边有3条，因此它的路径长度就为3。
概念2：结点的权及带权路径长度
树的每一个结点，都可以拥有自己的“权重”（Weight），权重在不同的算法当中可以起到不同的作用。
结点的带权路径长度，是指树的根结点到该结点的路径长度，和该结点权重的乘积。
图2
上图2中结点F的权重是10，从根结点A到结点F的路径长度是3，因此结点F的带权路径长度是 3 X 10= 30。
概念3：树的带权路径长度
在一棵树中，所有叶子结点的带权路径长度之和，被称为树的带权路径长度，也被简称为WPL。
在上图2中，该树的带权路径长度为WPL=1100+250+320+310=290。
那了解了这几个概念后，我们来看看，究竟什么是“哈夫曼树”？
其实啊，所谓的哈夫曼树（Huffman Tree）就是在叶子结点和权重确定的情况下，带权路径长度最小的二叉树，它也被称为最优二叉树。需要注意的是，同样叶子结点所构成的哈夫曼树可能不止一颗哦。
我们以{2，3，7，9，18，25}为例，来构造一棵哈夫曼树。
第一步：构造“森林”
我们把每一个叶子结点，都当做一颗独立的树（只有根结点的树），这样就形成了一个森林：
第一步
我们使用队列，根据权值大小存储所有叶子结点。
第二步：选择当前权值最小的两个结点，生成新的父结点。
借助辅助队列，我们可以找到权值最小的结点2和3，并根据这两个结点生成一个新的父结点，父节点的权值是这两个结点权值之和。
第二步
第三步：从队列中移除上一步选择的两个最小结点，把新的父节点加入队列。也就是从队列中删除2和3，插入5，并且仍然保持队列的升序。
第三步
第四步：选择当前权值最小的两个结点，生成新的父结点。
这是对第二步的重复操作。当前队列中权值最小的结点是5和7，生成新的父结点权值是5+7=12。
第四步
第五步：从队列中移除上一步选择的两个最小结点，把新的父节点加入队列。
这是对第三步的重复操作，也就是从队列中删除5和7，插入12，并且仍然保持队列的升序。
第五步
第六步：选择当前权值最小的两个结点，生成新的父结点。
这是对第二步的重复操作。当前队列中权值最小的结点是9和12，生成新的父结点权值是9+12=21。
第六步
第七步：从队列中移除上一步选择的两个最小结点，把新的父节点加入队列。
这是对第三步的重复操作，也就是从队列中删除9和12，插入21，并且仍然保持队列的升序。
第七步
第八步：选择当前权值最小的两个结点，生成新的父结点。
这是对第二步的重复操作。当前队列中权值最小的结点是18和21，生成新的父结点权值是18+21=39。
第八步
第九步：从队列中移除上一步选择的两个最小结点，把新的父节点加入队列。
这是对第三步的重复操作，也就是从队列中删除18和21，插入39，并且仍然保持队列的升序。
第九步
第十步：选择当前权值最小的两个结点，生成新的父结点。
这是对第二步的重复操作。当前队列中权值最小的结点是25和39，生成新的父结点权值是25+39=64。
第十步
第十一步：从队列中移除上一步选择的两个最小结点，把新的父节点加入队列
这是对第三步的重复操作，也就是从队列中删除25和39，插入64。
第十一步
此时，队列中仅有一个结点，说明整个森林已经合并成了一颗树，而这棵树就是我们想要的哈夫曼树。
哈夫曼树
下面代码没有使用队列来实现，有兴趣可以自行动手实现，借助C++提供的STL模板等。

#include<iostream>
#include<iomanip>
#include<stack>
using namespace std;
struct element
{
    int weight;
    int lchild, rchild, parent;
};
class HTree
{
    element *node;
    int n, m;
    stack<int> code;
    int setcode(int weight);
public:
    HTree(int _n, int _weight[]);
    ~HTree();
    void select(int &s1,int &s2);
    void createHT();
    int search(int weight);
    void print();
    void printHTcode();
};
HTree::HTree(int _n, int _weight[])
{
    n = _n;
    m = 2 * n - 1;//n个元素需要2n-1个空间
    node = new element[m];
    for (int i = 0; i < n; i++)
    {
        node[i].weight = _weight[i];
    }
    for (int i = 0; i < m; i++)
    {
        node[i].lchild = node[i].rchild = node[i].parent = 0;//初始化为0
    }
    createHT();
}
HTree::~HTree()
{
    delete node;
}
void HTree::select(int &s1, int &s2)
{
    for (int i = 0; i < n; i++)
    {
        if (node[i].parent == 0)
        {
            s1 = i;//临时元素
            break;
        }
    }
    for (int i = 0; i < n; i++)
    {
        if ((node[i].weight < node[s1].weight) && (node[i].parent == 0))
        {
            s1 = i;
        }
    }
    cout<<node[s1].weight<<endl;
    for (int i = 0; i < n; i++)
    {
        if ((node[i].parent == 0)&&(i!=s1))
        {
            s2 = i;
            break;
        }
    }
    for (int i = 0; i < n; i++)
    {
        if ((node[i].weight < node[s2].weight) && (node[i].parent == 0) && (i != s1))
        s2 = i;
    }
    cout<<node[s2].weight<<endl;
}
void HTree::createHT()
{
    for (int i = n; i < m; i++)
    {
        int s1, s2;//左小右大
        select(s1,s2);
        node[s1].parent = i;
        node[s2].parent = i;
        node[i].lchild = s1;
        node[i].rchild = s2;
        node[i].weight = node[s1].weight + node[s2].weight;
        n++;
    }
}
int HTree::setcode(int weight)
{
    int location, parent, k;//k为移动指针
    int count = 0;
    location = search(weight);
    k = location;
    parent = node[location].parent;
    while ((node[k].parent != 0) && (k != -1))
    {
        if (node[parent].lchild == k)
        {
            code.push(0);
        }
        else
        {
            code.push(1);
        }
        k = node[k].parent;
        parent = node[k].parent;
        count++;
    }
    if (k == -1)
        cout << "未找到！" <<endl;
    return count;
}
int HTree::search(int weight)
{
    int result = -1;
    for (int i = 0; i < m; i++)
    {
        if (node[i].weight == weight)
        {
            result = i;
        }
    }
    return result;
}
void HTree::print()
{
    cout << "索引 权值 双亲 左孩子 右孩子" << endl;
    cout << left;//左对齐

    for (int i = 0; i < m; i++)
    {
        cout << setw(5) << i << " ";
        cout << setw(6) << node[i].weight << " ";
        cout << setw(6) << node[i].parent << " ";
        cout << setw(6) << node[i].lchild << " ";
        cout << setw(6) << node[i].rchild << endl;
    }
    cout << "哈夫曼树打印完毕"<<endl;
}
void HTree::printHTcode()
{
    cout << "请输入要查询的编码的权值" << endl;
    int weight, size;
    cin >> weight;
    size = setcode(weight);
    cout << "权值" <<weight<< "编码长度" <<size<< endl;
    cout << "编码结果为";
    for (int i = 0; i < size; i++)
    {
        cout << code.top()<<" ";
        code.pop();
    }
    cout << endl;
}
int main()
{
    cout << "请输入要构造的哈夫曼树的结点个数" <<endl;
    int n, *weight;
    cin >> n;
    weight = new int[n+1];
    cout << "请输入这" << n << "个元素的权值" << endl;
    for (int i = 0; i < n; i++)
    {
        cin >> weight[i];
    }
    HTree test(n, weight);
    test.print();
    test.printHTcode();
    system("pause");
    return 0;
}

运行截图：

运行截图