1.哈夫曼树的查找算法文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25194.html
查找算法根据构建哈夫曼树算法衍生而来，我们在构建二叉树时需要查找出哪些数据最小，以符合我们哈夫曼树的最优解情况。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25194.html
查找权重值最小的两个结点的思想是：从待处理数据的头部位置开始，首先找到两个无父结点的结点（说明还未使用其构建成树），然后和后续无父结点的结点依次做比较，有两种情况需要考虑：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25194.html
l 如果比两个结点中较小的那个还小，就保留这个结点，删除原来较大的结点；文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25194.html
l 如果介于两个结点权重值之间，替换原来较大的结点；文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25194.html
其代码可以表示为：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25194.html
//HT数组中存放的哈夫曼树，end表示HT数组中存放结点的最终位置，s1和s2传递的是HT数组中权重值最小的两个结点在数组中的位置void Select(HuffmanTree HT, int end, int *s1, int *s2) { int min1, min2;//遍历数组初始下标为 1 int i = 1;//找到还没构建树的结点 while(HT[i].parent != 0 && i <= end) { i++; } min1 = HT[i].weight; *s1 = i; i++; while(HT[i].parent != 0 && i <= end) { i++; }//对找到的两个结点比较大小，min2为大的，min1为小的 if(HT[i].weight < min1) { min2 = min1; *s2 = *s1; min1 = HT[i].weight; *s1 = i; } else { min2 = HT[i].weight; *s2 = i; }//两个结点和后续的所有未构建成树的结点做比较 for(int j=i+1; j <= end; j++) {//如果有父结点，直接跳过，进行下一个 if(HT[j].parent != 0) { continue; }//如果比最小的还小，将min2=min1，min1赋值新的结点的下标 if(HT[j].weight < min1) { min2 = min1; min1 = HT[j].weight; *s2 = *s1; *s1 = j; }//如果介于两者之间，min2赋值为新的结点的位置下标 else if(HT[j].weight >= min1 && HT[j].weight < min2) { min2 = HT[j].weight; *s2 = j; } }} |
文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25194.html
2.哈夫曼编码文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25194.html
哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式，可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码（有时也称为霍夫曼编码）。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25194.html
哈夫曼编码，主要目的是根据使用频率来最大化节省字符（编码）的存储空间。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25194.html
文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25194.html
文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25194.html
霍夫曼编码是一种无前缀编码。解码时不会混淆。其主要应用在数据压缩，加密解密等场合，也包括文件传输的场合。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25194.html
如果考虑到进一步节省存储空间，就应该将出现概率大（占比多）的字符用尽量少的0-1进行编码，也就是更靠近根（节点少），这也就是最优二叉树-哈夫曼树。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25194.html