#include "stdafx.h"
#include <iostream>
#include <map>
#include <vector>
#include <list>
#include <fstream>
#include <string>
using namespace std;

//узел значений

class Node
{
public:
 int a;
 char c;
 Node *left, *right;

 Node(){left=right=NULL;}

 Node(Node *L, Node *R)
 {
  left = L;
  right = R;
  a = L->a + R->a;
 }
};

//сортировка узлов

struct MyCompare
{
 bool operator()(Node* l, Node* r) const
 {
  return l->a < r->a;
 }
};

//сжатие

vector<bool>code;
map<char,vector<bool> > table;
void BuildTable(Node *root)
{
  if (root->left!=NULL)
  {
   code.push_back(0);
   BuildTable(root->left);
  }

if (root->right!=NULL)
 {
  code.push_back(1);
  BuildTable(root->right);
 }
if (root->c)
table[root->c]=code;

code.pop_back();
}

int main()
{
 string s;
 getline (cin, s);

//символ и кол-во его вхождений
 map <char,int> m;

 for (int i=0; i<s.length(); i++)
 {
  char c = s[i];
  m[c]++;
 }

//слепить из символов узлы и сунуть их в list

 list<Node*> t;

 map <char,int>::iterator i;
 for(i = m.begin(); i != m.end(); ++i)
 {
  Node *p = new Node;
  p->c = i->first;
  p->a = i->second;
  t.push_back(p);
 }

//отсортировать узлы по кол-ву вхождений от наим.

 while (t.size()!=1)
 {
  t.sort(MyCompare());

  Node *SonL = t.front();
  t.pop_front();
  Node *SonR = t.front();
  t.pop_front();

  Node *parent = new Node(SonL, SonR);
  t.push_back(parent);
 }

 Node *root = t.front();

//сжатие

 BuildTable (root);

//вывод сжатой строки
 for (int i=0; i<s.length(); i++)
 {
  char c=s[i];
  vector<bool> x = table[c];
  for (int n=0; n<x.size(); n++)
  cout<<x[n];
 }


 cout<<endl;
 system("pause");
 return 0;
}

...

//сжатие

BuildTable (root);

map<char,vector<bool> >::iterator ii;

for (ii=table.begin(); ii!=table.end(); ii++)

cout << ii-> first << ":" << ii->second << endl;

cout<<endl;
system("pause");
return 0;
}