在哈夫曼树概念及构造和哈夫曼树存储类型及构造过程中构造出的哈夫曼树有什么用呢？

哈夫曼树的常见应用 – 哈夫曼编码

哈夫曼树是二叉树，自然想到 0-1 编码，那么规定左支为0，右支为1，那从根到叶子结点的路径即为 该结点的编码，如图：

哈夫曼编码有什么性质呢？

1、是前缀码。因为各叶子结点到根结点的路径不存在包含关系，因此不存在一个编码是另一个编码前缀的情况。

2、总长度最短的二进制前缀码。 因为哈夫曼树是带权路径长度最短的二叉树（可以这么理解：频度高的字符编码长度少）。

那么回到文章开头的提问：构造出的哈夫曼树有什么用呢？ – 从根走到叶结点的路径即为该结点的哈夫曼编码咯。

存储哈夫曼编码

哈夫曼编码在计算机中的存储通常涉及两个层面：程序内部的数据结构和持久化存储（如文件）的格式

程序内部的数据结构

在内存中，常用以下方式存储字符与哈夫曼编码的映射关系

哈希表（高效查找）

• 使用 std::unordered_map<char, std::string> 或 std::map<char, std::string>。
• 优点：快速查找字符对应的编码（时间复杂度 O(1) 或 O(log n)）。

std::unordered_map<char, std::string> huffmanCodes;
huffmanCodes['A'] = "010";
huffmanCodes['B'] = "10";

定长数组（针对ASCII字符集）

• 若字符范围有限（如ASCII），可用长度为256的数组，索引对应字符的ASCII值。
• 优点：访问速度极快（O(1)）。

std::string huffmanCodes[256];
huffmanCodes[65] = "010"; // 'A'的ASCII值为65

结构体数组

• 使用 std::vector<std::pair<char, std::string>> 存储字符与编码的对应关系。
• 适用场景：需要遍历所有字符时（如序列化到文件）。

std::vector<std::pair<char, std::string>> codes;
codes.push_back({'A', "010"});
codes.push_back({'B', "10"});

持久化存储（如文件）的格式

压缩后的文件需包含两部分：编码表（用于解码）和编码后的数据。

编码表的存储方式通常有两种：

存储哈夫曼树结构

• 方法：通过前序遍历序列化哈夫曼树。
  • 叶子节点：标记为特殊符号（如1），后跟字符值。
  • 内部节点：标记为0。
• 优点：空间紧凑，适合大规模字符集。
• 示例（假设字符为'A'和'B'）：

树结构序列化：0 1 A 1 B

直接存储字符与编码的映射

• 方法：将每个字符及其编码按特定格式写入文件头。
  • 格式：字符 + 编码长度 + 编码二进制位。
  • 示例（字符'A'编码为"010"，长度3）：

Header: A 3 010
Data: 010101... (编码后的二进制流)

注意：编码需转换为二进制位（而非ASCII的'0'/'1'），并按位紧凑存储。

小结

• 程序内部：优先选择哈希表或定长数组，以提高编码/解码速度。
• 文件存储：推荐序列化哈夫曼树或紧凑存储编码表，同时将编码后的数据转换为二进制位流。

编码后的数据存储

• 处理方式：将字符串形式的哈夫曼编码（如"010"）转换为真正的二进制位，按位写入文件。
  • 例如，"010"转换为二进制 0b010，填充到字节边界（如补零）。
• 优化：使用位操作库（如C++的 std::bitset）或手动位操作实现紧凑存储。

获取哈夫曼编码

哈夫曼树存储类型分顺序存储和链式存储，得到哈夫曼编码的操作也需要在相应的存储类型下进行。

此外阿Q下列代码均用std::map<char, std::string> 存储哈夫曼编码

链式存储

阿Q将链式存储放到前面，原因是其获得哈夫曼较为简单，从根走到叶子结点就获得了。

// 链式存储
// 哈夫曼编码
#include<map>
#include<string>
typedef std::map<char, std::string> HuffmanCode;

