DevJourney · code I wrote while learning

main.cpp

1.3 KB
#include <iostream>
#include <vector>
#include <string>
using namespace std;

struct Node
{
    string sym;
    int freq;
    Node *l, *r;

    Node(string s, int f)
    {
        sym = s;
        freq = f;
        l = nullptr;
        r = nullptr;
    }
};

void printCodes(Node *root, string code)
{
    if (!root)
        return;

    if (!root->l && !root->r)
    {
        cout << root->sym << ": " << code << "\n";
        return;
    }

    printCodes(root->l, code + "0");
    printCodes(root->r, code + "1");
}

int findMin(vector<Node *> &nodes)
{
    int idx = 0;
    for (int i = 1; i < nodes.size(); i++)
    {
        if (nodes[i]->freq < nodes[idx]->freq)
            idx = i;
    }
    return idx;
}

int main()
{
    int n;
    cin >> n;

    vector<Node *> nodes;

    for (int i = 0; i < n; i++)
    {
        string s;
        int f;
        cin >> s >> f;
        nodes.push_back(new Node(s, f));
    }

    while (nodes.size() > 1)
    {
        int i1 = findMin(nodes);
        Node *a = nodes[i1];
        nodes.erase(nodes.begin() + i1);

        int i2 = findMin(nodes);
        Node *b = nodes[i2];
        nodes.erase(nodes.begin() + i2);

        Node *p = new Node("", a->freq + b->freq);
        p->l = a;
        p->r = b;

        nodes.push_back(p);
    }

    if (!nodes.empty())
        printCodes(nodes[0], "");

    return 0;
}