fork(1) download
copy 
  1. #include <iostream>
  2. #include <queue>
  3.  
  4. using namespace std;
  5.  
  6. // Вузол бінарного дерева для зберігання частот символів
  7. struct TreeNode {
  8.     char ch;
  9.     int freq;
  10.     TreeNode* left;
  11.     TreeNode* right;
  12.  
  13.     TreeNode(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
  14. };
  15.  
  16. // Додає вузли в бінарне дерево пошуку
  17. TreeNode* insert(TreeNode* root, char ch, int freq) {
  18.     if (!root) return new TreeNode(ch, freq);
  19.  
  20.     if (ch < root->ch)
  21.         root->left = insert(root->left, ch, freq);
  22.     else if (ch > root->ch)
  23.         root->right = insert(root->right, ch, freq);
  24.     else
  25.         root->freq++; // Якщо символ вже є, збільшити його частоту
  26.  
  27.     return root;
  28. }
  29.  
  30. // Пошук символу в дереві
  31. TreeNode* find(TreeNode* root, char ch) {
  32.     if (!root) return nullptr;
  33.     if (root->ch == ch) return root;
  34.  
  35.     if (ch < root->ch)
  36.         return find(root->left, ch);
  37.     return find(root->right,ch);
  38. }
  39.  
  40. // Побудова дерева Хаффмана
  41. struct HuffmanNode {
  42.     char ch;
  43.     int freq;
  44.     HuffmanNode* left;
  45.     HuffmanNode* right;
  46.  
  47.     HuffmanNode(char c, int f, HuffmanNode* l = nullptr, HuffmanNode* r = nullptr)
  48.         : ch(c), freq(f), left(l), right(r) {}
  49. };
  50.  
  51. struct Compare {
  52.     bool operator()(HuffmanNode* a, HuffmanNode* b) {
  53.         return a->freq > b->freq;
  54.     }
  55. };
  56.  
  57. // Функція обходу дерева частот та додавання вузлів у пріоритетну чергу
  58. void traverse(TreeNode* node, priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare>& pq) {
  59.     if (!node) return;
  60.  
  61.     pq.push(new HuffmanNode(node->ch, node->freq));
  62.     traverse(node->left, pq);
  63.     traverse(node->right, pq);
  64. }
  65.  
  66. // Генерація кодів Хаффмана
  67. void generateCodes(HuffmanNode* root, string code, vector<pair<char, string>>& codes) {
  68.     if (!root) return;
  69.     if (root->ch != '\0')
  70.         codes.emplace_back(root->ch, code);
  71.  
  72.     generateCodes(root->left, code + "0", codes);
  73.     generateCodes(root->right, code + "1", codes);
  74. }
  75.  
  76. int main() {
  77.     string text = "danylukoleksandra";
  78.  
  79.     // Створення дерева частот символів
  80.     TreeNode* freqTree = nullptr;
  81.     for (char ch : text) {
  82.         TreeNode* node = find(freqTree, ch);
  83.         if (node)
  84.             node->freq++;
  85.         else
  86.             freqTree = insert(freqTree, ch, 1);
  87.     }
  88.  
  89.     // Створення черги для побудови дерева Хаффмана
  90.     priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> pq;
  91.     traverse(freqTree, pq);
  92.  
  93.     while (pq.size() > 1) {
  94.         HuffmanNode* left = pq.top(); pq.pop();
  95.         HuffmanNode* right = pq.top(); pq.pop();
  96.         HuffmanNode* parent = new HuffmanNode('\0', left->freq + right->freq, left, right);
  97.         pq.push(parent);
  98.     }
  99.  
  100.     HuffmanNode* root = pq.top();
  101.     vector<pair<char, string>> huffmanCodes;
  102.     generateCodes(root, "", huffmanCodes);
  103.  
  104.     // Вивід кодів
  105.     cout << "Коди Хаффмана:\n";
  106.     for (const auto& pair : huffmanCodes)
  107.         cout << pair.first << ": " << pair.second << '\n';
  108.  
  109.     return 0;
  110. }
  111.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Коди Хаффмана:
e: 0000
y: 0001
r: 0010
u: 0011
d: 010
k: 011
n: 100
s: 1010
o: 1011
l: 110
a: 111
https://ideone.com/enswLP
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!