fork 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. void inorder(HuffmanNode* root){
  76. 	//cout<<root->ch<<"_"<<root->freq<<endl;
  77. 	if (root->left!=nullptr){
  78. 		cout<<root->ch<<"_"<<root->freq<<"--"<<root->left->ch<<"_"<<root->left->freq<<endl;;
  79. 		inorder(root->left);
  80. 	}
  81. 	if (root->right!=nullptr){
  82. 		cout<<root->ch<<"_"<<root->freq<<"--"<<root->right->ch<<"_"<<root->right->freq<<endl;
  83. 		inorder(root->right);
  84.  
  85. 	}
  86. }
  87.  
  88. int main() {
  89.     string text = "BhatiaJaya";
  90.  
  91.     // Створення дерева частот символів
  92.     TreeNode* freqTree = nullptr;
  93.     for (char ch : text) {
  94.         TreeNode* node = find(freqTree, ch);
  95.         if (node)
  96.             node->freq++;
  97.         else
  98.             freqTree = insert(freqTree, ch, 1);
  99.     }
  100.  
  101.     // Створення черги для побудови дерева Хаффмана
  102.     priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> pq;
  103.     traverse(freqTree, pq);
  104.  
  105.     while (pq.size() > 1) {
  106.         HuffmanNode* left = pq.top(); pq.pop();
  107.         HuffmanNode* right = pq.top(); pq.pop();
  108.         HuffmanNode* parent = new HuffmanNode('\0', left->freq + right->freq, left, right);
  109.         pq.push(parent);
  110.     }
  111.  
  112.     HuffmanNode* root = pq.top();
  113.     vector<pair<char, string>> huffmanCodes;
  114.     generateCodes(root, "", huffmanCodes);
  115.  
  116.     // Вивід кодів
  117.     cout << "Коди Хаффмана:\n";
  118.     for (const auto& pair : huffmanCodes)
  119.         cout << pair.first << ": " << pair.second << '\n';
  120. inorder(root);
  121.     return 0;
  122. }
  123.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Коди Хаффмана:
B: 000
i: 001
y: 010
h: 011
t: 100
J: 101
a: 11
_10--_4
_4--_2
_2--B_1
_2--i_1
_4--_2
_2--y_1
_2--h_1
_10--_6
_6--_2
_2--t_1
_2--J_1
_6--a_4
https://ideone.com/9SFPCC
код Хаффмана
language:
C++14 (clang 8.0)
created:
13 days 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!