查找算法根据构建哈夫曼树算法衍生而来,我们在构建二叉树时需要查找出哪些数据最小,以符合我们哈夫曼树的最优解情况。
查找权重值最小的两个结点的思想是:从待处理数据的头部位置开始,首先找到两个无父结点的结点(说明还未使用其构建成树),然后和后续无父结点的结点依次做比较,有两种情况需要考虑:
l 如果比两个结点中较小的那个还小,就保留这个结点,删除原来较大的结点;
l 如果介于两个结点权重值之间,替换原来较大的结点;
其代码可以表示为:
//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; } } }
哈夫曼编码(Huffman Coding),又称霍夫曼编码,是一种编码方式,可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法,该方法完全依据字符出现概率来构造异字头的平均长度最短的码字,有时称之为最佳编码,一般就叫做Huffman编码(有时也称为霍夫曼编码)。
哈夫曼编码,主要目的是根据使用频率来最大化节省字符(编码)的存储空间。
霍夫曼编码是一种无前缀编码。解码时不会混淆。其主要应用在数据压缩,加密解密等场合,也包括文件传输的场合。
如果考虑到进一步节省存储空间,就应该将出现概率大(占比多)的字符用尽量少的0-1进行编码,也就是更靠近根(节点少),这也就是最优二叉树-哈夫曼树。
本文固定URL:https://www.dotcpp.com/course/144
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:
一点编程也不会写的:零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码?手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程