关于树的一些基本知识这里就不再提了，如果不知道的小伙伴可以先去了解一下，我们直接进入正题。哈夫曼树是一种特殊的树。根据定义：哈夫曼树，又叫做最优树，是一种带权路径长度最小的树。哈夫曼树中没有度为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。其形成的哈夫曼树如下图所示：
程序构建的保存哈夫曼树的表如下图所示（这里我们规定，每次选取的两个最小值中，第一小的值放在左子树上，第二小的值放在右子树上）：
| 编号 | 权重 | 双亲（编号） | 左子树（编号） | 右子树（编号） |
| 1 | 10 | 7 | 空 | 空 |
| 2 | 15 | 8 | 空 | 空 |
| 3 | 12 | 8 | 空 | 空 |
| 4 | 3 | 6 | 空 | 空 |
| 5 | 4 | 6 | 空 | 空 |
| 6 | 7 | 7 | 4 | 5 |
| 7 | 17 | 9 | 6 | 1 |
| 8 | 27 | 9 | 3 | 2 |
| 9 | 44 | 空 | 7 | 8 |
程序源代码：
# 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的结点的编码为0012、链式结构
链式结构和顺序结构的实现思想是相同的。区别在于链式结构以邻接表为基本数据类型。就是创建一个指针类型的数组，每一个指针都指向一个结点，对于新生成的结点添加到数组末尾，到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;
}运行结果：文章来源：https://www.toymoban.com/news/detail-742570.html
请输入元素个数:5
请输入各元素的权职:10 15 12 3 4
44 17 7 3 4 10 27 12 1以上是我个人的学习成果，很高兴能与大家分享。文章来源地址https://www.toymoban.com/news/detail-742570.html
到了这里，关于哈夫曼树的构建（详解顺序结构和链式结构）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
