當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

树：哈夫曼树和哈夫曼编码的详细介绍以及代码实现

發布時間：2025/3/15 编程问答 20 豆豆

生活随笔收集整理的這篇文章主要介紹了树：哈夫曼树和哈夫曼编码的详细介绍以及代码实现小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

閑扯前言

哈夫曼編碼的代碼實現對于初學數據結構的同學可能會有些困難，沒有必要灰心，其實沒啥，學習就猶如攀登一座又一座的山峰，每當我們攻克一個難點后，回首來看，也不過如此嘛。我們要做的就是不斷的去攀越學習上的山峰不斷的超越過去的自己。尤其是我們程序員，不進則退，中國最不缺的就是人，肯定不缺替代你的程序員，沒有越老越吃香的程序員，中國的老程序員都去哪了？要么轉管理，要么被淘汰轉行了，當然還有一小部分成為技術專家繼續活躍在IT圈。時代在進步，技術在不斷換代的更新，但是計算機一些固有的東西仍沒有改變，編程語言只是我們手中的武器，我們唯有把內功修煉好，然后拿著利器可以無往不勝！數據結構和算法就是我們程序員的內功修煉的一方面。不扯淡了。。。下面是博主如何攻克哈夫曼樹和哈夫曼編碼的一些思路。參考教材為 大話數據結構。

哈夫曼樹和哈夫曼編碼的關系

哈夫曼樹當然是一種樹，不過這種樹有些特殊之處。哈夫曼編碼呢，是根據哈夫曼樹規則生成的編碼！提供一個字符，根據哈夫曼編碼規則，你會得到一個哈夫曼編碼，不過你提供的字符必須在哈夫曼編碼表中有對應的編碼才行。

哈夫曼樹

哈夫曼大叔說，從樹中一個結點到另一個結點之間的分支構成2個結點之間的路徑，路勁上的分支數目稱作路徑長度。樹的路徑長度就是從樹根到每一結點的路徑長度之和。如果考慮到帶權的結點，結點的帶權的路徑長度就為從該結點到樹根之間的路徑長度與結點上權的乘積。樹的帶權路徑長度為樹中所有葉子結點的帶權路徑長度之和。

假設有n個權值{W1,W2.....,Wn}，構造一棵n個葉子結點的二叉樹，每個葉子結點帶權Wk，每個葉子的路徑長度為1k，我們通常記作，其中帶權路徑長度WPL最小的二叉樹稱為哈夫曼樹（又稱最優二叉樹）。

定義我們只要有理解就ok，重點是下面如何構建哈夫曼樹！

哈夫曼樹構造步驟

根據給定的n個權值{W1,W2,...,Wn}構成n棵二叉的集合F={T1,T2,...Tn}，其中每棵二叉樹Ti只有一個帶權為Wi的根結點，其左右子樹均為空。

在F中選取2棵根結點最小的樹作為左右子樹構造一棵新的二叉樹，且新的二叉樹的根結點左右子樹根結點權值之和。

在F中刪除這2棵子樹，同時將新得到的二叉樹加入F中。

重復2和3步驟，直到F只含一棵樹為止，這棵樹便是哈夫曼樹。

我們看這4個步驟，能否聯想到隊列的出隊入隊呢？往隊列方向想，思路是對的。將權值最小的2棵樹節點出隊，然后創建新結點入隊，這樣一直循環，最后剩下那一個樹結點時不就是哈夫曼樹么。下面是構建哈夫曼樹的HuffQueue.h的相關接口和數據結構。代碼匯總在最后。

HuffQueue.h

#pragma once #ifndef __HUFFQUEUE_H__ #define __HUFFQUEUE_H__ #include "HuffmanTree.h"//哈夫曼結點的隊列結點的數據結構 typedef struct HuffQueueNode {HuffmanNode* treeNode;//哈夫曼樹結點int weightNum;//權值struct HuffQueueNode* next;//指向下一個結點 }HuffQueueNode;//哈夫曼結點組成的隊列數據結構，由于插入數據（根據權值）和刪除數據（刪除隊頭的數據）的特性，需要結點個數和頭指針 typedef struct HuffQueue {int size;HuffQueueNode* first; }HuffQueue;//初始化隊列 void InitHuffQueue(HuffQueue** queue);//獲取結點（出隊操作），從隊頭出隊 HuffQueueNode* GetHuffQueueNode(HuffQueue* queue);//插入結點（入隊操作），特殊插入根據權值大小進行有序的插入結點非結尾處插入 void AddHuffQueueNode(HuffQueue* queue, HuffmanNode* treeNode, int weightNum);#endif // !__HUFFQUEUE_H__

