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

class Node
{
public:
    int a;
    int c;

    Node(){}

    Node *left, *right;
    Node(Node *L, Node *R) // конструктор принимающий ссылки на левого и правого сына
    {
        left = L;
        right = R;
        a = L->a + R->a;
    }

};
void print(Node* root, unsigned k = 0) //функция вывода k отвечает за отступы чем дальше тем больше
{
if (root != NULL)
    {
    print(root->left, k + 3);
    for (unsigned i = 0; i < k; i++)
        {
        cout << " ";
        }
    if (root->c) cout << root->a << " (" << root->c << ")" << endl; // если есть буква выводить букву, если нет то число
    else cout << root->a << endl;
    print(root->right, k + 3);
    }
}

struct MyCompare
{
    bool operator()(Node* l, Node* r) const
    {
        return l->a < r->a;
    }
};
vector<bool> code; // глобальные переменные бульного типа томушо ток 0 и 1
map<char, vector<bool> > table; // собсна ассоциация символа с code
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 = "iiiiiasdsada dasda dadasd";
    map<char, int> m; //создаем ассоциативный массив чар и инт

    for (int i = 0; i < s.length();i++) //считаем кол-во вхождения каждого символа(в цикле проходимся от нуля до конца строки)
    {
        char c = s[i]; //в ц записываем символ и считаем
        m[c]++ ;
    }

    list<Node*> t;
    map<char, int>::iterator i;                 // с помощью интератора кладем массив в список
    for (i = m.begin(); i != m.end(); ++i)
    {
        Node *p = new Node; //создаем указатель на Node, тупо проходимся по map и загружаем Nodы
        p->c = i->first;
        p->a = i->second;
        t.push_back(p); //и указатель на это дело кидаем в list
    }
    while (t.size() != 1) // сортирую убираю 1 е два эл та и на его мето кладу созданый 3 на основе их
    {
        t.sort(MyCompare()); // cортирую
        Node *SonL = t.front(); // Беру 1 эл, присваиваю его 1 эл ту в списке
        t.pop_front(); // этот 1 эл удаляем, на его место становиться второй
        Node *SonR = t.front(); // теперь этот же который на 1м месте его тоже удаляем
        t.pop_front();
        Node *parent = new Node(SonL, SonR); // создаю батьку a = a + a2 его лефт будет указателем на первый а райт на второй
        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];
    }

    // print(root);
    system("pause");
    return 0;

}