[期末课设#2][PTA]哈夫曼编码译码

题目要求为确保构建的哈夫曼树唯一，做了如下限定：

（1）选择根结点权值最小的两棵二叉树时，选取权值较小者作为左子树。

（2）若多棵二叉树根结点权值相等，按先后次序分左右，先出现的作为左子树，后出现的作为右子树。

另外需要注意的是输出编码的时候要按树的先序顺序，我一开始写的bfs

建树很简单，不断将两个权值最小的节点合并为一个逻辑节点直到只剩最后一个逻辑节点(根节点)为止即可

解码的部分有点像字典树，遇到叶节点输出当前节点的值并回溯到根节点即可

对于编码存储的部分可以用一个整形存，需要注意的是哈夫曼编码会产生形如0..的编码，需要将编码存为10..B

// PTA 7-2 哈夫曼编码译码
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

#define FREQ first
#define CHAR second

constexpr char EMPTY = -1;

using namespace std;

struct trieNode
{
    trieNode* leftSon = nullptr;
    trieNode* rightSon = nullptr;
    char payload = EMPTY;
    double weight;

    trieNode(double wt)
    {
        weight = wt;
    }
};

bool cmpWeight(const trieNode* a, const trieNode* b)
{
    return a->weight < b->weight;
}

bool cmpFirstElem(const pair<double, char>& a, const pair<double, char>& b)
{
    return a.FREQ > b.FREQ;
}

void merge(trieNode* leafLeft, trieNode* leafRight, trieNode* root)
{
    root->leftSon = leafLeft;
    root->rightSon = leafRight;
}

template <class elemType>
string showBin(elemType n)
{
    string dic = "01";
    string ans = "";
    while (n > 1)
    {
        ans = dic[n & 1] + ans;
        n >>= 1;
    }
    return ans;
}

template <class elemType>
void outputCode(trieNode* root, elemType prefix)
{
    if (root == nullptr)
    {
        return;
    }
    if (root->payload != EMPTY)
    {
        cout << root->payload << ":" << showBin(prefix) << "\n";
    }
    outputCode(root->leftSon, prefix << 1);
    outputCode(root->rightSon, prefix << 1 | 1);
    return;
}

string decode(trieNode* root, string encoded)
{
    trieNode* tmp = root;
    string ans = "";
    for (auto& iter : encoded)
    {
        if (iter == '1')
        {
            tmp = tmp->rightSon;
        }
        else
        {
            tmp = tmp->leftSon;
        }
        if (tmp->payload != EMPTY)
        {
            ans = ans + tmp->payload;
            tmp = root;
        }
    }
    return ans;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin >> n;
    vector<pair<double, char>> frequency(n);
    for (int i = 0; i < n; i++)
    {
        cin >> frequency[i].CHAR >> frequency[i].FREQ;
    }
    sort(frequency.begin(), frequency.end(), cmpFirstElem);
    vector<trieNode*> nodes;
    for (int i = 0; i < n; i++)
    {
        nodes.push_back(new trieNode(frequency[i].FREQ));
        nodes.back()->payload = frequency[i].CHAR;
    }
    while (nodes.size() > 1)
    {
        sort(nodes.begin(), nodes.end(), cmpWeight);
        trieNode* left = nodes.front();
        nodes.erase(nodes.begin());
        trieNode* right = nodes.front();
        nodes.erase(nodes.begin());
        trieNode* newNode = new trieNode(left->weight + right->weight);
        merge(left, right, newNode);
        nodes.push_back(newNode);
    }
    outputCode(nodes.front(), 1);
    string encoded;
    cin >> encoded;
    cout << "original:" << decode(nodes.front(), encoded);
    return 0;
}