您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> 關於C語言

數據結構：C 語言實現哈夫曼樹與哈夫曼編碼完整指南

編輯：關於C語言

數據結構：C 語言實現哈夫曼樹與哈夫曼編碼完整指南

1. 基本概念

路徑與路徑長度

若樹中存在結點序列 k1, k2, ..., kj，使得 ki 是 k_i+1 的雙親（1≤i<j），則稱此序列為從 k1 到 kj 的路徑。路徑長度為經過的分支數，等於路徑上結點數減 1。

結點的權與帶權路徑長度

許多應用中，樹的結點賦予實數權值。結點的帶權路徑長度 = 從根到該結點的路徑長度 × 該結點權值。

樹的帶權路徑長度 (WPL)

定義為所有葉子結點帶權路徑長度之和：
WPL = Σ (w_i × l_i)，i=1..n，n 為葉子數，w_i、l_i 分別為葉子權值與根到葉子路徑長度。
例：WPL = 9×2 + 12×2 + 15×2 + 6×3 + 3×4 + 5×4 = 122。

哈夫曼樹

又稱最優二叉樹。在 n 個帶權葉子構成的所有二叉樹中，WPL 最小者即為哈夫曼樹。為使結構盡量唯一，通常規定左子樹根權值 ≤ 右子樹根權值。

2. 構造哈夫曼樹

給定 n 個權值 w1..wn，構造規則：

將 n 個權值視為 n 棵單結點樹的森林；
在森林中選出根權值最小的兩棵樹合併，作為新樹的左右子樹，新根權值為兩子樹根權值之和；
從森林刪除這兩棵樹，加入新樹；
重複 (2)(3) 直到森林僅剩一棵樹，即為哈夫曼樹。

示例：權值 {3, 5, 6, 9, 12, 15} 構造過程圖解略。

3. 哈夫曼編碼

電報通信中，為縮短電文總長度，採用不等長編碼。以字符出現頻率為權值構造哈夫曼樹，左分支編 0、右分支編 1，根到葉子的路徑即該字符編碼。例：

a: 00
b: 01
c: 100
d: 1010
e: 1011
f: 11

4. 哈夫曼樹操作運算完整 C 代碼

/** 哈夫曼樹編碼完整實現 **/
#include <stdio.h>
#include <stdlib.h>
#define LENGTH 6

typedef int ElemType;
typedef struct HuffmanTreeNode {
    ElemType data;              // 結點權值
    struct HuffmanTreeNode *left, *right;
} HuffmanTreeNode, *PtrHuffman;

/** 創建哈夫曼樹 **/
PtrHuffman createHuffmanTree(ElemType arr[]) {
    PtrHuffman ptrArr[LENGTH], ptr, pRoot = NULL;
    for (int i = 0; i < LENGTH; i++) {
        ptr = (PtrHuffman)malloc(sizeof(HuffmanTreeNode));
        ptr->data = arr[i];
        ptr->left = ptr->right = NULL;
        ptrArr[i] = ptr;
    }
    for (int i = 1; i < LENGTH; i++) {
        int k1 = -1, k2;
        for (int j = 0; j < LENGTH; j++) {
            if (ptrArr[j] != NULL && k1 == -1) { k1 = j; continue; }
            if (ptrArr[j] != NULL) { k2 = j; break; }
        }
        for (int j = k2; j < LENGTH; j++) {
            if (ptrArr[j] != NULL) {
                if (ptrArr[j]->data < ptrArr[k1]->data) { k2 = k1; k1 = j; }
                else if (ptrArr[j]->data < ptrArr[k2]->data) { k2 = j; }
            }
        }
        pRoot = (PtrHuffman)malloc(sizeof(HuffmanTreeNode));
        pRoot->data = ptrArr[k1]->data + ptrArr[k2]->data;
        pRoot->left = ptrArr[k1];
        pRoot->right = ptrArr[k2];
        ptrArr[k1] = pRoot;
        ptrArr[k2] = NULL;
    }
    return pRoot;
}

/** 計算帶權路徑長度 WPL **/
ElemType calculateWeightLength(PtrHuffman ptrTree, int len) {
    if (ptrTree == NULL) return 0;
    if (ptrTree->left == NULL && ptrTree->right == NULL)
        return ptrTree->data * len;
    return calculateWeightLength(ptrTree->left, len+1) +
           calculateWeightLength(ptrTree->right, len+1);
}

/** 哈夫曼編碼（中序輸出葉子編碼） **/
void HuffmanCoding(PtrHuffman ptrTree, int len) {
    static int code[20];
    if (ptrTree != NULL) {
        if (ptrTree->left == NULL && ptrTree->right == NULL) {
            printf("結點權值為 %d 的編碼: ", ptrTree->data);
            for (int i = 0; i < len; i++) printf("%d", code[i]);
            printf("\n");
        } else {
            code[len] = 0;
            HuffmanCoding(ptrTree->left, len+1);
            code[len] = 1;
            HuffmanCoding(ptrTree->right, len+1);
        }
    }
}

/** 打印結點孩子關係 **/
void printHuffmanTreeChildNode(PtrHuffman node) {
    if (node->left == NULL && node->right == NULL) {
        printf("x=%d 是葉子結點\n\n", node->data);
        return;
    }
    if (node->left)  printf("x=%d 左孩子 lchild=%d\n", node->data, node->left->data);
    if (node->right) printf("x=%d 右孩子 rchild=%d\n", node->data, node->right->data);
    printf("\n");
}

/** 中序遍歷 **/
void midOrderPrint(PtrHuffman pRoot) {
    if (pRoot == NULL) return;
    midOrderPrint(pRoot->left);
    printf("%d ", pRoot->data);
    midOrderPrint(pRoot->right);
}

/** 先序遍歷（含孩子關係） **/
void preOrderPrint(PtrHuffman pRoot) {
    if (pRoot == NULL) return;
    printHuffmanTreeChildNode(pRoot);
    preOrderPrint(pRoot->left);
    preOrderPrint(pRoot->right);
}

/** 主程序測試 **/
int main() {
    ElemType arr[] = {3, 9, 5, 12, 6, 15};
    PtrHuffman pRoot = createHuffmanTree(arr);
    printf("========== 中序遍歷哈夫曼樹 ==========\n");
    midOrderPrint(pRoot);
    printf("\n\n========== 先序遍歷（含孩子關係） ==========\n");
    preOrderPrint(pRoot);
    printf("========== 計算帶權路徑長度 ==========\n");
    printf("WeightLength = %d\n\n", calculateWeightLength(pRoot, 0));
    printf("========== 各葉子結點哈夫曼編碼 ==========\n");
    HuffmanCoding(pRoot, 0);
    return 0;
}