构造哈夫曼树的贪心策略

哈夫曼树的构造是通过贪心策略来实现的。贪心策略是指在每一步选择中都选择当前最优的解决方案，从而希望最终得到全局最优解。

构造哈夫曼树的贪心策略如下：
1. 首先，根据给定的n个权值{w(1),w(2),…,w(n)}构成n棵二叉树的森林F=(T1,…,Tn)。其中每棵二叉树中只有一个带权为w(k)的根结点，其余结点的权值均为0。
2. 从森林F中选择两棵根结点权值最小的树，将它们合并为一棵新的二叉树，且新的二叉树的根结点的权值为这两棵树的根结点权值之和。
3. 将新的二叉树加入到森林F中，并删除原来的两棵树。
4. 重复步骤2和步骤3，直到森林F中只剩下一棵树为止，这棵树就是构造出的哈夫曼树。

贪心策略的关键在于每一步都选择当前最优的解决方案，即选择权值最小的两棵树进行合并。这样可以保证最终构造出的哈夫曼树具有最小的带权路径长度，从而达到了全局最优解。

相关问题

给定权值构造哈夫曼树

哈夫曼树是一种带有权值的二叉树，它的构造方法是通过贪心策略，将权值最小的两个节点合并成一个新节点，直到最后只剩下一个节点为止。下面是给定权值构造哈夫曼树的详细步骤：

1. 将所有权值作为叶子节点，构造一个节点集合。

2. 从节点集合中选出两个权值最小的节点，合并成一个新节点，权值为两个节点的权值之和。

3. 将新节点加入节点集合中，并删除原来的两个节点。

4. 重复步骤2和3，直到节点集合中只剩下一个节点为止，这个节点就是哈夫曼树的根节点。

下面是一个示例，假设给定的权值为[5, 9, 12, 13, 16, 45]：

首先构造出6个叶子节点：

   5    9    12    13    16    45
  /    /    /     /     /     /
  A    B    C     D     E     F

然后按照上面的步骤，合并权值最小的两个节点：

   5    9    12    13    16    45
  /    /    /     /          /  
  A    B    C     D     ┌────F
                        │
                       61
                        │
                        └────E

继续合并权值最小的两个节点：

   5    9    12          13    16    45
  /    /    /           /     /     /
  A    B    C     ┌────D     E     F
               │
              25
               │
               └─────┐
                     │
                    36
                     │
                     └────C

继续合并权值最小的两个节点：

   5          9    12          13    16    45
  /           /    /           /     /     /
  A           B    ┌─────┐     D     E     F
                    │     │
                   25    36
                    │     │
                    └─────┘
                        │
                       61
                        │
                        └────C

最后只剩下一个节点，它就是哈夫曼树的根节点：

                             111
                            /   \
                           /     \
                          /       \
                         /         \
                        /           \
                       /             \
                      /               \
                     /                 \
                    /                   \
                   /                     \
                  /                       \
                 /                         \
                /                           \
               /                             \
              /                               \
             /                                 \
            /                                   \
           /                                     \
          /                                       \
         /                                         \
        5                                           106
       / \                                          /   \
      /   \                                        /     \
     /     \                                      /       \
    A       B                                    C         61
                                                 / \
                                                /   \
                                               D     E

因此，给定权值构造出的哈夫曼树就是上面的树形结构。

数据结构构造哈夫曼树c++

哈夫曼树是一种特殊的二叉树，它的叶子节点对应着要编码的字符，而非叶子节点则对应着编码。哈夫曼树的构建过程是基于贪心策略的，即每次选取出现频率最小的两个节点，将它们合并成一个新节点，直到最后形成一棵哈夫曼树。以下是一个 C++ 的实现：

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

// 定义哈夫曼树节点结构体
struct TreeNode {
    char data; // 节点存储的字符
    int freq; // 节点对应字符出现的频率
    TreeNode* left; // 左子节点
    TreeNode* right; // 右子节点
    TreeNode(char data, int freq) : data(data), freq(freq), left(nullptr), right(nullptr) {}
};

// 定义比较函数，用于优先队列的排序
struct cmp {
    bool operator()(TreeNode* a, TreeNode* b) {
        return a->freq > b->freq; // 频率小的节点优先级高
    }
};

// 构建哈夫曼树的函数
TreeNode* buildHuffmanTree(vector<char>& chars, vector<int>& freqs) {
    priority_queue<TreeNode*, vector<TreeNode*>, cmp> pq; // 定义优先队列
    for (int i = 0; i < chars.size(); i++) {
        TreeNode* node = new TreeNode(chars[i], freqs[i]); // 创建节点，存储字符和频率
        pq.push(node); // 将节点加入到优先队列中
    }
    while (pq.size() > 1) { // 只要队列中还有两个及以上的节点
        TreeNode* left = pq.top(); // 取出频率最小的节点
        pq.pop();
        TreeNode* right = pq.top(); // 取出频率次小的节点
        pq.pop();
        TreeNode* parent = new TreeNode('$', left->freq + right->freq); // 新建一个父节点
        parent->left = left; // 将左子节点挂到父节点下面
        parent->right = right; // 将右子节点挂到父节点下面
        pq.push(parent); // 将新建的父节点加入到队列中
    }
    return pq.top(); // 队列中最后剩下的节点即为根节点
}

// 递归打印哈夫曼树的编码
void printHuffmanCode(TreeNode* root, string code) {
    if (!root) return; // 递归结束条件
    if (root->data != '$') { // 如果是叶子节点，输出对应字符和编码
        cout << root->data << " " << code << endl;
    }
    printHuffmanCode(root->left, code + "0"); // 递归处理左子树
    printHuffmanCode(root->right, code + "1"); // 递归处理右子树
}

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

输出结果：

f 0
c 100
d 101
a 1100
b 1101
e 111

以上代码中，`buildHuffmanTree` 函数用于构建哈夫曼树，它使用了优先队列（堆）来维护频率最小的两个节点，不断合并成为新的节点，直到最后形成一棵哈夫曼树。`printHuffmanCode` 函数用于递归打印哈夫曼树的编码，其中传入的 `code` 参数表示当前节点的编码。