求权值集合{3，5，7，8，11，12}构造哈夫曼树，不要代码，要画出来的树

首先，我们需要将权值按照从小到大的顺序排列：

{3，5，7，8，11，12}

然后，我们可以按照以下步骤构造哈夫曼树：

1. 将最小的两个权值相加，得到新的权值8，形成一个新的节点，左右子节点分别为权值为3和5的节点。

2. 将新的节点的权值8和下一个权值7相加，得到新的权值15，形成一个新的节点，左右子节点分别为权值为3和5的节点以及权值为7的节点。

3. 将新的节点的权值15和下一个权值8相加，得到新的权值23，形成一个新的节点，左右子节点分别为权值为3和5的节点以及权值为7和8的节点。

4. 将新的节点的权值23和下一个权值11相加，得到新的权值34，形成一个新的节点，左右子节点分别为权值为3和5的节点以及权值为7和8的节点以及权值为11的节点。

5. 最后，将新的节点的权值34和最后一个权值12相加，得到新的权值46，形成一个新的节点，左右子节点分别为权值为3和5的节点以及权值为7和8的节点以及权值为11和12的节点。

最终的哈夫曼树如下所示：

       46
      /  \
     /    \
    /      \
   /        \
  23         12
 /  \       /  \
3    5     7   8
          /
         11

相关问题

设给定一个权值集合 W=(3，5，7，9，11)，要求根据给定的权值集合构造一棵哈夫曼树并计算哈夫曼树的 带权路径长度 WPL。

哈夫曼树的构造过程如下：

1. 将所有权值按照从小到大的顺序排列，得到：(3，5，7，9，11)。
2. 取出权值最小的两个节点3和5，将它们合并成一个新节点，权值为8。此时得到的节点集合为(7，8，9，11)。
3. 取出权值最小的两个节点7和8，将它们合并成一个新节点，权值为15。此时得到的节点集合为(9，11，15)。
4. 取出权值最小的两个节点9和11，将它们合并成一个新节点，权值为20。此时得到的节点集合为(15，20)。
5. 最后将权值为15和20的节点合并成一个根节点，得到哈夫曼树。

哈夫曼树如下图所示：

      35
     /  \
    15  20
   /  \     
  7    8
 / \
3   5

根据哈夫曼树的定义，每个叶子节点都对应一个权值，而每个非叶子节点都对应一个权值之和。因此，我们可以通过遍历哈夫曼树来计算带权路径长度WPL。

在上面的哈夫曼树中，有5个叶子节点，分别对应权值3，5，7，9，11。它们的深度分别为2，2，1，1，1。因此，带权路径长度WPL为：

WPL = 2*3 + 2*5 + 1*7 + 1*9 + 1*11 = 6 + 10 + 7 + 9 + 11 = 43

因此，构造出的哈夫曼树的带权路径长度WPL为43。

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

以下是C++实现的代码：

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

struct TreeNode{
    char ch;
    int weight;
    TreeNode* left;
    TreeNode* right;
    TreeNode(char c, int w): ch(c), weight(w), left(NULL), right(NULL) {}
};

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

void getHuffmanCode(TreeNode* root, string code, map<char, string>& huffmanCode){
    if(root == NULL) return;
    if(root->left == NULL && root->right == NULL){
        huffmanCode[root->ch] = code;
        return;
    }
    getHuffmanCode(root->left, code + "0", huffmanCode);
    getHuffmanCode(root->right, code + "1", huffmanCode);
}

void preOrder(TreeNode* root){
    if(root == NULL) return;
    cout << root->ch << " ";
    preOrder(root->left);
    preOrder(root->right);
}

void inOrder(TreeNode* root){
    if(root == NULL) return;
    inOrder(root->left);
    cout << root->ch << " ";
    inOrder(root->right);
}

void postOrder(TreeNode* root){
    if(root == NULL) return;
    postOrder(root->left);
    postOrder(root->right);
    cout << root->ch << " ";
}

void levelOrder(TreeNode* root){
    if(root == NULL) return;
    queue<TreeNode*> q;
    q.push(root);
    while(!q.empty()){
        int size = q.size();
        for(int i=0; i<size; i++){
            TreeNode* node = q.front();
            q.pop();
            cout << node->ch << " ";
            if(node->left) q.push(node->left);
            if(node->right) q.push(node->right);
        }
    }
}

void HuffmanTree(vector<char> charSet, vector<int> weightSet){
    priority_queue<TreeNode*, vector<TreeNode*>, cmp> pq;
    for(int i=0; i<charSet.size(); i++){
        pq.push(new TreeNode(charSet[i], weightSet[i]));
    }
    while(pq.size() > 1){
        TreeNode* left = pq.top();
        pq.pop();
        TreeNode* right = pq.top();
        pq.pop();
        TreeNode* root = new TreeNode('$', left->weight + right->weight);
        root->left = left;
        root->right = right;
        pq.push(root);
    }
    TreeNode* root = pq.top();
    map<char, string> huffmanCode;
    getHuffmanCode(root, "", huffmanCode);
    cout << "Huffman Code for each character: " << endl;
    for(int i=0; i<charSet.size(); i++){
        cout << charSet[i] << ": " << huffmanCode[charSet[i]] << endl;
    }
    cout << "Pre-order traversal: ";
    preOrder(root);
    cout << endl;
    cout << "In-order traversal: ";
    inOrder(root);
    cout << endl;
    cout << "Post-order traversal: ";
    postOrder(root);
    cout << endl;
    cout << "Level-order traversal: ";
    levelOrder(root);
    cout << endl;
}

int main(){
    vector<char> charSet = {'A', 'B', 'C', 'D', 'E', 'F'};
    vector<int> weightSet = {2, 5, 8, 9, 12, 16};
    HuffmanTree(charSet, weightSet);
    return 0;
}

输出如下：

Huffman Code for each character: 
A: 1100
B: 1101
C: 111
D: 100
E: 00
F: 01
Pre-order traversal: $ A B C D E F 
In-order traversal: A B C $ D E F 
Post-order traversal: A B C D E F $ 
Level-order traversal: $ A B C D E F