哈夫曼树的构建（详解顺序结构和链式结构）

关于树的一些基本知识这里就不再提了，如果不知道的小伙伴可以先去了解一下，我们直接进入正题。哈夫曼树是一种特殊的树。根据定义：哈夫曼树，又叫做最优树，是一种带权路径长度最小的树。哈夫曼树中没有度为1的节点（哈夫曼树也是二叉树），因此包含n个结点的哈夫曼树一共具有n个叶结点和n-1个度为2的中间结点（这里是根据二叉树的一些性质得出的），共计2*n-1个结点（这点很重要）。

接下来，我们来说一说哈夫曼树的构建思想：

1、现有n个权值，每个权值对应一个结点，这些结点构成了一个森林，森林中的每棵树Ti都是二叉树，且都仅包含一个具有权值的根节点，左右子树都为空，双亲也为空。

2、从森林中选取根节点权值最小的两棵树Ti和Tj（两棵树根节点双亲都为空）进行合并，创建出一棵新的二叉树。新的二叉树根节点的权值为Ti和Tj两棵树根节点权值之和。新的二叉树双亲为空，左右结点分别为Ti和Tj（Ti和Tj的双亲即为新的二叉树）。

3、重复上述过程直到森林中只剩下一棵二叉树为止（判断依据为只有一个根节点双亲为空或者已经有了2*n-1个结点），这棵树就是哈夫曼树。

具体实现上，我们先来看一看顺序结构：

1、顺序结构

顺序结构就是创建一个结构体数组保存各个结点，对于新生成的结点添加到数组末尾，当有2*n-1个结点时，哈夫曼树的构建就完成了。我们构建的是一张完整的保存哈夫曼树的表，我们用哈夫曼编码的方式来检验构建是否正确。哈夫曼编码：规定哈夫曼树中的左分支为0，右分支为1（反之也可以），则由根结点到某叶结点所经过的分支对应的0或1组成的序列就是该叶结点对应的哈夫曼编码。

我们采用的测试用例为 10  15  12  3  4。其形成的哈夫曼树如下图所示：

程序构建的保存哈夫曼树的表如下图所示（这里我们规定，每次选取的两个最小值中，第一小的值放在左子树上，第二小的值放在右子树上）：

程序源代码：

# include <iostream>
# include <string>
using namespace std;
typedef struct HTNode {
	int data;
	int parent, lchild, rchild;
}HTNode, * HufTree;
int main()
{
	int N;
	cout << "请输入元素个数:";
	cin >> N;
	cout << "请输入各元素的权职:";
	HufTree HT;
	HT = (HufTree)malloc(2 * N * sizeof(HTNode)); //哈夫曼树总结点有2*N-1个，动态分配2*N个空间
	for (int i = 1; i <= N; i++) {     //输入原始结点
		cin >> HT[i].data;
		HT[i].parent = -1;
		HT[i].lchild = -1;
		HT[i].rchild = -1;
	}
	//构建哈夫曼树
	for (int i = N + 1; i < 2 * N; i++) {  //哈夫曼树中共有2*N-1个结点，所以循环到2*N-1
		//寻找两个根节点权值最小的树
		int m1 = i - 1, m2 = i - 1;  //m1保存第一小的位置，m2保存第二小的位置
		int x1 = 1e9, x2 = 1e9;      //x1保存第一小的值，x2保存第二小的值
		for (int j = 1; j < i; j++) {      //从第一个结点到当前的最后一个结点，寻找两个权重最小的位置
			if (HT[j].parent == -1 && HT[j].data < x1) {  //符合条件的值，双亲必须为空
				x2 = x1;
				x1 = HT[j].data;
				m2 = m1;  //m2接替原m1，保存当前第二小的位置
				m1 = j;   //将当前最小值的位置赋给m1
			}
			else if (HT[j].parent == -1 && HT[j].data < x2) {
				x2 = HT[j].data;
				m2 = j;  
			}
		}
		//添加新树
		HT[m1].parent = i;  //添加双亲
		HT[m2].parent = i;  //添加双亲
		HT[i].data = HT[m1].data + HT[m2].data; //新加入的结点，权重为两个最小值的和
		HT[i].lchild = m1;  //将第一小的位置作为左子树
		HT[i].rchild = m2;  //将第二小的位置作为右子树
		HT[i].parent = -1;  //新结点的双亲为空
	}
	//依据哈夫曼树，打印输出各原始节点的编码
	string s;
	for (int i = 1; i <= N; i++) {
		int j = i;
		int p = HT[j].parent;
		while (p != -1) {
			if (j == HT[p].lchild) {
				s.append(1, '0');  //如果是双亲的左子树则编为0
			}
			else {
				s.append(1, '1');  //如果是双亲的右子树则编为1
			}
			j = p;
			p = HT[p].parent;
		}
		cout << "权重为" << HT[i].data << "的结点的编码为";
		for (int k = s.size() - 1; k >= 0; k--) { //倒序输出的才是正确的编码方式
			cout << s[k];
		}
		cout << endl;
		s.clear();
	}
	return 0;
}

