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

哈夫曼编码的构造过程：

1. 将权值集合按从小到大排序，并将每个字符看成一个独立的节点；
2. 取出权值最小的两个节点，合并成一个新节点，其权值为两个节点的权值之和，将这个新节点插入到节点集合中；
3. 重复步骤2，直到节点集合中只剩下一个节点，这个节点即为哈夫曼树的根节点。

C++代码实现：

#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;

// 定义哈夫曼树的节点结构体
struct Node {
    char ch;                // 节点对应的字符
    int weight;             // 节点对应的权值
    Node *left, *right;     // 左右子节点指针
    Node(char c, int w) : ch(c), weight(w), left(nullptr), right(nullptr) {}
};

// 定义比较器，用于优先队列的排序
struct cmp {
    bool operator()(const Node* a, const Node* b) {
        return a->weight > b->weight;
    }
};

// 构造哈夫曼树
Node* buildHuffmanTree(map<char, int>& mp) {
    priority_queue<Node*, vector<Node*>, cmp> pq;
    // 将字符集合中的每个字符看成一个独立的节点，加入到优先队列中
    for (auto iter = mp.begin(); iter != mp.end(); iter++) {
        pq.push(new Node(iter->first, iter->second));
    }
    // 不断取出权值最小的两个节点，合并成一个新节点，并将新节点加入到优先队列中
    while (pq.size() > 1) {
        Node *left = pq.top();
        pq.pop();
        Node *right = pq.top();
        pq.pop();
        Node *parent = new Node('\0', left->weight + right->weight);
        parent->left = left;
        parent->right = right;
        pq.push(parent);
    }
    // 返回根节点
    return pq.top();
}

// 递归遍历哈夫曼树，生成哈夫曼编码
void generateHuffmanCode(Node *root, string code, map<char, string>& mp) {
    if (!root->left && !root->right) {     // 叶子节点
        mp[root->ch] = code;
        return;
    }
    if (root->left) {
        generateHuffmanCode(root->left, code + "0", mp);
    }
    if (root->right) {
        generateHuffmanCode(root->right, code + "1", mp);
    }
}

int main() {
    map<char, int> mp = {{'A', 2}, {'B', 5}, {'C', 8}, {'D', 9}, {'E', 12}, {'F', 16}};
    Node* root = buildHuffmanTree(mp);      // 构造哈夫曼树
    map<char, string> huffmanCode;
    generateHuffmanCode(root, "", huffmanCode);      // 生成哈夫曼编码

    // 输出每个字符的哈夫曼编码
    for (auto iter = huffmanCode.begin(); iter != huffmanCode.end(); iter++) {
        cout << iter->first << " : " << iter->second << endl;
    }

    // 输出哈夫曼树的前中后序遍历和层次遍历序列
    cout << "前序遍历：";
    function<void(Node*)> preOrder = [&](Node* node) {
        if (!node) {
            return;
        }
        cout << node->ch << "(" << node->weight << ") ";
        preOrder(node->left);
        preOrder(node->right);
    };
    preOrder(root);
    cout << endl;

    cout << "中序遍历：";
    function<void(Node*)> inOrder = [&](Node* node) {
        if (!node) {
            return;
        }
        inOrder(node->left);
        cout << node->ch << "(" << node->weight << ") ";
        inOrder(node->right);
    };
    inOrder(root);
    cout << endl;

    cout << "后序遍历：";
    function<void(Node*)> postOrder = [&](Node* node) {
        if (!node) {
            return;
        }
        postOrder(node->left);
        postOrder(node->right);
        cout << node->ch << "(" << node->weight << ") ";
    };
    postOrder(root);
    cout << endl;

    cout << "层次遍历：";
    queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        Node* 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;

    return 0;
}

输出结果：

A : 11110
B : 1110
C : 110
D : 10
E : 0
F : 1111
前序遍历：
(52) A(2) (50) (23) D(9) (14) C(8) E(12) (28) F(16) B(5) 
中序遍历：D(9) A(2) C(8) E(12) (23) F(16) (14) B(5) (50) 
后序遍历：D(9) C(8) E(12) A(2) F(16) B(5) (50) 
(52) 
层次遍历：
(52) (50) A(2) (28) B(5) (14) (23) F(16) D(9) C(8) E(12)