赫夫曼樹

赫夫曼樹是一種基於赫夫曼編碼的二叉樹。赫夫曼編碼是一種無損編碼方式，假設一個字元的出現頻率越高，則編碼的位數越少，從而在傳輸數據時佔用的帶寬更小。赫夫曼樹的構建方法是，先按照字元出現的頻率構建一個森林，然後迭代地將頻率較小的樹合併成一個新的樹，直到只剩下一棵樹為止。

一、赫夫曼編碼的應用

赫夫曼編碼是一種無損壓縮編碼，通常用於圖像、音頻、視頻等數據傳輸和存儲中。由於這些數據通常需要傳輸的時間很長，因此對於它們的壓縮和解壓速度要求非常高。而赫夫曼編碼可以根據字元出現的頻率來確定每個字元的編碼，從而實現儘可能小的壓縮比。

二、赫夫曼樹的構建

赫夫曼樹的構建是一個迭代的過程，首先需要對文本中的字元進行一次掃描，以統計每個字元出現的頻率。然後將每個字元視為一棵以其出現頻率為根節點的樹，並按照頻率從小到大排序。

// C++代碼示例
struct node {
    char ch; // 字元
    int freq; // 頻率
    node * left, * right; // 左右孩子
};

node * buildHuffmanTree(string s) {
    // 統計字元頻率
    map freq;
    for (char c : s) {
        freq[c]++;
    }
    // 初始化森林
    vector forest;
    for (auto p : freq) {
        node * t = new node;
        t->ch = p.first;
        t->freq = p.second;
        t->left = t->right = nullptr;
        forest.push_back(t);
    }
    // 構建赫夫曼樹
    while (forest.size() > 1) {
        sort(forest.begin(), forest.end(), [](node * a, node * b) { return a->freq freq; });
        node * l = forest[0], * r = forest[1];
        node * p = new node;
        p->ch = 0;
        p->freq = l->freq + r->freq;
        p->left = l;
        p->right = r;
        forest.erase(forest.begin(), forest.begin()+2);
        forest.push_back(p);
    }
    return forest[0];
}

三、赫夫曼編碼的計算

赫夫曼編碼計算的過程是從根節點開始，每次遇到左孩子則標記1，遇到右孩子則標記0，直到遍歷到葉子節點。遍歷到葉子節點時得到的01串就是該葉子節點對應的編碼。由於赫夫曼編碼的特殊性質，任何一個編碼都不是另一個編碼的前綴，因此可以方便地解碼。

// C++代碼示例
void getHuffmanCode(node * root, string code, map & huffmanCode) {
    if (root == nullptr) return;
    if (root->left == nullptr && root->right == nullptr) {
        huffmanCode[root->ch] = code;
        return;
    }
    getHuffmanCode(root->left, code+"1", huffmanCode);
    getHuffmanCode(root->right, code+"0", huffmanCode);
}

四、赫夫曼樹的性質

赫夫曼樹的高度和字元的出現頻率有關係，出現頻率較高的字元在樹中的深度較小，出現頻率較低的字元在樹中的深度較大。因此，赫夫曼樹是一種帶權路徑最短的樹。

五、小結

赫夫曼樹是一種基於赫夫曼編碼的二叉樹，用於提供無損壓縮編碼方案。它的構建過程是一個迭代的過程，每次將森林中頻率較小的樹合併成一個新的樹，直到只剩下一棵樹為止。赫夫曼編碼計算的過程是從根節點開始，每次遇到左孩子則標記1，遇到右孩子則標記0，直到遍歷到葉子節點。赫夫曼樹具有帶權路徑最短的性質，即出現頻率較高的字元在樹中的深度較小，出現頻率較低的字元在樹中的深度較大。