运行结果：

请输入元素个数:5
请输入各元素的权职:10 15 12 3 4
权重为10的结点的编码为01
权重为15的结点的编码为11
权重为12的结点的编码为10
权重为3的结点的编码为000
权重为4的结点的编码为001

2、链式结构

链式结构和顺序结构的实现思想是相同的。区别在于链式结构以邻接表为基本数据类型。就是创建一个指针类型的数组，每一个指针都指向一个结点，对于新生成的结点添加到数组末尾，到2*n-1个结点，也就是最后一个结点时，这个结点上的二叉树就是要构建的哈夫曼树。这里，我们通过先序（二叉树的一种遍历方法）打印哈夫曼树来得到输出结果。

程序源代码：

# include <iostream>
# include <stdlib.h>
# define maxn 256
using namespace std;

typedef struct HTNode {
	int data;
	struct HTNode* lchild, * rchild, * parent;
}HTNode, * HufTree;

void PriPrint_Tree(HufTree T) //先序遍历
{
	if (T) {
		cout << T->data << " ";
		PriPrint_Tree(T->lchild);
		PriPrint_Tree(T->rchild);
	}
}

HufTree H[maxn]; //指针类型的数组
HufTree T;
int main()
{
	int N;
	cout << "请输入元素个数:";
	cin >> N;
	cout << "请输入各元素的权职:";
	for (int i = 1; i <= N; i++) {
		H[i] = (HufTree)malloc(sizeof(HTNode));
		cin >> H[i]->data;
		H[i]->lchild = NULL;
		H[i]->rchild = NULL;
		H[i]->parent = NULL;
	}
	for (int i = N + 1; i < 2 * N; i++) {  //哈夫曼树中共有2*N-1个结点，所以循环到2*N-1
		int m1 = i - 1, m2 = i - 1;  //m1保存第一小的位置，m2保存第二小的位置
		int x1 = 1e9, x2 = 1e9;      //x1保存第一小的值，x2保存第二小的值
		for (int j = 1; j < i; j++) {      //从第一个结点到当前的最后一个结点，寻找两个权重最小的位置
			if (H[j]->parent == NULL && H[j]->data < x1) {  //符合条件的值，双亲必须为空
				x2 = x1;
				x1 = H[j]->data;
				m2 = m1;  //m2接替原m1，保存当前第二小的位置
				m1 = j;   //将当前最小值的位置赋给m1
			}
			else if (H[j]->parent == NULL && H[j]->data < x2) { //大于等于第一小的值，小于第二小的值
				x2 = H[j]->data;
				m2 = j;
			}
		}
		H[i] = (HufTree)malloc(sizeof(HTNode)); //先给新结点开空间
		H[m1]->parent = H[i];  //添加双亲
		H[m2]->parent = H[i];  //添加双亲
		H[i]->data = H[m1]->data + H[m2]->data; //新加入的结点，权重为两个最小值的和
		H[i]->lchild = H[m1];  //将第一小的位置作为左子树
		H[i]->rchild = H[m2];  //将第二小的位置作为右子树
		H[i]->parent = NULL;  //新结点的双亲为空
	}
	T = H[2 * N - 1]; //最后一个结点上保存的即是完整的哈夫曼树
	PriPrint_Tree(T); //先序遍历打印哈夫曼树
	cout << endl;
	return 0;
}

运行结果：

请输入元素个数:5
请输入各元素的权职:10 15 12 3 4
44 17 7 3 4 10 27 12 1

以上是我个人的学习成果，很高兴能与大家分享。