哈夫曼編碼與解碼：從原理到 C++ 完整實現

哈夫曼樹核心原理

哈夫曼樹（最優二叉樹）是帶權路徑長度最小的二叉樹，廣泛應用於無損數據壓縮。核心思想：

1. 將所有字符按頻率構建葉子節點
2. 重複合併兩個最小頻率節點，新節點頻率為兩者之和
3. 直到只剩根節點，構建完成

高頻字符編碼短，低頻字符編碼長，實現平均編碼長度最小化。

關鍵數據結構

template
struct mydata {
    mydata() {}
    mydata(int i) : freq(i) {}
    string coded;   // 編碼結果
    int freq;       // 頻率
    T data;         // 字符數據
    bool operator<(const mydata& rhs) { return freq < rhs.freq; }
    mydata operator+(mydata& rhs) { return mydata(freq + rhs.freq); } // 僅頻率相加
};

template
class TreeNode {
public:
    TreeNode() : pfather(NULL), plchild(NULL), prchild(NULL) {}
    T data;
    TreeNode *pfather, *plchild, *prchild;
    bool operator<(const TreeNode& rhs) { return data < rhs.data; }
};

構建哈夫曼樹

使用最小優先隊列（STL priority_queue）：

template
TreeNode* MakeHuffmanTree(T* begin, T* end) {
    priority_queue*, vector*>, cmp> pri_que;
    TreeNode* pf = NULL;

    // 初始化葉子節點
    for (T* iter = begin; iter != end; ++iter) {
        TreeNode* pNode = new TreeNode();
        pNode->data = *iter;
        pNode->pfather = pf;
        pri_que.push(pNode);
    }

    // 合併構建
    while (pri_que.size() > 1) {
        TreeNode* plchild = pri_que.top(); pri_que.pop();
        TreeNode* prchild = pri_que.top(); pri_que.pop();
        TreeNode* pNode = new TreeNode();
        pNode->plchild = plchild;
        pNode->prchild = prchild;
        pNode->data = plchild->data + prchild->data; // 頻率相加
        pri_que.push(pNode);
    }
    return pri_que.top();
}

編碼生成（DFS）

深度優先搜索記錄路徑：左分支 '0'，右分支 '1'

const int MAXLEN = 20;
char path[MAXLEN] = {0};

template
void DFS(T* root, int deep = -1, char a = '-') {
    if (!root) return;
    if (a != '-') path[deep] = a;
    if (!root->plchild || !root->prchild) // 葉子節點
        (root->data).coded = string(path, path + deep + 1);
    if (root->plchild) DFS(root->plchild, deep + 1, '0');
    if (root->prchild) DFS(root->prchild, deep + 1, '1');
}

編碼提取（BFS）

廣度優先搜索收集葉子節點編碼：

template
void BFS(T* root, mydata* data) {
    queue que;
    que.push(root);
    while (!que.empty()) {
        T* pT = que.front(); que.pop();
        if (pT->plchild) que.push(pT->plchild);
        if (pT->prchild) que.push(pT->prchild);
        if (!pT->plchild || !pT->prchild) { // 葉子節點
            mydata* pd = data;
            while ((pT->data).data != pd->data) ++pd;
            pd->coded = (pT->data).coded;
        }
    }
}

template
class Huffman {
public:
    void Coded(string& coded);           // 編碼
    void DeCode(const string& codedstr, string& decodestr); // 解碼
    void InputData(T* begin, T* end);    // 輸入數據並統計頻率
private:
    string FindVal(char c);
    void m_CalcFreq(T* begin, T* end);
    TreeNode>* root;
    mydata* data;
    int data_size;
    T* m_begin, *m_end;
};

int main() {
    char* pmystr = "cbcddddbbbbaaaaaaa";
    Huffman h;
    h.InputData(pmystr, pmystr + 18);
    cout << "originstr: " << pmystr << endl;

    string coded;
    h.Coded(coded);
    cout << "coded: " << coded << endl;

    string decode;
    h.DeCode(coded, decode);
    cout << "decode: " << decode << endl;
    return 0;
}