BuildHuffmanTree函數

//根據用戶提供字符集，生成對應的哈夫曼樹 HuffmanTree BuildHuffmanTree(char* inputString) {//統計每個字符出現的權值int charWeight[MAX_SZ] = { 0 };for (int i = 0; i < inputString[i]!='\0'; i++){charWeight[(unsigned char)inputString[i]]++;}HuffQueue* queue = NULL;InitHuffQueue(&queue);for (int i = 0; i <MAX_SZ; i++){//對應的字符有權值，創建樹結點，添加到樹節點隊列中if (charWeight[i]){HuffmanNode* treeNode = (HuffmanNode*)malloc(sizeof(HuffmanNode));treeNode->data = i;treeNode->lchild = treeNode->rchild = NULL;AddHuffQueueNode(queue, treeNode, charWeight[i]);}}//根據哈夫曼樹創建原理構建哈夫曼樹//核心就是將權值最小的2個結點，取出作為新創建樹結點的孩子結點，新創建樹結點的權值為它們之和，然后放回樹結點隊列//一直這樣循環進行操作，直到隊列中最后剩一個結點，它就是樹的根結點。while (queue->size != 1){HuffQueueNode* node1 = GetHuffQueueNode(queue);HuffQueueNode* node2 = GetHuffQueueNode(queue);HuffmanNode* treeNode = (HuffmanNode*)malloc(sizeof(HuffmanNode));treeNode->data = '\0';treeNode->lchild = node1->treeNode;treeNode->rchild = node2->treeNode;int weightNum = node1->weightNum + node2->weightNum;AddHuffQueueNode(queue, treeNode, weightNum);}return queue->first->treeNode; }

哈夫曼編碼

定義還是先過一遍！一般地，設需要編碼的字符集為{d1,d2,...dn}，各個字符在電文中出現的次數或者頻率集合{W1,W2,...Wn},以d1,d2,...dn作為葉子結點，以W1,W2,...Wn作為相應葉子結點的權值來構造一棵哈夫曼樹。規定哈夫曼樹的左分支代表0，右分支代表1，則從根結點到葉子結點所經過的路勁分支組成的0和1的序列便為該結點對應字符的編碼，這就是哈夫曼編碼。

后面一句話是重點！走到葉子結點經過的0101...就是對應字符的哈夫曼編碼！

有了哈夫曼樹，寫哈夫曼編碼表就很好，編寫了！看下哈夫曼編碼表的數據結構采用鏈式隊列的方式，這樣是否更方便！數據結構是我們人為去定義，是為我們操作數據提供方便的。下面是 HuffmanTree.h提供的相關接口和相應的數據結構。代碼匯總在最后。

HuffmanTree.h

#pragma once #ifndef __HUFFMANTREE_H__ #define __HUFFMANTREE_H__//創建哈夫曼樹提供的字符的最大長度 #define MAX_SZ 256 //哈夫曼編碼字符串最大長度 #define MAX_ENCODE 1024 //哈夫曼樹結點數據結構 typedef struct HuffmanNode {char data;struct HuffmanNode *lchild, *rchild; }HuffmanNode,*HuffmanTree;//哈夫曼編碼表結點數據結構 typedef struct HuffmanTableNode {char data; //字符char *encode; //字符對應的哈夫曼編碼struct HuffmanTableNode *next; }HuffmanTableNode; //哈夫曼編碼表數據結構 typedef struct HuffmanTable {HuffmanTableNode* front;//指向隊頭元素HuffmanTableNode* tail; //指向隊尾元素 }HuffmanTable;//根據用戶提供原始數據，生成對應的哈夫曼樹 HuffmanTree BuildHuffmanTree(char* inputString);//根據哈夫曼樹生成對應的哈夫曼編碼表 HuffmanTable* BuildHuffmanTable(HuffmanTree tree);//對用戶提供的源字符進行哈夫曼編碼 char* encode(HuffmanTable* table, char* src);//根據用戶提供的哈夫曼編碼進行解碼 char* decode(HuffmanTree root, char* encode);//遍歷哈夫曼編碼表 void TraverseHuffmanTable(HuffmanTable* table); #endif // !__HUFFMANTREE_H__

