哈夫曼树的简单实现
哈夫哈夫曼树（霍夫曼树）又称为最优二叉树。常用于哈夫曼编码，可以起压缩作用。
哈夫曼树的定义如下：
给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
定义中出现了以下几个概念
路径：树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。
路径长度：路径上的分枝数目称作路径长度。
树的路径长度：从树根到每一个结点的路径长度之和。
结点的带权路径长度：在一棵树中，如果其结点上附带有一个权值，通常把该结点的路径长度与该结点上的权值之积称为该结点的带权路径长度（weighted path length）
对于哈夫曼编码，百度百科给的解释挺好，有兴趣可以读一下
在数据通信中，需要将传送的文字转换成二进制的字符串，用0，1码的不同排列来表示字符。例如，需传送的报文为“AFTER DATA EAR ARE ART AREA”，这里用到的字符集为“A，E，R，T，F，D”，各字母出现的次数为{8，4，5，3，1，1}。现要求为这些字母设计编码。要区别6个字母，最简单的二进制编码方式是等长编码，固定采用3位二进制，可分别用000、001、010、011、100、101对“A，E，R，T，F，D”进行编码发送，当对方接收报文时再按照三位一分进行译码。显然编码的长度取决报文中不同字符的个数。若报文中可能出现26个不同字符，则固定编码长度为5。然而，传送报文时总是希望总长度尽可能短。在实际应用中，各个字符的出现频度或使用次数是不相同的，如A、B、C的使用频率远远高于X、Y、Z，自然会想到设计编码时，让使用频率高的用短码，使用频率低的用长码，以优化整个报文编码。
哈夫曼树的构造
假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：
(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
(3)从森林中删除选取的两棵树，并将新树加入森林；
(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。
举个例子，有如下八个权值，应该如何构造哈夫曼树呢？
先选出最小的两个权值，分别是2和3，将其合并，并将新的树放在森林中，将2和3作为新树的左右孩子，如图二
接下来继续选出最小的两个权值，分别是4和4，将其合并，并将新的树放在森林中，将4和4作为新树的左右孩子，如图三
继续重复以上步骤直至森林中只有一棵树
图八即是我们的最终的结果
代码实现
对于上面的例子，可以说主要思路就是对这个数组不停地取出最小的两个数然后相加再次放进这个数组里面。但对于代码，我们需要生成一棵实实在在的二叉树，那么这个森林该如何存储呢？如何取两个最小的相加再次放到数组里呢？
思考后决定，函数参数设置为一个数组。函数首先应该生成相应的节点，并且将这些节点放入vector中，对其进行排序之后，可以方便的找到最小的两个节点。取出后，生成一个新节点，将新节点放入vector中，原来最小的两个移除数组后重新排序，直到vector容器中只有一个元素为止，此元素就是哈夫曼树的根节点
二叉树结构体定义
struct BinaryTree
{
int value = DEFAULT;
BinaryTree *left = NULL;
BinaryTree *right = NULL;
};对sort函数重写比较方法
bool comp(const BinaryTree *a, const BinaryTree *b) {
return a->value > b->value;
}生成哈夫曼树，参数是一个数组，以及数组长度
BinaryTree* HuffmanTree(int nums[] ,int len)
{
//初始化vector集合
vector<BinaryTree*> nodes;
for (int i = 0; i < len; i++)
{
BinaryTree *node = new BinaryTree;
node->value = nums[i];
nodes.push_back(node);
}
//对vector进行降序排列
sort(nodes.begin(), nodes.end(), comp);
while (nodes.size() > 1)
{
//删除最小的两个点
BinaryTree *a = nodes[nodes.size() - 1];
BinaryTree *b = nodes[nodes.size() - 2];
nodes.pop_back();
nodes.pop_back();
//新增一个点
BinaryTree *node = new BinaryTree;
node->value = a->value + b->value;
node->left = a;
node->right = b;
nodes.push_back(node);
//重新排序
sort(nodes.begin(), nodes.end(), comp);
}
return nodes[0];
}测试代码
int main()
{
int a[5] = { 3,8,1,7,9 };
BinaryTree* tree = HuffmanTree(a, 5);
}