void GetHuffmanCode(Htree T, HuffmanCode &Hcode, std::string s=""){
    /*
        递归实现：
            1、若为叶子节点，直接 Hcode[T.c] = s
            2、递归左子树（s += '0'）
            3、递归右子树 (s += '1'） 
    */
    // 递归终止条件
    if(!T) return;

    // 若为叶子结点
    if(!T->lchild && !T->rchild) Hcode[T->c] = s;

    // 递归左子树
    GetHuffmanCode(T->lchild, Hcode, s+"0");

    // 递归右子树
    GetHuffmanCode(T->rchild, Hcode, s+"1");
}

#include<iostream>
#include"HuffmanTreelink.h"

#define n 4

int main(){
    int weight[n] = {7, 5, 2, 4};
    char c[n] = {'a', 'b', 'c', 'd'};
    Prior_Queue Q;

    InitHuffmanTree(Q, weight, c, n);
    Htree T = CreateHuffmanTree(Q);

    HuffmanCode code;

    GetHuffmanCode(T, code);
    
    for(auto iter = code.begin(); iter != code.end(); iter++)
        std::cout << "char = " << iter->first <<"\t" << "Huffmancode = " << iter->second << std::endl;

    return 0;
}
/*
输出结果：
char = a        Huffmancode = 0
char = b        Huffmancode = 10
char = c        Huffmancode = 110
char = d        Huffmancode = 111
*/

顺序存储

在王卓老师的课中利用一个数组（从尾到头逆着存）来获得哈夫曼编码震撼到阿Q，如图：

当然可以用字符串的逆转直接获得，但是阿Q接下来使用王卓老师的方案去解决字符串逆转问题

// 顺序存储
// 获取哈夫曼编码
#include<map>
#include<string>

typedef std::map<char, std::string> HuffmanCode;

void GetHuffmanCode(Htree T, HuffmanCode &Hcode){
    std::string s;

    // 辅助数组 （倒着存）
    char assist[T.n];
    assist[T.n - 1] = '\0';
    int k = T.n - 1;

    // 1 ~ T.n 均为叶子结点
    for(int i = 1; i <= T.n; i++){
        s = "";

        // 叶子结点走到根
        int j = i;
        while(T.Nodes[j].parent){
            if(T.Nodes[T.Nodes[j].parent].lchild == j)
                assist[--k] = '0';
            else assist[--k] = '1';
            j = T.Nodes[j].parent;
        }

        // 将 assist 数组下标 k ~ n-1合并即可
        for(; k <= T.n-1; k++)
            s += assist[k];
        
        Hcode[T.Nodes[i].c] = s;
    }
}

#include<iostream>
#include"HuffmanTree.h"

#define n 4

int main(){
    int weight[n] = {7, 5, 2, 4};
    char c[n] = {'a', 'b', 'c', 'd'};
    
    Htree T;

    InitHuffmanTree(T, weight, c, n);
    
    CreateHuffmanTree(T);

    HuffmanCode code;

    GetHuffmanCode(T, code);
    
    for(auto iter = code.begin(); iter != code.end(); iter++)
        std::cout << "char = " << iter->first <<"\t" << "Huffmancode = " << iter->second << std::endl;

    return 0;
}
/*
输出结果：
char = a        Huffmancode = 0
char = b        Huffmancode = 10
char = c        Huffmancode = 110
char = d        Huffmancode = 111
*/

其他应用

最优文件合并

设有6个有序表A，B，C，D，E，F，分别含有 10，35，40，50，60 和 200个数据元素，各表中的元素按升序排列。要求通过5次两两合并，将6个表最终合并为1个升序表，并使得最坏情况下比较的总次数达到最小；
1）给出完整的合并过程，并求出最坏情况下比较的总次数；

2）根据合并过程，描述n (n>=2)个不等长升序表的合并策略，说明理由。

任务调度优化

资源分配与负载均衡

网络数据传输优化

图像与信号处理

决策树优化

判断编码的前缀特性

现有某字符集（字符个数>=2）的不等长编码，每个字符的编码均为二进制的0、1序列，最长为L位，且具有前缀特性；

1）哪种数据结构适合保存上述具有前缀特性的不等长编码；

2）基于所设计的数据结构，简述从0/1串到字符串的译码过程；

3）简述判定某字符集的不等长编码是否具有前缀特性的过程。