BuildHuffmanTable函數

/* 遞歸遍歷哈夫曼樹 depth 樹的深度 tree 哈夫曼樹 hTable 哈夫曼編碼表 encode 字符對應的哈夫曼編碼 */ void traverseHuffTree(HuffmanTable* hTable,HuffmanTree tree,char* encode,int depth) {if (NULL == tree->lchild && NULL == tree->rchild){HuffmanTableNode* tableNode = (HuffmanTableNode*)malloc(sizeof(HuffmanTableNode));tableNode->data = tree->data;tableNode->next = NULL;encode[depth] = '\0';tableNode->encode = (char*)malloc(depth+1);strcpy(tableNode->encode, encode);if (hTable->front == NULL){hTable->front = hTable->tail = tableNode;}else{hTable->tail->next = tableNode;hTable->tail = tableNode;}}if (NULL != tree->lchild){encode[depth] = '0';//左分支代表0traverseHuffTree(hTable, tree->lchild, encode, depth+1);}if (NULL != tree->rchild){encode[depth] = '1';//右分支代表1traverseHuffTree(hTable, tree->rchild, encode, depth+1);}return; }//根據哈夫曼樹生成哈夫曼編碼表 HuffmanTable * BuildHuffmanTable(HuffmanTree tree) {HuffmanTable* hTable = (HuffmanTable*)malloc(sizeof(HuffmanTable));hTable->front = hTable->tail = NULL;char encode[MAX_SZ] = { 0 };traverseHuffTree(hTable, tree, encode, 0);return hTable; }

哈夫曼樹和哈夫曼編碼的使用

既然有了哈夫曼編碼，那么就可以進行對用戶提供的字符集進行哈夫曼編碼了喲，當然也可用利用用戶提供的哈夫曼編碼進行解碼咯。這就是小case了，encode 編碼：根據用戶提供的字符到哈夫曼編碼表中找到對應的哈夫曼編碼然后返回給用戶就可以了。decode解碼：用戶提供01100等哈夫曼編碼，利用哈夫曼樹進行解碼就ok，0就往左走，1就往右走，直到葉子結點對應的字符不就出來了么，然后又從哈夫曼樹根結點開始走，直到將哈夫曼編碼走完。下面是encode和decode代碼。

encode函數

char* encode(HuffmanTable* table,char* src) {char* encode = (char*)calloc(sizeof(char)*MAX_ENCODE,1);for (int i = 0; i < src[i]!='\0'; i++){char ch = src[i];HuffmanTableNode* iterator = table->front;while (iterator != NULL){if (iterator->data == ch){strcat(encode, iterator->encode);break;}iterator = iterator->next;}if (iterator == NULL){printf("哈夫曼編碼表中沒有字符%c對應的哈夫曼編碼！\n",ch);return NULL;}}return encode; }

decode函數

//根據用戶提供的哈夫曼編碼進行解碼 char* decode(HuffmanTree root,char* encode) {char* decode = (char*)calloc(MAX_SZ, 1);HuffmanTree tree = root;for (int i = 0; i < encode[i]!='\0'; i++){char ch = encode[i];if ('0' == ch)//0 往左走{tree = tree->lchild;}else//1 往右走{tree = tree->rchild;}//走到頭，也就是找到相應的源字符了if (tree->lchild == NULL && tree->rchild == NULL){strncat(decode, &tree->data, 1);//找到字符后，樹節點回到根結點，繼續解碼tree = root;}}return decode; }

代碼匯總一覽

HuffQueue.h

HuffQueue.c

#include "HuffQueue.h" #include <stdlib.h>//初始化隊列 void InitHuffQueue(HuffQueue** queue) {*queue = (HuffQueue*)malloc(sizeof(HuffQueue));(*queue)->size = 0;(*queue)->first = NULL; }//獲取結點（出隊操作），只需要樹節點的數據，故只返回樹節點數據 HuffQueueNode* GetHuffQueueNode(HuffQueue* queue) {if (NULL == queue || 0 == queue->size || NULL == queue->first){return NULL;}HuffQueueNode* queueNode = queue->first;queue->first = queue->first->next;queue->size--;return queueNode;}//插入結點（入隊操作），特殊插入根據權值大小進行有序的插入結點非隊尾處插入 void AddHuffQueueNode(HuffQueue* queue, HuffmanNode* treeNode, int weightNum) {HuffQueueNode *queueNode = (HuffQueueNode*)malloc(sizeof(HuffQueueNode));queueNode->weightNum = weightNum;queueNode->treeNode = treeNode;queueNode->next = NULL;//隊列為空if (0 == queue->size){queue->first = queueNode;queue->size++;return;}else{//比第一個結點權值都小if (weightNum < queue->first->weightNum){queueNode->next = queue->first;queue->first = queueNode;queue->size++;return;}HuffQueueNode* iterator = queue->first;HuffQueueNode* pre = NULL;while (iterator != NULL && weightNum > iterator->weightNum){pre = iterator;iterator = iterator->next;}//在隊列中找到自己位置，將其插入其中if (NULL != iterator){queueNode->next = iterator->next;iterator->next = queueNode;}//沒找到，說明自己權值最大，插入到末尾else{pre->next = queueNode;}queue->size++;return;}return; }

HuffmanTree.h

HuffmanTree.c

#define _CRT_SECURE_NO_WARNINGS #include <stdlib.h> #include <stdio.h> #include <string.h> #include "HuffmanTree.h" #include "HuffQueue.h"//根據用戶提供字符集，生成對應的哈夫曼樹 HuffmanTree BuildHuffmanTree(char* inputString) {//統計每個字符出現的權值int charWeight[MAX_SZ] = { 0 };for (int i = 0; i < inputString[i]!='\0'; i++){charWeight[(unsigned char)inputString[i]]++;}HuffQueue* queue = NULL;InitHuffQueue(&queue);for (int i = 0; i <MAX_SZ; i++){//對應的字符有權值，創建樹結點，添加到樹節點隊列中if (charWeight[i]){HuffmanNode* treeNode = (HuffmanNode*)malloc(sizeof(HuffmanNode));treeNode->data = i;treeNode->lchild = treeNode->rchild = NULL;AddHuffQueueNode(queue, treeNode, charWeight[i]);}}//根據哈夫曼樹創建原理構建哈夫曼樹//核心就是將權值最小的2個結點，取出作為新創建樹結點的孩子結點，新創建樹結點的權值為它們之和，然后放回樹結點隊列//一直這樣循環進行操作，直到隊列中最后剩一個結點，它就是樹的根結點。while (queue->size != 1){HuffQueueNode* node1 = GetHuffQueueNode(queue);HuffQueueNode* node2 = GetHuffQueueNode(queue);HuffmanNode* treeNode = (HuffmanNode*)malloc(sizeof(HuffmanNode));treeNode->data = '\0';treeNode->lchild = node1->treeNode;treeNode->rchild = node2->treeNode;int weightNum = node1->weightNum + node2->weightNum;AddHuffQueueNode(queue, treeNode, weightNum);}return queue->first->treeNode; } /* 遞歸遍歷哈夫曼樹 depth 樹的深度 tree 哈夫曼樹 hTable 哈夫曼編碼表 encode 字符對應的哈夫曼編碼 */ void traverseHuffTree(HuffmanTable* hTable,HuffmanTree tree,char* encode,int depth) {if (NULL == tree->lchild && NULL == tree->rchild){HuffmanTableNode* tableNode = (HuffmanTableNode*)malloc(sizeof(HuffmanTableNode));tableNode->data = tree->data;tableNode->next = NULL;encode[depth] = '\0';tableNode->encode = (char*)malloc(depth+1);strcpy(tableNode->encode, encode);if (hTable->front == NULL){hTable->front = hTable->tail = tableNode;}else{hTable->tail->next = tableNode;hTable->tail = tableNode;}}if (NULL != tree->lchild){encode[depth] = '0';//左分支代表0traverseHuffTree(hTable, tree->lchild, encode, depth+1);}if (NULL != tree->rchild){encode[depth] = '1';//右分支代表1traverseHuffTree(hTable, tree->rchild, encode, depth+1);}return; }//根據哈夫曼樹生成哈夫曼編碼表 HuffmanTable * BuildHuffmanTable(HuffmanTree tree) {HuffmanTable* hTable = (HuffmanTable*)malloc(sizeof(HuffmanTable));hTable->front = hTable->tail = NULL;char encode[MAX_SZ] = { 0 };traverseHuffTree(hTable, tree, encode, 0);return hTable; }//對用戶提供的源字符進行哈夫曼編碼 char* encode(HuffmanTable* table,char* src) {char* encode = (char*)calloc(sizeof(char)*MAX_ENCODE,1);for (int i = 0; i < src[i]!='\0'; i++){char ch = src[i];HuffmanTableNode* iterator = table->front;while (iterator != NULL){if (iterator->data == ch){strcat(encode, iterator->encode);break;}iterator = iterator->next;}if (iterator == NULL){printf("哈夫曼編碼表中沒有字符%c對應的哈夫曼編碼！\n",ch);return NULL;}}return encode; }//根據用戶提供的哈夫曼編碼進行解碼 char* decode(HuffmanTree root,char* encode) {char* decode = (char*)calloc(MAX_SZ, 1);HuffmanTree tree = root;for (int i = 0; i < encode[i]!='\0'; i++){char ch = encode[i];if ('0' == ch)//0 往左走{tree = tree->lchild;}else//1 往右走{tree = tree->rchild;}//走到頭，也就是找到相應的源字符了if (tree->lchild == NULL && tree->rchild == NULL){strncat(decode, &tree->data, 1);//找到字符后，樹節點回到根結點，繼續解碼tree = root;}}return decode; }//打印哈夫曼編碼表 void TraverseHuffmanTable(HuffmanTable* table) {HuffmanTableNode* node = table->front;while (node != NULL){printf("源字符:%c ->哈夫曼編碼:%s\n", node->data, node->encode);node = node->next;} }int main(int argc, char *argv[]) {HuffmanTree tree = BuildHuffmanTree("aabbccc");HuffmanTable* table = BuildHuffmanTable(tree);TraverseHuffmanTable(table);char *src = "abc";char* dest = "10110101101";char* encode_str = encode(table, src);char* decode_str = decode(tree, dest);printf("原始字符串:%s ->哈夫曼編碼:%s\n", src, encode_str);printf("哈夫曼編碼:%s ->解碼為:%s\n", dest, decode_str);return 0; }

圖解和運行測試

圖解

我們那字符串aabbccc來生成哈夫曼樹和哈夫曼編碼表。對應的哈夫曼樹如下圖：
很明顯，c字符->哈夫曼編碼為0，a字符->哈夫曼編碼10，b字符->哈夫曼編碼11。

測試代碼

int main(int argc, char *argv[]) {HuffmanTree tree = BuildHuffmanTree("aabbccc");HuffmanTable* table = BuildHuffmanTable(tree);TraverseHuffmanTable(table);char *src = "abc";char* dest = "10110101101";char* encode_str = encode(table, src);char* decode_str = decode(tree, dest);printf("原始字符串:%s ->哈夫曼編碼:%s\n", src, encode_str);printf("哈夫曼編碼:%s ->解碼為:%s\n", dest, decode_str);return 0; }

運行結果

總結

以上是生活随笔為你收集整理的树：哈夫曼树和哈夫曼编码的详细介绍以及代码实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

上一篇： Java 并发框架Disruptor（七
下一篇： MyBatis3系列__05查询补充re