0.32，0.25，0.179，0.14，0.07，0.03，哈夫曼树

这几个数字是哈夫曼树的构建过程中，每个节点的权重值。哈夫曼树是一种带权路径长度最短的树，它的构建过程就是通过贪心策略来实现的。具体来说，就是把每个节点的权重值看作一个叶子节点，并按照权重值从小到大排序。然后每次取出权重值最小的两个节点，将它们合并成一个新节点，新节点的权重值等于这两个节点的权重值之和。这个新节点再参与下一轮的合并，直到最后只剩下一个节点，就是哈夫曼树的根节点。

在这个例子中，我们按照权重值从小到大排序得到：0.03，0.07，0.14，0.179，0.25，0.32。然后依次取出0.03和0.07，合并成一个新节点，权重值为0.1；取出0.1和0.14，合并成一个新节点，权重值为0.24；取出0.179和0.24，合并成一个新节点，权重值为0.419；取出0.25和0.32，合并成一个新节点，权重值为0.57；最后将0.419和0.57合并成一个新节点，权重值为0.989。这就构建出了一棵带有权重的哈夫曼树。

相关问题

用 c++创建哈夫曼树，并实现对其编码，包括以下功能： 1.输入要创建的哈夫曼树的结点数和各结点的权权值。 2.建立哈夫曼树：根据输入的结点数和各结点的权值建哈夫曼树。 3.输出哈夫曼树。 4.对哈夫曼树进行编码，并输出其哈夫曼编码。

好的，我可以帮你解决这个问题。首先，哈夫曼树是一种带权路径长度最小的树，可以用于数据压缩等场景。下面我将介绍如何用 C++ 实现哈夫曼树的创建和编码。

1. 输入要创建的哈夫曼树的结点数和各结点的权权值。

我们可以定义一个结构体来表示每个结点，包含一个权值和指向左右子树的指针。

struct Node {
    int weight;
    Node* left;
    Node* right;
};

然后，我们可以使用一个数组来存储每个结点的权值，如下所示：

int weights[MAX_N]; // 存储每个结点的权值
int n; // 结点数

在实际使用中，可以通过输入或从文件中读取这些权值。

2. 建立哈夫曼树

建立哈夫曼树的过程可以使用贪心算法。算法的基本思路是：每次选择权值最小的两个结点，将它们合并成一个新的结点，并将新结点的权值设为这两个结点的权值之和。重复这个过程直到只剩下一个结点，这个结点就是哈夫曼树的根节点。

具体实现可以使用优先队列（堆）来实现。我们可以将每个结点看作一个单独的树，然后将它们插入到一个最小堆中。每次从最小堆中取出两个权值最小的结点，合并成一个新的结点，并将这个新的结点插入到最小堆中。重复这个过程直到堆中只剩下一个结点，这个结点就是哈夫曼树的根节点。

下面是代码实现：

Node* buildHuffmanTree(int weights[], int n) {
    // 优先队列中存储的是指向结点的指针，然后通过重载运算符实现结点比较的方法
    priority_queue<Node*, vector<Node*>, [](Node* a, Node* b) {
        return a->weight > b->weight;
    }> pq;
    for (int i = 0; i < n; i++) {
        Node* node = new Node();
        node->weight = weights[i];
        node->left = nullptr;
        node->right = nullptr;
        pq.push(node);
    }
    while (pq.size() > 1) {
        Node* left = pq.top();
        pq.pop();
        Node* right = pq.top();
        pq.pop();
        Node* parent = new Node();
        parent->weight = left->weight + right->weight;
        parent->left = left;
        parent->right = right;
        pq.push(parent);
    }
    return pq.top();
}

3. 输出哈夫曼树

输出哈夫曼树可以使用递归的方式进行遍历，并输出每个结点的权值和它的左右子树（如果有的话）。

void printHuffmanTree(Node* root) {
    if (root == nullptr) {
        return;
    }
    cout << root->weight << endl;
    if (root->left != nullptr) {
        cout << "Left: ";
        printHuffmanTree(root->left);
    }
    if (root->right != nullptr) {
        cout << "Right: ";
        printHuffmanTree(root->right);
    }
}

4. 对哈夫曼树进行编码，并输出其哈夫曼编码

对哈夫曼树进行编码需要用到递归。基本思路是：从根节点开始，如果往左走就在编码后的字符串中加入一个 0，如果往右走就在编码后的字符串中加入一个 1。当到达叶子结点时，就得到了这个结点的哈夫曼编码。重复这个过程直到遍历完整个哈夫曼树。

为了方便存储编码，我们可以使用一个数组来存储每个结点的编码。数组的下标表示结点的权值，数组的值表示该结点的编码。

下面是代码实现：

void encodeHuffmanTree(Node* root, string code, vector<string>& codes) {
    if (root == nullptr) {
        return;
    }
    if (root->left == nullptr && root->right == nullptr) {
        codes[root->weight] = code;
    }
    encodeHuffmanTree(root->left, code + "0", codes);
    encodeHuffmanTree(root->right, code + "1", codes);
}

完整代码如下：

1.输入要创建的哈夫曼树的结点数和各结点的权权值。 2.建立哈夫曼树：根据输入的结点数和各结点的权值建哈夫曼树。 3.输出哈夫曼树。 4.对哈夫曼树进行编码，并输出其哈夫曼编码。c++

以下是C++实现哈夫曼编码的代码：

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

//哈夫曼树结点定义
struct HuffmanNode {
    int weight; //结点权值
    HuffmanNode *left, *right; //左右子节点指针
    HuffmanNode(int w = 0, HuffmanNode *l = nullptr, HuffmanNode *r = nullptr) : weight(w), left(l), right(r){}
};

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

//构建哈夫曼树
HuffmanNode* buildHuffmanTree(int n, int* weight) {
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, CompareHuffmanNode> q;
    for (int i = 0; i < n; i++) {
        q.push(new HuffmanNode(weight[i]));
    }
    while (q.size() > 1) {
        HuffmanNode *left = q.top();
        q.pop();
        HuffmanNode *right = q.top();
        q.pop();
        HuffmanNode *parent = new HuffmanNode(left->weight + right->weight, left, right);
        q.push(parent);
    }
    return q.top();
}

//获取哈夫曼编码
void getHuffmanCode(HuffmanNode *node, string code, map<int, string> &table) {
    if (node->left == nullptr && node->right == nullptr) {
        table[node->weight] = code;
        return;
    }
    if (node->left != nullptr) {
        getHuffmanCode(node->left, code + "0", table);
    }
    if (node->right != nullptr) {
        getHuffmanCode(node->right, code + "1", table);
    }
}

int main() {
    int n;
    cout << "请输入结点数：";
    cin >> n;
    int *weight = new int[n];
    cout << "请输入各结点权值：";
    for (int i = 0; i < n; i++) {
        cin >> weight[i];
    }
    HuffmanNode *root = buildHuffmanTree(n, weight);
    cout << "哈夫曼树：" << endl;
    //层次遍历哈夫曼树
    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->weight << " ";
            if (node->left != nullptr) {
                q.push(node->left);
            }
            if (node->right != nullptr) {
                q.push(node->right);
            }
        }
        cout << endl;
    }
    map<int, string> table;
    getHuffmanCode(root, "", table);
    cout << "哈夫曼编码：" << endl;
    for (auto it : table) {
        cout << it.first << " " << it.second << endl;
    }
    return 0;
}

运行结果示例：

请输入结点数：5
请输入各结点权值：6 2 3 4 5
哈夫曼树：
2 3 4 5 6 
10 7 
17 
哈夫曼编码：
2 000
3 001
4 010
5 011
6 1