哈夫曼树编码的实现+图解（含全部代码）

03-15 1834阅读 0评论

$哈夫曼树编码的实现+图解（含全部代码）,哈夫曼树编码的实现+图解（含全部代码）,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,我们,方法,设置,第1张$

（图片来源网络，侵删）

哈夫曼树的基本概念

------------哈夫曼树的构造方法

------------------------哈夫曼编码

------------------------------------全部代码

哈夫曼树的基本概念

哈夫曼树通常以二叉树的形式出现，所以也称最优二叉树，是一类带权路径长度最短的树

首先得知道下以下几个术语：

$哈夫曼树编码的实现+图解（含全部代码）,哈夫曼树编码的实现+图解（含全部代码）,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,我们,方法,设置,第2张$

（图片来源网络，侵删）

路径：从树中的一个结点到另一个结点之间的分支构成这两点之间的路径

路径长度：路径上的分支数目称作路径长度

树的路径长度：从树根到每一个结点的路径长度之和

权：赋予某个实体的一个量

结点的带权路径长度：从该结点到树根之间的路径长度与结点上权的乘积

树的带权路径长度：树中所有叶子结点的带权路径长度之和

$哈夫曼树编码的实现+图解（含全部代码）,哈夫曼树编码的实现+图解（含全部代码）,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,我们,方法,设置,第3张$

（图片来源网络，侵删）

$哈夫曼树编码的实现+图解（含全部代码）,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,我们,方法,设置,第4张$

哈夫曼树的构造方法

哈夫曼树的实现利用了贪心算法的理念，就是先给定的若干结点的权进行分割，让它们变为单个的森林或者说是单个的树，因为树肯定是森林，而后在其中选择两个权值最小的结点生成新的结点，而后删除被选择的结点，让生成的结点参与森林中进行选拔，直至无结点进行选拔。

$哈夫曼树编码的实现+图解（含全部代码）,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,我们,方法,设置,第5张$

$哈夫曼树编码的实现+图解（含全部代码）,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,我们,方法,设置,第6张$ $哈夫曼树编码的实现+图解（含全部代码）,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,我们,方法,设置,第7张$

不好意思结点搞的太多了。。。每次生成都是到最后的原因是因为后面的代码，不然最后的结果不是一样的，当然哈夫曼树并不唯一，但是为了让最后答案一样，我选择这样画，这个过程也是后面构建哈夫曼树代码的过程，后面代码看不懂的可以结合这个图一起理解。

接下来就是哈夫曼树的存储结构了，因为每个结点需要权值，孩子结点与双亲结点的地址和结点的数据，所以我们需要用一个结构体来存储。而且这是二叉树的顺序存储。

typedef struct 
{
    char data;             //结点的数据
    int parent,lch,rch;    //双亲结点和孩子结点的下标
    int weight;            //结点的权值
}htNode,*HuffmanTree;

$哈夫曼树编码的实现+图解（含全部代码）,词库加载错误:未能找到文件“C:\Users\Administrator\Desktop\火车头9.8破解版\Configuration\Dict_Stopwords.txt”。,我们,方法,设置,第8张$

这个就是这个结构体的内部图，有了存储结构后，我们要做的就是初始化，因为是顺序存储，所以我们要知道给的这些结点构成哈夫曼树需要多少空间，因为我们要节省空间，所以需要用动态分配的方法来解决。

而我们知道，假设有n个结点构成哈夫曼树则会生成2n-1个结点，这是因为每个结点都会有个双亲，而根结点没有双亲，生成结点和边数相同为n-1，所以为2n-1，而我们在构成哈夫曼树时0下标是不用的，所以我们真正要申请的空间为2n个。

知道这些后我们就可以来初始化哈夫曼树了，我们在各自输入权值和结点数据后还需把各个结点的孩子与双亲的值置为-1（置为-1的好处就是能当个flag，也就是现在都没有双亲，都是森林，而且在生成的过程中不会出现和它相同的值）：以下是初始化的代码

int initHuffmanTree(huffmanTree& HT)
{
	HT = (htNode*)malloc(sizeof(htNode) * (2 * NODENUM));			//给HT分配2 * NODENUM个htNOde大小的htNode类型的数组
	for (int i = 1; i