数据结构-哈夫曼树（最优二叉树）

港控/mmm° 2024-03-22 15:14 54阅读 0赞

**目录**

一、引言

二、哈夫曼树的概念

三、哈夫曼树的构建

1. 构建步骤

2. 构建示例

四、哈夫曼编码

1. 编码规则

2. 编码示例

五、哈夫曼树的应用

1. 数据压缩

2. 文件加密

六、总结

--------------------

## 一、引言 ##

在计算机科学中，数据结构是指计算机中数据组织、管理和存储的方式。数据结构是计算机科学的重要基础，它对于计算机程序的设计和实现具有重要的影响。哈夫曼树是一种重要的数据结构，它被广泛应用于数据压缩、文件加密等领域。本文将介绍哈夫曼树的概念、构建方法、编码规则以及应用。

## 二、哈夫曼树的概念 ##

哈夫曼树是一种二叉树，它的叶子节点代表着一组数据，而非叶子节点代表着数据的组合。哈夫曼树的构建是基于数据的出现频率来进行的，出现频率高的数据在哈夫曼树中的深度较浅，而出现频率低的数据在哈夫曼树中的深度较深。因此，哈夫曼树可以用来实现数据的压缩和加密。

## 三、哈夫曼树的构建 ##

### 1. 构建步骤 ###

哈夫曼树的构建步骤如下：

1. 将数据按照出现频率从小到大排序。  
2. 取出出现频率最小的两个数据，将它们合并成一个节点，该节点的权值为两个数据的权值之和。  
3. 将新节点插入到已排序的数据中，保持数据的有序性。  
4. 重复步骤2和3，直到只剩下一个节点，该节点即为哈夫曼树的根节点。

### 2. 构建示例 ###

假设有以下数据：

A: 5次  
B: 2次  
C: 4次  
D: 3次

按照出现频率从小到大排序后，得到以下序列：

B: 2次  
D: 3次  
C: 4次  
A: 5次

取出出现频率最小的两个数据B和D，将它们合并成一个节点，该节点的权值为两个数据的权值之和，即5。得到以下序列：

C: 4次  
A: 5次  
BD: 5次

将新节点BD插入到已排序的数据中，保持数据的有序性，得到以下序列：

C: 4次  
BD: 5次  
A: 5次

重复步骤2和3，取出出现频率最小的两个数据C和BD，将它们合并成一个节点，该节点的权值为两个数据的权值之和，即9。得到以下序列：

A: 5次  
CBD: 9次

将新节点CDB插入到已排序的数据中，保持数据的有序性，得到以下序列：

A: 5次  
CDB: 9次

重复步骤2和3，取出出现频率最小的两个数据A和CDB，将它们合并成一个节点，该节点的权值为两个数据的权值之和，即14。得到以下哈夫曼树：

14  
/ \\  
A 9  
/ \\  
4 CBD  
/ \\  
C BD

以下是C++实现哈夫曼树的示例代码：

include <iostream>
    #include <queue>
    #include <vector>
    using namespace std;
    
    // 哈夫曼树节点
    struct HuffmanNode {
        int weight; // 权重
        char ch; // 字符
        HuffmanNode *left, *right; // 左右子节点
    
        HuffmanNode(int w, char c = '\0', HuffmanNode *l = nullptr, HuffmanNode *r = nullptr)
            : weight(w), ch(c), left(l), right(r) {}
    };
    
    // 哈夫曼编码表
    struct HuffmanCode {
        char ch; // 字符
        string code; // 编码
        HuffmanCode(char c = '\0', string s = "") : ch(c), code(s) {}
    };
    
    // 比较函数，用于优先队列
    struct cmp {
        bool operator()(HuffmanNode *a, HuffmanNode *b) { return a->weight > b->weight; }
    };
    
    // 构建哈夫曼树
    HuffmanNode *buildHuffmanTree(vector<int> &weights, vector<char> &chars) {
        priority_queue<HuffmanNode *, vector<HuffmanNode *>, cmp> pq;
        for (int i = 0; i < weights.size(); i++) {
            pq.push(new HuffmanNode(weights[i], chars[i]));
        }
        while (pq.size() > 1) {
            HuffmanNode *left = pq.top();
            pq.pop();
            HuffmanNode *right = pq.top();
            pq.pop();
            HuffmanNode *parent = new HuffmanNode(left->weight + right->weight, '\0', left, right);
            pq.push(parent);
        }
        return pq.top();
    }
    
    // 生成哈夫曼编码表
    void generateHuffmanCode(HuffmanNode *root, string code, vector<HuffmanCode> &huffmanCodes) {
        if (!root) return;
        if (root->ch != '\0') {
            huffmanCodes.push_back(HuffmanCode(root->ch, code));
        }
        generateHuffmanCode(root->left, code + "0", huffmanCodes);
        generateHuffmanCode(root->right, code + "1", huffmanCodes);
    }
    
    int main() {
        vector<int> weights = {5, 2, 7, 4, 9};
        vector<char> chars = {'A', 'B', 'C', 'D', 'E'};
    
        HuffmanNode *root = buildHuffmanTree(weights, chars);
    
        vector<HuffmanCode> huffmanCodes;
        generateHuffmanCode(root, "", huffmanCodes);
    
        for (auto hc : huffmanCodes) {
            cout << hc.ch << ": " << hc.code << endl;
        }
    
        return 0;
    }

上述代码中，\`HuffmanNode\`表示哈夫曼树节点，\`HuffmanCode\`表示哈夫曼编码表中的一项。\`buildHuffmanTree\`函数用于构建哈夫曼树，\`generateHuffmanCode\`函数用于生成哈夫曼编码表。最后，输出哈夫曼编码表中每个字符的编码。

## 四、哈夫曼编码 ##

### 1. 编码规则 ###

哈夫曼编码是一种前缀编码，即任何一个字符的编码都不是另一个字符编码的前缀。哈夫曼编码的规则如下：

1. 对于哈夫曼树中的每个叶子节点，将它的编码设置为从根节点到该叶子节点的路径上经过的边的方向，0表示向左，1表示向右。  
2. 对于哈夫曼树中的每个非叶子节点，将它的编码设置为它的左子树的编码加上0，右子树的编码加上1。

### 2. 编码示例 ###

以前面构建的哈夫曼树为例，对于数据A、B、C、D的编码如下：

A: 0  
B: 110  
C: 10  
D: 111

## 五、哈夫曼树的应用 ##

### 1. 数据压缩 ###

哈夫曼树可以用来实现数据的压缩，即将数据用哈夫曼编码进行编码，然后将编码后的数据进行传输或存储。由于哈夫曼编码是一种前缀编码，因此可以保证编码后的数据不会出现歧义，从而实现数据的高效压缩。

### 2. 文件加密 ###