一、哈夫曼树的定义
首先需要理解几个问题：
1、什么是路径
在一棵树中，从一个结点到另一个结点所经过的所有结点，被我们称为两个结点之间的路径
2、什么是路径长度
在一棵树中，从一个结点到另一个结点所经过的“边”的数量，被我们称为两个结点之间的路径长度。
3、什么是结点的带权路径长度
树的每一个结点，都可以拥有自己的“权重”（Weight），权重在不同的算法当中可以起到不同的作用。结点的带权路径长度，是指树的根结点到该结点的路径长度，和该结点权重的乘积。
4、什么是树的带权路径长度
在一棵树中，所有叶子结点的带权路径长度之和，被称为树的带权路径长度，也被简称为WPL。
比如以上 WPL=13+33+42+62+8*2=46
而哈夫曼树（Huffman Tree）是在叶子结点和权重确定的情况下，带权路径长度最小的二叉树，也被称为最优二叉树。文章来源：https://www.toymoban.com/news/detail-442996.html
二、构建思路
初始状态：有四棵只有根节点的树
合并权值为1和2的树，生成他们的父结点，父结点权值为3
合并权值为3和2的两颗树，生成父结点，父节点权值为5
最后合并剩下的两棵树，最后剩下的一棵就是哈夫曼树
基本思路就是先将每个给定权值的结点看成一棵只有根节点的树，然后不断合成权值最小的两个树，生成一个权值为他们之和的一棵新树，最终剩下的一棵树就是哈夫曼树文章来源地址https://www.toymoban.com/news/detail-442996.html
三、代码实现
定义树
typedef struct {
int weight; // 结点权值?
int parent, lc, rc; // 双亲结点和左 右子节点
} HTNode, *HuffmanTree;
查找最小的两个权值的结点
void Select(HuffmanTree &HT, int n, int &s1, int &s2)
{
int minum; // 定义一个临时变量保存最小值?
for(int i=1; i<=n; i++) // 以下是找到第一个最小值
{
if(HT[i].parent == 0)
{
minum = i;
break;
}
}
for(int i=1; i<=n; i++)
{
if(HT[i].parent == 0)
if(HT[i].weight < HT[minum].weight)
minum = i;
}
s1 = minum;
// 以下是找到第二个最小值，且与第一个不同
for(int i=1; i<=n; i++)
{
if(HT[i].parent == 0 && i != s1)
{
minum = i;
break;
}
}
for(int i=1; i<=n; i++)
{
if(HT[i].parent == 0 && i != s1)
if(HT[i].weight < HT[minum].weight)
minum = i;
}
s2 = minum;
}
建立哈夫曼树
void CreatHuff(HuffmanTree &HT, int *w, int n)
{
int m, s1, s2;
m = n * 2 - 1; // 总结点的个数
HT = new HTNode[m + 1]; // 分配空间
for(int i=1; i<=n; i++) // 1 - n 存放叶子结点，初始化
{
HT[i].weight = w[i];
HT[i].parent = 0;
HT[i].lc = 0;
HT[i].rc = 0;
}
for(int i=n+1; i<=m; i++) // 非叶子结点的初始化
{
HT[i].weight = 0;
HT[i].parent = 0;
HT[i].lc = 0;
HT[i].rc = 0;
}
printf("\nthe HuffmanTree is: \n");
for(int i = n+1; i<=m; i++) // 创建非叶子节点，建哈夫曼树
{ // 在HT[1]~HT[i-1]的范围内选择两个parent为0且weight最小的两个结点，其序号分别赋值给 s1 s2
Select(HT, i-1, s1, s2);
HT[s1].parent = i; // 删除这两个结点
HT[s2].parent = i;
HT[i].lc = s1; // 生成新的树，左右子节点是 s1和s2
HT[i].rc = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight; // 新树的权??
printf("%d (%d, %d)\n", HT[i].weight, HT[s1].weight, HT[s2].weight);
}
printf("\n");
}
总代码：
#include <stdio.h>
#include <string.h>
typedef struct {
int weight; // 结点权值?
int parent, lc, rc; // 双亲结点和左 右子节点
} HTNode, *HuffmanTree;
void Select(HuffmanTree &HT, int n, int &s1, int &s2)
{
int minum; // 定义一个临时变量保存最小值?
for(int i=1; i<=n; i++) // 以下是找到第一个最小值
{
if(HT[i].parent == 0)
{
minum = i;
break;
}
}
for(int i=1; i<=n; i++)
{
if(HT[i].parent == 0)
if(HT[i].weight < HT[minum].weight)
minum = i;
}
s1 = minum;
// 以下是找到第二个最小值，且与第一个不同
for(int i=1; i<=n; i++)
{
if(HT[i].parent == 0 && i != s1)
{
minum = i;
break;
}
}
for(int i=1; i<=n; i++)
{
if(HT[i].parent == 0 && i != s1)
if(HT[i].weight < HT[minum].weight)
minum = i;
}
s2 = minum;
}
void CreatHuff(HuffmanTree &HT, int *w, int n)
{
int m, s1, s2;
m = n * 2 - 1; // 总结点的个数
HT = new HTNode[m + 1]; // 分配空间
for(int i=1; i<=n; i++) // 1 - n 存放叶子结点，初始化
{
HT[i].weight = w[i];
HT[i].parent = 0;
HT[i].lc = 0;
HT[i].rc = 0;
}
for(int i=n+1; i<=m; i++) // 非叶子结点的初始化
{
HT[i].weight = 0;
HT[i].parent = 0;
HT[i].lc = 0;
HT[i].rc = 0;
}
printf("\nthe HuffmanTree is: \n");
for(int i = n+1; i<=m; i++) // 创建非叶子节点，建哈夫曼树
{ // 在HT[1]~HT[i-1]的范围内选择两个parent为0且weight最小的两个结点，其序号分别赋值给 s1 s2
Select(HT, i-1, s1, s2);
HT[s1].parent = i; // 删除这两个结点
HT[s2].parent = i;
HT[i].lc = s1; // 生成新的树，左右子节点是 s1和s2
HT[i].rc = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight; // 新树的权??
printf("%d (%d, %d)\n", HT[i].weight, HT[s1].weight, HT[s2].weight);
}
printf("\n");
}
int main()*
{
HuffmanTree HT;
int *w, n, wei;
printf("input the number of node\n");
scanf("%d", &n);
w = new int[n+1];
printf("\ninput the %dth node of value\n", n);
for(int i=1; i<=n; i++)
{
scanf("%d", &wei);
w[i] = wei;
}
CreatHuff(HT, w, n);
return 0;
}
到了这里，关于哈夫曼树的构建方法的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
