数据结构哈夫曼树课设附上代码

哈夫曼树是一种常用的数据压缩算法，它通过构建二叉树来实现对数据的压缩。具体来说，哈夫曼树的构建过程是：首先将每个字符出现的频率作为权值，构建出一棵森林；然后从森林中选择两个权值最小的节点作为左右子节点，构建一棵新的二叉树，并将新的二叉树的根节点的权值设为左右子节点权值之和；不断重复这个过程，直到最后只剩下一棵二叉树，即为哈夫曼树。在对数据进行压缩时，对于每个字符，使用哈夫曼树中该字符对应的路径编码来进行压缩，即可实现高效的数据压缩。

以下是一个简单的哈夫曼树构建的代码实现（C++）：

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

struct Node {
    char ch; // 字符
    int freq; // 频率
    Node* left; // 左子节点
    Node* right; // 右子节点
    Node(char c, int f): ch(c), freq(f), left(nullptr), right(nullptr) {}
};

struct cmp {
    bool operator()(Node* a, Node* b) {
        return a->freq > b->freq;
    }
};

Node* buildHuffmanTree(vector<int>& freq, vector<char>& ch) {
    priority_queue<Node*, vector<Node*>, cmp> pq;
    for (int i = 0; i < freq.size(); i++) {
        pq.push(new Node(ch[i], freq[i]));
    }
    while (pq.size() > 1) {
        Node* left = pq.top(); pq.pop();
        Node* right = pq.top(); pq.pop();
        Node* parent = new Node('\0', left->freq + right->freq);
        parent->left = left;
        parent->right = right;
        pq.push(parent);
    }
    return pq.top();
}

void printHuffmanCode(Node* root, string code) {
    if (root == nullptr) return;
    if (root->ch != '\0') {
        cout << root->ch << ": " << code << endl;
    }
    printHuffmanCode(root->left, code + "0");
    printHuffmanCode(root->right, code + "1");
}

int main() {
    vector<char> ch = {'a', 'b', 'c', 'd', 'e', 'f'};
    vector<int> freq = {5, 9, 12, 13, 16, 45};
    Node* root = buildHuffmanTree(freq, ch);
    printHuffmanCode(root, "");
    return 0;
}

以上代码实现了对字符集 {a,b,c,d,e,f} 中各个字符出现频率的统计，并通过优先队列实现了对节点按照权值（即频率）进行排序。最后调用 `buildHuffmanTree` 函数构建哈夫曼树，并通过 `printHuffmanCode` 函数输出每个字符对应的编码。