哈夫曼树编码与查找算法（C语言实现）

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编码（有时也称为霍夫曼编码）。

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

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

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