特殊的树:哈夫曼树2

点击打开在线编译器,边学边练

1.哈夫曼树的查找算法

查找算法根据构建哈夫曼树算法衍生而来,我们在构建二叉树时需要查找出哪些数据最小,以符合我们哈夫曼树的最优解情况。

查找权重值最小的两个结点的思想是:从待处理数据的头部位置开始,首先找到两个无父结点的结点(说明还未使用其构建成树),然后和后续无父结点的结点依次做比较,有两种情况需要考虑:

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;
        }
    }
}


2.哈夫曼编码

哈夫曼编码(Huffman Coding),又称霍夫曼编码,是一种编码方式,可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法,该方法完全依据字符出现概率来构造异字头的平均长度最短的码字,有时称之为最佳编码,一般就叫做Huffman编码(有时也称为霍夫曼编码)。

哈夫曼编码,主要目的是根据使用频率来最大化节省字符(编码)的存储空间。

35.png


        霍夫曼编码是一种无前缀编码。解码时不会混淆。其主要应用在数据压缩,加密解密等场合,也包括文件传输的场合。

        如果考虑到进一步节省存储空间,就应该将出现概率大(占比多)的字符用尽量少的0-1进行编码,也就是更靠近根(节点少),这也就是最优二叉树-哈夫曼树。


第一章 数据结构入门
第二章 链表
第三章 栈
第四章 队列
第五章 从C语言到C++
第六章 串,数组,矩阵,广义表
第七章 树
第八章 图
第九章 算法—查找
第十章 算法—排序
第十一章 算法&竞赛,思维培养
第十二章 后记