數據結構之C語言實現哈夫曼樹

1、基本概念 a、路徑和路徑長度若在一棵樹中存在著一個結點序列 k1，k2，……，kj，使得 ki是ki+1 的雙親（1<=i<j），則稱此結點序列是從 k1 到 kj 的路徑。從 k1 到 kj 所經過的分支數稱為這兩點之間的路徑長度，它等於路徑上的結點數減1. b、結點的權和帶權路徑長度 ...

1、基本概念

a、路徑和路徑長度

若在一棵樹中存在著一個結點序列 k1，k2，……，kj，使得 ki是ki+1 的雙親（1<=i<j），則稱此結點序列是從 k1 到 kj 的路徑。

從 k1 到 kj 所經過的分支數稱為這兩點之間的路徑長度，它等於路徑上的結點數減1.

b、結點的權和帶權路徑長度

在許多應用中，常常將樹中的結點賦予一個有著某種意義的實數，我們稱此實數為該結點的權，(如下麵一個樹中的藍色數字表示結點的權)

結點的帶權路徑長度規定為從樹根結點到該結點之間的路徑長度與該結點上權的乘積。

c、樹的帶權路徑長度

樹的帶權路徑長度定義為樹中所有葉子結點的帶權路徑長度之和，公式為：

其中，n表示葉子結點的數目，wi 和 li 分別表示葉子結點 ki 的權值和樹根結點到 ki 之間的路徑長度。

如下圖中樹的帶權路徑長度 WPL = 9 x 2 + 12 x 2 + 15 x 2 + 6 x 3 + 3 x 4 + 5 x 4 = 122

d、哈夫曼樹

哈夫曼樹又稱最優二叉樹。它是 n 個帶權葉子結點構成的所有二叉樹中，帶權路徑長度 WPL 最小的二叉樹。

如下圖為一哈夫曼樹示意圖。

2、構造哈夫曼樹

假設有n個權值，則構造出的哈夫曼樹有n個葉子結點。 n個權值分別設為 w1、w2、…、wn，則哈夫曼樹的構造規則為：

(1) 將w1、w2、…，wn看成是有n 棵樹的森林(每棵樹僅有一個結點)；

(2) 在森林中選出兩個根結點的權值最小的樹合併，作為一棵新樹的左、右子樹，且新樹的根結點權值為其左、右子樹根結點權值之和；

(3)從森林中刪除選取的兩棵樹，並將新樹加入森林；

(4)重覆(2)、(3)步，直到森林中只剩一棵樹為止，該樹即為所求得的哈夫曼樹。

如：對下圖中的六個帶權葉子結點來構造一棵哈夫曼樹，步驟如下：

註意：為了使得到的哈夫曼樹的結構儘量唯一，通常規定生成的哈夫曼樹中每個結點的左子樹根結點的權小於等於右子樹根結點的權。

具體演算法如下：

/**
 * 創建哈夫曼樹
 */
PtrHuffman createHuffmanTree(ElemType arr[]){
    PtrHuffman ptrArr[LENGTH];
    PtrHuffman 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(i = 1; i < LENGTH; i++){  //進行 n-1 次迴圈建立哈夫曼樹  
        //k1表示森林中具有最小權值的樹根結點的下標,k2為次最小的下標
        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;  
            }  
        }  
        //將指針數組中的指針指向的最小值賦值給索引號為k1的,次小值賦值給索引號為k2的
        for (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指向樹根結點
        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指針數組中k1位置
        ptrArr[k2] = NULL; //k2位置為空
    }

    return pRoot;
}

3、哈夫曼編碼

在電報通信中，電文是以二進位的0、1序列傳送的，每個字元對應一個二進位編碼，為了縮短電文的總長度，採用不等長編碼方式，構造哈夫曼樹，

將每個字元的出現頻率作為字元結點的權值賦予葉子結點，每個分支結點的左右分支分別用0和1編碼，從樹根結點到每個葉子結點的路徑上

所經分支的0、1編碼序列等於該葉子結點的二進位編碼。如上文所示的哈夫曼編碼如下：

a 的編碼為：00

b 的編碼為：01

c 的編碼為：100

d 的編碼為：1010

e 的編碼為：1011

f 的編碼為：11

4、哈夫曼樹的操作運算

以上文的哈夫曼樹作為具體實例，用詳細的程式展示哈夫曼樹的操作運算：

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

typedef int ElemType;  

typedef struct HuffmanTreeNode{  
    ElemType data;  //哈夫曼樹中節點的權值
    struct HuffmanTreeNode* left;  
    struct HuffmanTreeNode* right;  
}HuffmanTreeNode,*PtrHuffman;  


