哈夫曼树的建立、编码及译码的详解和实现 |
您所在的位置：网站首页 › 三菱系统的m代码如何译码出来 › 哈夫曼树的建立、编码及译码的详解和实现 |
哈夫曼树的建立、编码及译码的详解和实现
|
简单哈夫曼树的建立，及其编码、译码的详解和实现
基本术语
二叉树的带权路径长度
二叉树中所有叶子结点的带权路径长度之和 根到结点的路径长度从根到结点的路径上的分支数 哈夫曼树二叉树又称最优二叉树，是一带权路径长度最短的二叉树。 例：设结点a、b、c、d的权值分别为1、3、5、7， 二叉树（1）的带权路径长度=31+33+25+17=29 二叉树（2）的带权路径长度=21+23+25+27=32 二叉树（3）的带权路径长度=21+33+35+17=33
所以，那么问题来了。 怎么构建哈夫曼树呢？ 构建哈夫曼树 算法根据给定的n个权值{w1,w2,…,wn}构成n棵二叉树的集合F={T1,T2,…,Tn}，其中每棵二叉树只含一个带权的根结点，其左右子树均空； 在F中选两棵根结点的权值最小的二叉树作为左右子树，构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和； 在F中删除这两棵二叉树，同时将新得到的二叉树加入F ； 重复2和3，直到F只含一棵二叉树，此即最优二叉树。 输入一串哈夫曼码，将其解码变成一串字符。 string estring;//创建一个字符串类型的数据，用于存储解码得出的字符 int pos = 0, first = 0; for(int x = 0; x if(hft[i].num == s.substr(first, pos))//first为从第几个字符开始截取，pos为截取几个字符。 //哈夫曼树中的哈夫曼码与选中的哈夫曼码进行对比 { cout int s1; int s2; } MIN; //选择结点权值最小的两个结点 MIN Select(HuffmanTree HT, int n) { int min, secmin,s1,s2; min = 10000; secmin = 10000; MIN code; s1 = 1; s2 = 1; for (int i = 1; i min = HT[i].weight; s1 = i; } } for (int i = 1; i secmin = HT[i].weight; s2 = i; } } code.s1 = s1; code.s2 = s2; return code; } //将哈夫曼码存储在结构体num中 void putlorinnum(HuffmanTree &hft, int num) { for(int i = num; i >= 1; i--) { if(hft[hft[i].parent].parent) { hft[i].num = hft[hft[i].parent].num + hft[i].num; } } } //创造哈夫曼树 void CreateHuffmanTree(HuffmanTree &HT, int num) { int m; m = 2 * num - 1; HT = new HTNode[m + 1]; //分配空间 for (int i = 1; i cin >> HT[i].weight; cin>>HT[i].data; } for (int i = num + 1; i if(HT[i].data != -1) { cout for(int x = 1; x estring = estring + hft[x].num;//哈夫曼码连接起来 x = m; } } } cout pos++; for(int i = 1; i cout int q; cout cout |
在所有可以构建的二叉树中，（1）的带权路径长度是最短，所以（1）是最优二叉树。
代码如下：【本文地址】