哈夫曼树的定义和构造，哈夫曼编码

哈夫曼树（Huffman Tree）是一种用于数据压缩的树形结构，它通过将出现频率较高的字符赋予较短的编码，而将出现频率较低的字符赋予较长的编码，以达到有效压缩数据的目的。

以下是哈夫曼树的构造步骤：

1. 统计每个字符在给定文本中的出现频率。

2. 将每个字符作为树的叶子节点，节点的权重为字符的频率。

3. 将这些叶子节点按照权重从小到大排序，并构造一个优先队列（最小堆）。

4. 从优先队列中选取两个权重最小的节点，创建一个新的内部节点，该节点的权重为这两个节点的权重之和。将新节点插入优先队列。

5. 重复步骤 4，直到队列中只剩下一个节点，该节点即为哈夫曼树的根节点。

构造好的哈夫曼树具有以下特点：

• 树中的叶子节点对应于给定文本中的字符。

• 树中的内部节点没有对应的字符，它们的权重是其子节点权重之和。

• 从根节点到每个叶子节点的路径上的边上标记了字符的编码，通常使用 0 表示左子树路径，1 表示右子树路径。

通过哈夫曼树构造出来的编码称为哈夫曼编码。编码规则如下：

• 对于哈夫曼树的左子树路径，编码为路径上所有边的标记（0）的串。

• 对于哈夫曼树的右子树路径，编码为路径上所有边的标记（1）的串。

哈夫曼编码的特点是没有一个字符的编码是另一个字符编码的前缀，即它是一种前缀编码。这意味着在解码时，我们可以根据接收到的编码逐位向下遍历哈夫曼树，直到达到叶子节点，从而确定对应的字符。这样的编码方式可以确保在解码时不会出现二义性。

哈夫曼编码在数据压缩中被广泛应用，因为它能够根据字符的出现频率设计出最优的编码方案，从而实现较高的压缩比率。

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

// 哈夫曼树节点
struct Node {
    char data;           // 字符数据
    int frequency;       // 出现频率
    Node* leftChild;     // 左子节点指针
    Node* rightChild;    // 右子节点指针

    Node(char data, int frequency) {
        this->data = data;
        this->frequency = frequency;
        leftChild = NULL;
        rightChild = NULL;
    }
};

// 用于优先队列排序的比较函数
struct Compare {
    bool operator()(const Node* a, const Node* b) {
        return a->frequency > b->frequency;
    }
};

// 构造哈夫曼树
Node* constructHuffmanTree(vector<pair<char, int> >& frequencies) {
    priority_queue<Node*, vector<Node*>, Compare> pq;

    // 创建叶子节点并加入优先队列
    for (int i = 0; i < frequencies.size(); ++i) {
        Node* newNode = new Node(frequencies[i].first, frequencies[i].second);
        pq.push(newNode);
    }

    // 构造哈夫曼树
    while (pq.size() > 1) {
        Node* left = pq.top();
        pq.pop();
        Node* right = pq.top();
        pq.pop();

        Node* internalNode = new Node('$', left->frequency + right->frequency);
        internalNode->leftChild = left;
        internalNode->rightChild = right;

        pq.push(internalNode);
    }

    // 返回根节点
    return pq.top();
}

// 生成哈夫曼编码
void generateHuffmanCode(Node* root, string code, vector<pair<char, string> >& huffmanCodes) {
    if (root == NULL)
        return;

    // 叶子节点，将编码存入哈夫曼编码映射表
    if (root->leftChild == NULL && root->rightChild == NULL) {
        huffmanCodes.push_back(make_pair(root->data, code));
    }

    // 递归处理左子树和右子树
    generateHuffmanCode(root->leftChild, code + "0", huffmanCodes);
    generateHuffmanCode(root->rightChild, code + "1", huffmanCodes);
}

int main() {
    string text = "hello world";

    // 统计字符频率
    vector<pair<char, int> > frequencies;
    for (int i = 0; i < text.length(); i++) {
        bool found = false;
        for (int j = 0; j < frequencies.size(); ++j) {
            if (frequencies[j].first == text[i]) {
                frequencies[j].second++;
                found = true;
                break;
            }
        }
        if (!found) {
            frequencies.push_back(make_pair(text[i], 1));
        }
    }

    // 构造哈夫曼树
    Node* root = constructHuffmanTree(frequencies);

    // 生成哈夫曼编码
    vector<pair<char, string> > huffmanCodes;
    generateHuffmanCode(root, "", huffmanCodes);

    // 打印字符及其对应的哈夫曼编码
    cout << "Character\\tHuffman Code" << endl;
    for (int i = 0; i < huffmanCodes.size(); ++i) {
        cout << huffmanCodes[i].first << "\\t\\t" << huffmanCodes[i].second << endl;
    }

    return 0;
}

