1 构造原理

假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：
(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
(3)从森林中删除选取的两棵树，并将新树加入森林；
(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。

显然对n个权值，构造哈夫曼树树需要合并n-1次，形成的树结点总数为2n-1；

2 代码实现

根据哈夫曼树的构造原理，为方便实现，我们使用数组来存储每个结点,其命名为Tree；

2.1 节点结构

节点具有以下结构：
weight：权值
parent：父节点在数组中的位置（同时用来判断该节点是否已经参与了合并）
lchild, rchild：左右孩子结点在数组中的位置
code：该结点所分配的编码

//结点结构
struct HNode{
	float weight;  //权值
	int parent;  //父节点，父节点主要判定一个结点是否已经加入哈夫曼树
	int lchild, rchild;  //左孩子，右孩子
	string code;  //记录结点编码
	HNode() {
		weight = 0;
		parent = lchild = rchild = -1;
		code = "";
	}
	HNode(float w) {
		weight = w;
		parent = lchild = rchild = -1;
		code = "";
	}
};

2.2 关键成员函数解析

2.2.1 构造函数

为了判定一个结点是否已经加入哈夫曼树中，可通过parent域的值来确定。初始时parent的值为-1，当某结点加入到树中时，该节点parent域的值为其双亲结点在数组中的下标。

构造哈夫曼树时，首先将n个权值的叶子结点存放到数组haftree的前n个分量中，然后不断将两棵子树合并为一棵子树，并将新子树的根节点顺序存放到数组Tree的前n个分量的后面。

哈夫曼算法用伪代码描述为：
1、数组haftree初始化，所有数组元素的双亲、左右孩子都置为-1；
2、数组haftree的前n个元素的权值置给定权值；
3、进行n-1次合并:
3.1 在二叉树集合中选取两个权值最小的根节点，其下标分别为i1，i2;
3.2 将二叉树i1、i2合并为一棵新的二叉树k。

构造函数输入为权值数组和数组长度

	//构造哈夫曼树，输入权值数组 和 数组长度n
	void Create(float* a, int n) {
		TreeSize = 2 * n - 1;  //确定哈夫曼树的结点个数
		Tree = new HNode[TreeSize];
		//权值数组保存在哈夫曼树数组前n个数值
		for (int i = 0; i < n; i++)
		{
			Tree[i].weight = a[i];
		}

		//开始进行n-1次合并操作，形成一颗哈夫曼树
		int s1, s2;
		int nextPos = (TreeSize + 1) / 2; //记录下一个插入位置,起始为n
		for (int i =0; i < (TreeSize-1)/2; i++) {
			SelectTwoMin(nextPos, s1, s2); //找到数组中权值最小的两个点
			//对Tree中新节点的孩子结点及权值赋值
			Tree[nextPos].lchild = s1;
			Tree[nextPos].rchild = s2;
			Tree[nextPos].weight = Tree[s1].weight + Tree[s2].weight;
			//给这两个结点分配父节点(意味着两个结点已加入哈夫曼树)
			Tree[s1].parent = Tree[s2].parent = nextPos;
			nextPos++;  //插入位置后移一位
		}
	}

2.2.2 寻找最小的两个点

先寻找到前两个还未合并的点（parent=-1），在和后面未合并过的点比较权值，确定最终最小的两个点,并确保权值小的在前面；

	//寻找数组中权值最小的两个点
	void SelectTwoMin(int nextPos,int &s1, int &s2) 
	{
		//找到第一个未加入哈夫曼树的结点,标记为s1
		int i=0;
		while (Tree[i].parent != -1) {
			i++;
		}
		//从s2后一位开始找到第二个未加入哈夫曼树的结点,标记为s2
		s1 = i;
		int j = i + 1;
		while (Tree[j].parent != -1) {
			j++;
		}
		s2 = j;
		//调整s1和s2对应权值大小，确保s1对应点的权值更小，从而寻找更小的点时只需和s2比较
		KeepOrder(s1, s2);

		//从s2后一位开始，和s1,s2比较，确定数组中权值最小的两个点
		for (int k = j + 1; k <nextPos; k++) 
		{
			if (Tree[k].parent == -1) {
				if (Tree[k].weight < Tree[s2].weight) {
					s2 = k;
					//找到小于s2的点后，需和s1比较确定大小顺序
					KeepOrder(s1, s2);
				}
			}
		}
	}
	//确保n1对应结点的权值小于n2
	void KeepOrder(int& n1,int& n2) {
		if (Tree[n1].weight > Tree[n2].weight)
		{
			float tmp = n1;
			n1 = n2;
			n2 = tmp;
		}
	}

2.2.3 对构造好的哈夫曼树进行编码并输出

这里使用层次遍历，借助一个队列实现；孩子结点的编码由父节点的code加上'1'/'0'（根据其处于父节点的左孩子还是右孩子而定，左孩子为'1'）;
只输出叶子结点的编码.也可以在编码完成后直接输出Tree数组的前n个的结点的编码；

	//对树中结点编码并输出
	void PrintCoder() 
	{
		cout << "index weight     code" << endl;
		queue<int> codeQueue;  //只保存编号
		int tmp;
		codeQueue.push(TreeSize - 1);
		while (!codeQueue.empty())
		{
			tmp = codeQueue.front();
			codeQueue.pop();
			if (Tree[tmp].lchild ==-1 && Tree[tmp].rchild == -1) {  
				//叶子节点直接输出
				cout << setw(5) << tmp << setw(6) << Tree[tmp].weight << setw(10) << Tree[tmp].code << endl;	
			}
			else {//因为哈夫曼树中只有N0和N2
				codeQueue.push(Tree[tmp].lchild);
				Tree[Tree[tmp].lchild].code = Tree[tmp].code + "1";  //对左孩子编码

				codeQueue.push(Tree[tmp].rchild);
				Tree[Tree[tmp].rchild].code = Tree[tmp].code + "0"; //对右孩子编码
			}
		}
	}
};

2.2.4 输出整个哈夫曼树所有的结点的全部信息（除编码）；

	//输出构建完成的哈夫曼树
	void PrintTree() {
		cout << "index weight parent lchild rchild" << endl;
		for (int i = 0; i < TreeSize; i++) {
			cout << setw(5) << i;
			cout << setw(6) << Tree[i].weight;
			cout << setw(6) << Tree[i].parent;
			cout << setw(6) << Tree[i].lchild;
			cout << setw(6) << Tree[i].rchild;
			cout << endl;
		}
	}

2.2 完整代码

#pragma once
#include <iostream>
#include <iomanip>
#include <Queue>
#include <string>
using namespace std;
//用来获取数组长度
template <class T>
int getArrayLen(T& array)
{
	return (sizeof(array) / sizeof(array[0]));
}

//结点结构
struct HNode{
	float weight;  //权值
	int parent;  //父节点，父节点主要判定一个结点是否已经加入哈夫曼树
	int lchild, rchild;  //左孩子，右孩子
	string code;  //记录结点编码
	HNode() {
		weight = 0;
		parent = lchild = rchild = -1;
		code = "";
	}
	HNode(float w) {
		weight = w;
		parent = lchild = rchild = -1;
		code = "";
	}
};

class HuffmanTree {
	HNode* Tree;  //哈夫曼树结点数组头部
	int TreeSize; //树中结点树总数，TreeSize=叶子结点n(要编码的字符个数) * 2 - 1
public:
	HuffmanTree() {
		Tree = NULL;
		TreeSize = 0;
	}
	~HuffmanTree() {
		delete[] Tree;
	}

	//构造哈夫曼树，输入权值数组 和 数组长度n
	void Create(float* a, int n) {
		TreeSize = 2 * n - 1;  //确定哈夫曼树的结点个数
		Tree = new HNode[TreeSize];
		//权值数组保存在哈夫曼树数组前n个数值
		for (int i = 0; i < n; i++)
		{
			Tree[i].weight = a[i];
		}

		//开始进行n-1次合并操作，形成一颗哈夫曼树
		int s1, s2;
		int nextPos = (TreeSize + 1) / 2; //记录下一个插入位置,起始为n
		for (int i =0; i < (TreeSize-1)/2; i++) {
			SelectTwoMin(nextPos, s1, s2); //找到数组中权值最小的两个点
			//对Tree中新节点的孩子结点及权值赋值
			Tree[nextPos].lchild = s1;
			Tree[nextPos].rchild = s2;
			Tree[nextPos].weight = Tree[s1].weight + Tree[s2].weight;
			//给这两个结点分配父节点(意味着两个结点已加入哈夫曼树)
			Tree[s1].parent = Tree[s2].parent = nextPos;
			nextPos++;  //插入位置后移一位
		}
	}

	//寻找数组中权值最小的两个点
	void SelectTwoMin(int nextPos,int &s1, int &s2) 
	{
		//找到第一个未加入哈夫曼树的结点,标记为s1
		int i=0;
		while (Tree[i].parent != -1) {
			i++;
		}
		//从s2后一位开始找到第二个未加入哈夫曼树的结点,标记为s2
		s1 = i;
		int j = i + 1;
		while (Tree[j].parent != -1) {
			j++;
		}
		s2 = j;
		//调整s1和s2对应权值大小，确保s1对应点的权值更小，从而寻找更小的点时只需和s2比较
		KeepOrder(s1, s2);

		//从s2后一位开始，和s1,s2比较，确定数组中权值最小的两个点
		for (int k = j + 1; k <nextPos; k++) 
		{
			if (Tree[k].parent == -1) {
				if (Tree[k].weight < Tree[s2].weight) {
					s2 = k;
					//找到小于s2的点后，需和s1比较确定大小顺序
					KeepOrder(s1, s2);
				}
			}
		}
	}

	//确保n1对应结点的权值小于n2
	void KeepOrder(int& n1,int& n2) {
		if (Tree[n1].weight > Tree[n2].weight)
		{
			float tmp = n1;
			n1 = n2;
			n2 = tmp;
		}
	}

	//输出构建完成的哈夫曼树
	void PrintTree() {
		cout << "index weight parent lchild rchild" << endl;
		for (int i = 0; i < TreeSize; i++) {
			cout << setw(5) << i;
			cout << setw(6) << Tree[i].weight;
			cout << setw(6) << Tree[i].parent;
			cout << setw(6) << Tree[i].lchild;
			cout << setw(6) << Tree[i].rchild;
			cout << endl;
		}
	}

	//对树中结点编码并输出
	void PrintCoder() 
	{
		cout << "index weight     code" << endl;
		queue<int> codeQueue;  //只保存编号
		int tmp;
		codeQueue.push(TreeSize - 1);
		while (!codeQueue.empty())
		{
			tmp = codeQueue.front();
			codeQueue.pop();
			if (Tree[tmp].lchild ==-1 && Tree[tmp].rchild == -1) {  
				//叶子节点直接输出
				cout << setw(5) << tmp << setw(6) << Tree[tmp].weight << setw(10) << Tree[tmp].code << endl;	
			}
			else {//因为哈夫曼树中只有N0和N2
				codeQueue.push(Tree[tmp].lchild);
				Tree[Tree[tmp].lchild].code = Tree[tmp].code + "1";  //对左孩子编码

				codeQueue.push(Tree[tmp].rchild);
				Tree[Tree[tmp].rchild].code = Tree[tmp].code + "0"; //对右孩子编码
			}
		}
	}
};

3 测试代码及输出

    ///哈夫曼树
    HuffmanTree hTree;
	float x[] = { 5,29,7,8,14,23,3,11 };
	hTree.Create(x, getArrayLen(x));//避免输入错误的数组长度导致错误
	hTree.PrintTree();
	hTree.PrintCoder();

正确输出：

4 参考资料

1.哈夫曼树算法及C++实现:www.cnblogs.com/smile233/p/…
2.百度百科·哈夫曼树：baike.baidu.com/item/哈夫曼树/2…
3.数据结构：Huffman树(哈夫曼树)原理及C++实现：blog.csdn.net/weixin_4142…

哈夫曼树(Huffman树)原理分析及实现（C++）