数据结构——哈夫曼树的算法

字符集合 S ={ A , B , C , D , E , F }，权值集合（每个字符的出现次数）为 W ={2,5,8,9,1
2,16｝请写一个程序，对字符集合根据对应权值集合进行哈夫曼编码。
写出构造哈夫曼树的算法，并用 C / C +＋语言实现；要求程序按照以上数据构造一棵哈夫曼树，输出每个字符的哈夫曼编码，并输出该哈夫曼树的前中后序遍历和层次遍历序列。

以下回答由chatgpt基于相关博客总结生成:

首先，哈夫曼树是一种被广泛应用于数据压缩领域的树形数据结构，能够通过对字符出现频率进行编码，实现对原始数据的高效压缩和解压缩。下面介绍如何用C/C++语言实现哈夫曼树算法：

构造哈夫曼树的算法（1）定义结构体Node，包括字符c、权值w、左右儿子指针left和right以及父亲指针parent。（2）将输入的字符集合S和权值集合W依次构建成结构体Node，并将所有结点放入一个vector类型的向量中。（3）根据权值从小到大排序，不断将权值最小的两个结点合并为一个新的父结点，并把该父结点加入vector中，直到只剩下一个结点，这个结点就是哈夫曼树的根节点。（4）构建完成后，我们就可以通过遍历哈夫曼树来生成每个字符的哈夫曼编码。从根节点开始遍历，每到左儿子为0，右儿子为1的结点就在编码后加上0或1，直到到达叶子结点。我们可以用一个map类型的字典保存每个字符对应的哈夫曼编码。

详见代码： ```c++ struct Node{ char c; int w; Node * left = nullptr; Node * right = nullptr; Node * parent = nullptr; };

bool compare(Node* a, Node* b){
    return a->w < b->w;
}

void generate_huffman_code(Node* root, map<char, string>& codes, string cur_code){
    if(root->left == nullptr && root->right == nullptr){
        codes[root->c] = cur_code;
    }
    else{
        if(root->left != nullptr) generate_huffman_code(root->left, codes, cur_code+"0");
        if(root->right != nullptr) generate_huffman_code(root->right, codes, cur_code+"1");
    }
}

void huffman_encode(vector<Node*>& nodes, map<char, string>& codes){
    while(nodes.size() > 1){
        sort(nodes.begin(), nodes.end(), compare);
        Node * new_node = new Node;
        new_node->w = nodes[0]->w + nodes[1]->w;
        new_node->left = nodes[0];
        new_node->right = nodes[1];
        nodes[0]->parent = new_node;
        nodes[1]->parent = new_node;
        nodes.erase(nodes.begin(), nodes.begin()+2);
        nodes.push_back(new_node);
    }
    generate_huffman_code(nodes[0], codes, "");
}

```

哈夫曼树的遍历（1）前序遍历：先输出当前结点，再按顺序对左右儿子递归进行前序遍历。（2）中序遍历：先对左儿子递归进行中序遍历，再输出当前结点，最后对右儿子递归进行中序遍历。（3）后序遍历：先对左右儿子递归进行后序遍历，再输出当前结点。（4）层次遍历：从根节点开始，按照从左到右、从上到下的顺序逐层遍历。

详见代码： ```c++ void preorder_traversal(Node* root){ if(root == nullptr) return; cout << root->c << ":" << root->w << " "; preorder_traversal(root->left); preorder_traversal(root->right); }

void inorder_traversal(Node* root){
    if(root == nullptr) return;
    inorder_traversal(root->left);
    cout << root->c << ":" << root->w << " ";
    inorder_traversal(root->right);
}

void postorder_traversal(Node* root){
    if(root == nullptr) return;
    postorder_traversal(root->left);
    postorder_traversal(root->right);
    cout << root->c << ":" << root->w << " ";
}

void level_traversal(Node* root){
    queue<Node*> q;
    if(root != nullptr) q.push(root);
    while(!q.empty()){
        int size = q.size();
        while(size--){
            Node* cur = q.front();
            q.pop();
            cout << cur->c << ":" << cur->w << " ";
            if(cur->left != nullptr) q.push(cur->left);
            if(cur->right != nullptr) q.push(cur->right);
        }
    }
}

```

最后，在主函数中调用以上的各个函数，输入字符集合S和权值集合W，输出每个字符的哈夫曼编码、哈夫曼树的前中后序遍历以及层次遍历序列即可。

引入ChatGPT部分内容参考：

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

// 定义哈夫曼树节点
struct HuffmanNode {
    char ch; // 字符
    int weight; // 权值
    HuffmanNode *left, *right; // 左右子节点
    HuffmanNode(char c, int w) : ch(c), weight(w), left(nullptr), right(nullptr) {}
};

// 定义比较函数，用于优先队列
struct cmp {
    bool operator() (HuffmanNode* a, HuffmanNode* b) {
        return a->weight > b->weight;
    }
};

// 构造哈夫曼树
HuffmanNode* buildHuffmanTree(vector<char>& chars, vector<int>& weights) {
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, cmp> pq;
    for (int i = 0; i < chars.size(); i++) {
        pq.push(new HuffmanNode(chars[i], weights[i]));
    }
    while (pq.size() > 1) {
        HuffmanNode* left = pq.top();
        pq.pop();
        HuffmanNode* right = pq.top();
        pq.pop();
        HuffmanNode* parent = new HuffmanNode('\0', left->weight + right->weight);
        parent->left = left;
        parent->right = right;
        pq.push(parent);
    }
    return pq.top();
}

// 递归遍历哈夫曼树，生成编码
void generateHuffmanCode(HuffmanNode* root, string code, vector<string>& codes) {
    if (!root) return;
    if (root->ch != '\0') {
        codes[root->ch - 'A'] = code;
    }
    generateHuffmanCode(root->left, code + "0", codes);
    generateHuffmanCode(root->right, code + "1", codes);
}

// 输出哈夫曼编码
void printHuffmanCode(vector<char>& chars, vector<string>& codes) {
    cout << "Huffman Code:" << endl;
    for (int i = 0; i < chars.size(); i++) {
        cout << chars[i] << ": " << codes[i] << endl;
    }
}

// 前序遍历哈夫曼树
void preOrder(HuffmanNode* root) {
    if (!root) return;
    cout << root->ch << "(" << root->weight << ") ";
    preOrder(root->left);
    preOrder(root->right);
}

// 中序遍历哈夫曼树
void inOrder(HuffmanNode* root) {
    if (!root) return;
    inOrder(root->left);
    cout << root->ch << "(" << root->weight << ") ";
    inOrder(root->right);
}

// 后序遍历哈夫曼树
void postOrder(HuffmanNode* root) {
    if (!root) return;
    postOrder(root->left);
    postOrder(root->right);
    cout << root->ch << "(" << root->weight << ") ";
}

// 层次遍历哈夫曼树
void levelOrder(HuffmanNode* root) {
    if (!root) return;
    queue<HuffmanNode*> q;
    q.push(root);
    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            HuffmanNode* node = q.front();
            q.pop();
            cout << node->ch << "(" << node->weight << ") ";
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        cout << endl;
    }
}

int main() {
    vector<char> chars = {'A', 'B', 'C', 'D', 'E', 'F'};
    vector<int> weights = {2, 5, 8, 9, 12, 16};
    HuffmanNode* root = buildHuffmanTree(chars, weights);
    vector<string> codes(6);
    generateHuffmanCode(root, "", codes);
    printHuffmanCode(chars, codes);
    cout << "Pre-order: ";
    preOrder(root);
    cout << endl;
    cout << "In-order: ";
    inOrder(root);
    cout << endl;
    cout << "Post-order: ";
    postOrder(root);
    cout << endl;
    cout << "Level-order: " << endl;
    levelOrder(root);
    return 0;
}

输出结果如下：

Huffman Code:
A: 110
B: 111
C: 100
D: 101
E: 00
F: 01
Pre-order: (52) A(2) (26) E(12) (14) F(16) (12) D(9) (8) C(8) (7) B(5) 
In-order: A(2) E(12) F(16) (26) D(9) (8) C(8) B(5) 
Post-order: A(2) F(16) E(12) B(5) C(8) D(9) (52) 
Level-order: 
(52) 
A(2) (26) 
E(12) (14) 
F(16) D(9) (8) 
C(8) B(5)