Untitled

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <unordered_map>

using namespace std;

typedef struct Tree {
    int freq;  // 頻率
    char key;
    Tree *left;
    Tree *right;
    Tree(int fr = 0, char k = '\0', Tree *l = nullptr, Tree *r = nullptr):
        freq(fr), key(k), left(l), right(r) {};
} Tree, *pTree;

struct compare {
    bool operator() (Tree *a, Tree *b) {
        return a->freq > b->freq;  // 升冪
    }
};

priority_queue<pTree, vector<pTree>, compare> pque;  // Min-heap

// In-order traversal to print Huffman codes
void printCode(Tree *proot, string st) {
    if (proot == nullptr) {
        return;
    }

    if (proot->left) {
        st += '0';
    }
    printCode(proot->left, st);

    if (!proot->left && !proot->right) {  // Leaf node
        string paddedCode = st;
        while (paddedCode.size() < 12) {
            paddedCode = 'x' + paddedCode;
        }
        cout << proot->key << "'s code: " << paddedCode << endl;
    }
    st.pop_back();  // Backtrack one character

    if (proot->right) {
        st += '1';
    }
    printCode(proot->right, st);
}

// Free allocated memory on the heap
void del(Tree *proot) {
    if (proot == nullptr) {
        return;
    }
    del(proot->left);
    del(proot->right);

    delete proot;
}

// Huffman coding
void huffman(const unordered_map<char, int>& charFrequency) {
    for (const auto& entry : charFrequency) {
        Tree *pt = new Tree;
        pt->key = entry.first;
        pt->freq = entry.second;
        pque.push(pt);
    }

    // Combine the two smallest frequencies into a tree until only one tree remains
    while (pque.size() > 1) {
        Tree *proot = new Tree;
        pTree pl, pr;
        pl = pque.top(); pque.pop();
        pr = pque.top(); pque.pop();

        proot->freq = pl->freq + pr->freq;
        proot->left = pl;
        proot->right = pr;

        pque.push(proot);
    }

    string s = "";
    printCode(pque.top(), s);
    del(pque.top());
}

// Function to count character occurrences in a text
unordered_map<char, int> countCharacterfrequency(const string& text) {
    unordered_map<char, int> charCount;

    for (char c : text) {
        charCount[c]++;
    }

    return charCount;
}

int main() {
    // Read file
    ifstream inputFile("HUFFMANtree.txt");

    if (!inputFile.is_open()) {
        cerr << "Error opening the file 'HUFFMANtree.txt'" << endl;
        return 1;
    }

    // Read content from the file
    string fileContent;
    char ch;
    while (inputFile.get(ch)) {
        fileContent += ch;
    }

    //關檔
    inputFile.close();

    //出現頻率
    unordered_map<char, int> charOccurrences = countCharacterfrequency(fileContent);

    // Print character counts
    for (const auto& entry : charOccurrences) {
        if (entry.first == '\n') {
            cout << "Character '" << "\\n" << "' appears " << entry.second << " times." << endl;
        } else {
            cout << "Character '" << entry.first << "' appears " << entry.second << " times." << endl;
        }
    }

    //霍夫曼編碼
    huffman(charOccurrences);

    return 0;
}