/**
 * 創建哈夫曼樹
 */
PtrHuffman createHuffmanTree(ElemType arr[]){
    PtrHuffman ptrArr[LENGTH];
    PtrHuffman 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(i = 1; i < LENGTH; i++){  //進行 n-1 次迴圈建立哈夫曼樹  
        //k1表示森林中具有最小權值的樹根結點的下標,k2為次最小的下標
        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;  
            }  
        }  
        //將指針數組中的指針指向的最小值賦值給索引號為k1的,次小值賦值給索引號為k2的
        for (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指向樹根結點
        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指針數組中k1位置
        ptrArr[k2] = NULL; //k2位置為空
    }

    return pRoot;
}

/**
 * 計算哈夫曼樹帶權路徑長度WPL
 */
ElemType calculateWeightLength(PtrHuffman &ptrTree,int len){
    if(ptrTree==NULL){ //空樹返回0
        return 0;
    }else{
        if(ptrTree->left==NULL && ptrTree->right==NULL){ //訪問到葉子節點
            return ptrTree->data * len;
        }else{
            return calculateWeightLength(ptrTree->left,len+1) + calculateWeightLength(ptrTree->right,len+1); //向下遞歸計算
        }
    }
}


/**
 * 哈夫曼樹編碼(葉子節點按中序方式依次列印其編碼)
 */
void HuffmanCoding(PtrHuffman &ptrTree,int len){
    //靜態局部變數相當於全局變數(只是只有在這個函數中能訪問,但是生命周期是和全局變數差不多的)函數退出之後變數還在,而且只在第一次進入的時候做初始化,以後會跳過初始化語句,保留原來的值
    static int arr[20];  
    if(ptrTree != NULL){
        if(ptrTree->left==NULL && ptrTree->right==NULL){
           printf("結點權值為%d的編碼: ", ptrTree->data); 
           for(int i = 0; i < len; i++){
               printf("%d", arr[i]);      
           }   
           printf("\n"); 
        }else{
            arr[len] = 0;
            HuffmanCoding(ptrTree->left,len+1);
            arr[len] = 1;
            HuffmanCoding(ptrTree->right,len+1);
        }
    }
}


/**
 * 列印哈夫曼樹中各個節點的孩子節點
 * 若為葉子節點,則只顯示提示信息
 * @param node 需要顯示孩子節點的父節點
 */
void printHuffmanTreeChildNode(PtrHuffman node){
    if(node->left == NULL && node->right == NULL){
        printf("x=%d是哈夫曼樹中的葉子節點",node->data);
        printf("\n\n");
        return;
    }
    if(node->left != NULL){
        printf("x=%d在哈夫曼樹中的左孩子節點是lchild=%d",node->data,node->left->data);
        printf("\n");
    }
    if(node->right != NULL){
        printf("x=%d在哈夫曼樹中的右孩子節點是rchild=%d",node->data,node->right->data);
        printf("\n");
    }
    printf("\n");
}


/**
 * 中序列印哈夫曼樹的節點
 */
void midOrderprintHuffmanTreeNode(PtrHuffman &pRoot){
    if(pRoot==NULL){
        return;
    }else{
        midOrderprintHuffmanTreeNode(pRoot->left);
        printf("%d ",pRoot->data);
        midOrderprintHuffmanTreeNode(pRoot->right);
    }
}

/**
 * 先序列印哈夫曼樹的節點
 */
void PreOrderprintHuffmanTreeNode(PtrHuffman &pRoot){
    if(pRoot==NULL){
        return;
    }else{
        printHuffmanTreeChildNode(pRoot); //依次列印哈夫曼樹中各個節點的孩子節點
        PreOrderprintHuffmanTreeNode(pRoot->left);
        PreOrderprintHuffmanTreeNode(pRoot->right);
    }
}


/**
 * 測試程式入口
 */
int main(){
    ElemType arr[] = {3,9,5,12,6,15};
    PtrHuffman pRoot = createHuffmanTree(arr);  //返回指向哈夫曼樹根節點的指針

    printf("==========中序列印哈夫曼樹節點數據==========\n");
    midOrderprintHuffmanTreeNode(pRoot);
    printf("\n\n");

    printf("==========先序列印哈夫曼樹節點關係==========\n");
    PreOrderprintHuffmanTreeNode(pRoot);

    printf("==========計算帶權路徑長度==========\n");
    printf("WeightLength=%d\n",calculateWeightLength(pRoot,0));
    printf("\n");

    printf("==========各節點的哈夫曼樹編碼==========\n");
    HuffmanCoding(pRoot,0);

    fprintf(stdout,"\n");
    
    return 0;
}

運行結果截圖: