给定的数组用C++编程哈夫曼树编码和权值

以下是一个简单的C++实现，用于构建哈夫曼树并进行编码：

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

struct Node {
  char data;
  int freq;
  Node* left;
  Node* right;

  Node() {}
  Node(char c, int f) : data(c), freq(f), left(nullptr), right(nullptr) {}

  bool operator>(const Node& other) const { return freq > other.freq; }
};

class HuffmanCoding {
 public:
  HuffmanCoding(const string& s) : s_(s) {}

  void buildTree() {
    unordered_map<char, int> freq;
    for (char c : s_) freq[c]++;

    priority_queue<Node, vector<Node>, greater<Node>> pq;
    for (auto it : freq) pq.push(Node(it.first, it.second));

    while (pq.size() > 1) {
      Node* left = new Node(pq.top().data, pq.top().freq);
      pq.pop();
      Node* right = new Node(pq.top().data, pq.top().freq);
      pq.pop();
      Node* parent = new Node('$', left->freq + right->freq);
      parent->left = left;
      parent->right = right;
      pq.push(*parent);
    }

    root_ = new Node(pq.top().data, pq.top().freq);
  }

  void encode() {
    unordered_map<char, string> codes;
    encodeHelper(root_, "", codes);

    cout << "Character\tFrequency\tCode" << endl;
    for (auto it : codes) {
      cout << it.first << "\t\t" << freq_[it.first] << "\t\t" << it.second
           << endl;
    }
  }

 private:
  string s_;
  Node* root_;
  unordered_map<char, int> freq_;

  void encodeHelper(Node* curr, string code,
                    unordered_map<char, string>& codes) {
    if (curr == nullptr) return;
    if (curr->data != '$') {
      codes[curr->data] = code;
      freq_[curr->data] = curr->freq;
    }
    encodeHelper(curr->left, code + "0", codes);
    encodeHelper(curr->right, code + "1", codes);
  }
};

int main() {
  string s = "hello world";
  HuffmanCoding hc(s);
  hc.buildTree();
  hc.encode();
  return 0;
}

这个实现使用一个`Node`结构来表示哈夫曼树的节点。在构建哈夫曼树时，使用一个最小堆（`priority_queue`）来维护权值最小的节点。

在构建哈夫曼树时，首先统计字符频率，然后将每个字符和它的频率放入最小堆中。每次从最小堆中取出两个节点，将它们合并为一个新的父节点，然后将父节点插入最小堆中。重复此过程，直到只剩下一个节点，即根节点。

在编码阶段，使用递归来遍历哈夫曼树，并构建每个字符对应的编码。在每个叶节点处，将字符和编码保存在`codes`哈希表中，并将字符的频率保存在`freq_`哈希表中。

最后，输出每个字符的频率和编码。这里使用`$`作为内部节点的占位符，以便在输出时将其过滤掉。