关于树的一些基本知识这里就不再提了，如果不知道的小伙伴可以先去了解一下，我们直接进入正题。哈夫曼树是一种特殊的树。根据定义：哈夫曼树，又叫做最优树，是一种带权路径长度最小的树。哈夫曼树中没有度为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。其形成的哈夫曼树如下图所示：
程序构建的保存哈夫曼树的表如下图所示（这里我们规定，每次选取的两个最小值中，第一小的值放在左子树上，第二小的值放在右子树上）：
程序源代码：
运行结果：
2、链式结构
链式结构和顺序结构的实现思想是相同的。区别在于链式结构以邻接表为基本数据类型。就是创建一个指针类型的数组，每一个指针都指向一个结点，对于新生成的结点添加到数组末尾，到2*n-1个结点，也就是最后一个结点时，这个结点上的二叉树就是要构建的哈夫曼树。这里，我们通过先序（二叉树的一种遍历方法）打印哈夫曼树来得到输出结果。
程序源代码：
运行结果：
以上是我个人的学习成果，很高兴能与大家分享。
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.mushiming.com/mjsbk/6555.html