pair<char, int>是C++中的标准库模板类std::pair的一个实例化，表示包含两个不同类型的值的有序对。

在这个上下文中，pair<char, int>表示一个包含一个char类型的字符和一个int类型的频率值的有序对。这种表示方式常用于存储字符及其对应的频率，用于统计字符出现的次数或权重。

例如，可以使用pair<char, int>来表示字符 'a' 的频率为 5：pair<char, int> frequency('a', 5);

make_pair(text[i], 1) 是一个用于创建 pair 对象的函数模板。它将 text[i] 的值作为第一个元素，将整数值 1 作为第二个元素，然后返回一个包含这两个元素的 pair 对象。

在上述代码中，make_pair(text[i], 1) 用于创建一个表示字符 text[i] 和频率值为 1 的有序对。这样的有序对可以被添加到 frequencies 向量中，以便统计字符频率。

#include <iostream>
#include <cstdlib>
#include <cstring>

// 哈夫曼树节点
struct Node {
    char data;           // 字符数据
    int frequency;       // 出现频率
    Node* leftChild;     // 左子节点指针
    Node* rightChild;    // 右子节点指针

    Node(char data, int frequency) {
        this->data = data;
        this->frequency = frequency;
        leftChild = NULL;
        rightChild = NULL;
    }
};

// 构造哈夫曼树
Node* constructHuffmanTree(Node** nodes, int n) {
    while (n > 1) {
        int min1 = 0;
        int min2 = 1;

        if (nodes[min1]->frequency > nodes[min2]->frequency) {
            int temp = min1;
            min1 = min2;
            min2 = temp;
        }

        for (int i = 2; i < n; ++i) {
            if (nodes[i]->frequency < nodes[min1]->frequency) {
                min2 = min1;
                min1 = i;
            }
            else if (nodes[i]->frequency < nodes[min2]->frequency) {
                min2 = i;
            }
        }

        Node* internalNode = new Node('$', nodes[min1]->frequency + nodes[min2]->frequency);
        internalNode->leftChild = nodes[min1];
        internalNode->rightChild = nodes[min2];

        nodes[min1] = internalNode;
        nodes[min2] = nodes[n - 1];
        --n;
    }

    return nodes[0];
}

// 生成哈夫曼编码
void generateHuffmanCode(Node* root, std::string code, std::string* huffmanCodes, char* characters) {
    if (root->leftChild == NULL && root->rightChild == NULL) {
        int index = strchr(characters, root->data) - characters;
        huffmanCodes[index] = code;
    }

    if (root->leftChild)
        generateHuffmanCode(root->leftChild, code + "0", huffmanCodes, characters);
    if (root->rightChild)
        generateHuffmanCode(root->rightChild, code + "1", huffmanCodes, characters);
}

int main() {
    std::string text = "hello world";
    int n = text.length();

    char characters[n];
    int frequencies[n];
    int uniqueCharacters = 0;

    for (int i = 0; i < n; ++i) {
        bool found = false;
        for (int j = 0; j < uniqueCharacters; ++j) {
            if (characters[j] == text[i]) {
                frequencies[j]++;
                found = true;
                break;
            }
        }
        if (!found) {
            characters[uniqueCharacters] = text[i];
            frequencies[uniqueCharacters] = 1;
            ++uniqueCharacters;
        }
    }

    Node* nodes[uniqueCharacters];

    for (int i = 0; i < uniqueCharacters; ++i) {
        nodes[i] = new Node(characters[i], frequencies[i]);
    }

    Node* root = constructHuffmanTree(nodes, uniqueCharacters);

    std::string huffmanCodes[uniqueCharacters];
    generateHuffmanCode(root, "", huffmanCodes, characters);

    std::cout << "Character\\tHuffman Code" << std::endl;
    for (int i = 0; i < uniqueCharacters; ++i) {
        std::cout << characters[i] << "\\t\\t" << huffmanCodes[i] << std::endl;
    }

    return 0;
}

这个代码中，我们使用了字符数组 characters 和整数数组 frequencies 来代替 std::vector 来存储字符和频率。此外，我们使用了一个节点指针数组 nodes 来代替 std::queue，并手动实现了构造哈夫曼树和生成哈夫曼编码的函数。