一、個(gè)人理解

在遠(yuǎn)程通訊中，需要把字符轉(zhuǎn)成二進(jìn)制的字符串進(jìn)行傳輸，例如我們需要傳輸ABCD，我們可以用定長(zhǎng)的字符串進(jìn)行表示，例如:

1. A:00

2. B:01

3. C:02

4. D:03

這樣可能就造成空間的浪費(fèi)，我們多存儲(chǔ)了一個(gè)0號(hào)位。那用變長(zhǎng)呢，會(huì)怎么樣，我們?cè)囋?#xff0c;例如：

1. A:0

2. B:00

3. C:01

4. D:1

如果接收到的二進(jìn)制字符串為：0000101，在解碼時(shí)是否就會(huì)出現(xiàn)歧義，可以是AAAADAD,也可以是ABCC，也可以是BBDC等等。

從而引入了哈夫曼編碼，也稱(chēng)為最優(yōu)前綴碼。之前我們已經(jīng)實(shí)現(xiàn)了哈夫曼樹(shù)，可以參考文章鏈接《數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)-學(xué)習(xí)-17-二叉樹(shù)之哈夫曼樹(shù)》，從哈夫曼樹(shù)這個(gè)中間結(jié)果，轉(zhuǎn)換出我們想要的哈夫曼編碼。

二、為什么哈夫曼編碼得出二進(jìn)制字符串最短呢？

1. 在生成哈夫曼樹(shù)之前，我們需要統(tǒng)計(jì)字符在數(shù)據(jù)中出現(xiàn)的概率，出現(xiàn)的概率越高，編碼會(huì)越短。

2. 之前介紹過(guò)的哈夫曼樹(shù)的特點(diǎn)，權(quán)值越大的結(jié)點(diǎn)離根結(jié)點(diǎn)越近，也就是路徑越短。

3. 哈夫曼樹(shù)規(guī)定走左子樹(shù)就標(biāo)記為0，走右子樹(shù)就標(biāo)記為1，從根結(jié)點(diǎn)到各個(gè)葉子節(jié)點(diǎn)的標(biāo)記拼接起來(lái)，就是這個(gè)字符的哈夫曼編碼。

三、結(jié)構(gòu)體定義

typedef char** HaffmanCode;

四、函數(shù)實(shí)現(xiàn)

1、生成哈夫曼編碼

（1）定義

Status CreateHaffmanCode(HaffmanTree HT, HaffmanCode* HC, HaffmanTreeLentype ArrayLen)
{JudgeAllNullPointer(HT);//Init HaffmanCode*HC          = (HaffmanCode)MyMalloc(sizeof(char*) * ArrayLen);char* TmpHC = (char*)MyMalloc(sizeof(char) * (ArrayLen - 1));//臨時(shí)數(shù)組存放哈夫曼編碼中間結(jié)果,長(zhǎng)度n，編碼最長(zhǎng)需要n-1,所以分配n-1。HaffmanTreeLentype TmpHCLen = 0;HaffmanTreeLentype i,j;HaffmanTreeLentype TmpParentIndex;//上一個(gè)結(jié)點(diǎn)的父親索引。HaffmanTreeLentype TmpIndex;//上一個(gè)結(jié)點(diǎn)的索引號(hào)。for(i = 1; i <= ArrayLen; i++){TmpParentIndex = HT[i].ParentIndex;TmpIndex       = i;while(HT[TmpParentIndex].ParentIndex != 0){if(HT[TmpParentIndex].LeftChildIndex == TmpIndex){TmpHC[TmpHCLen] = '0';TmpHCLen++;}else if (HT[TmpParentIndex].RightChildIndex == TmpIndex){TmpHC[TmpHCLen] = '1';TmpHCLen++;}else{Log("Internal Error : Perant LeftChildIndex and RightChildIndex != TmpIndex",Error);}TmpIndex       = TmpParentIndex;TmpParentIndex = HT[TmpParentIndex].ParentIndex;}//根節(jié)點(diǎn)判斷if(HT[TmpParentIndex].LeftChildIndex == TmpIndex){TmpHC[TmpHCLen] = '0';TmpHCLen++;}else if(HT[TmpParentIndex].RightChildIndex == TmpIndex){TmpHC[TmpHCLen] = '1';TmpHCLen++;}else{Log("Internal Error : Root Node Perant LeftChildIndex and RightChildIndex != TmpIndex",Error);}//將TmpHC中的字符倒序?qū)懭際C中。(*HC)[i-1] = (char*)MyMalloc(sizeof(char) * (TmpHCLen + 1));//編碼最長(zhǎng)需要n,加上\0，所以分配n+1。for(j = TmpHCLen - 1; j >= 0; j--){(*HC)[i-1][TmpHCLen - 1 - j] = TmpHC[j];if(j == 0)//因?yàn)閖是無(wú)符號(hào)長(zhǎng)整型，j不能等于負(fù)數(shù)，當(dāng)j=-1,退出循環(huán)，導(dǎo)致程序core掉，由此添加此判斷，避免問(wèn)題的發(fā)生。{break;}}(*HC)[i-1][TmpHCLen] = '\0';TmpHCLen             = 0;}free(TmpHC);TmpHC = NULL;Log("Create HaffmanCode     : OK\n",Info);return SuccessFlag;
}

（2）參數(shù)

（3）實(shí)現(xiàn)思路

A,B,C,D,E對(duì)應(yīng)的權(quán)值如下：

HaffmanTreeLentype WeightArray[]  = {2,4,2,3,3};

生成哈夫曼樹(shù)如下：

2023-3--[Info]--HaffmanTree            :
[ Index | Weight | ParentIndex | LeftChildIndex | RightChildIndex ]
[ 0     | 0      | 0           | 0              | 0               ]
[ 1     | 2      | 6           | 0              | 0               ]
[ 2     | 4      | 8           | 0              | 0               ]
[ 3     | 2      | 6           | 0              | 0               ]
[ 4     | 3      | 7           | 0              | 0               ]
[ 5     | 3      | 7           | 0              | 0               ]
[ 6     | 4      | 8           | 1              | 3               ]
[ 7     | 6      | 9           | 4              | 5               ]
[ 8     | 8      | 9           | 6              | 2               ]
[ 9     | 14     | 0           | 7              | 8               ]

圖示如下：

從根節(jié)點(diǎn)開(kāi)始遍歷到每個(gè)葉子結(jié)點(diǎn)算出哈夫曼編碼比較困難，我們反其道而行之，從葉子結(jié)點(diǎn)開(kāi)始遍歷到根節(jié)點(diǎn)，但我們算出的結(jié)果是一個(gè)倒序的，我們需要一個(gè)臨時(shí)數(shù)組來(lái)存儲(chǔ)倒序編碼，最后再正序填寫(xiě)回哈夫曼編碼數(shù)組中即可。

例如我們來(lái)算一個(gè)A，父親是權(quán)值4，走左子樹(shù)為0，0寫(xiě)入臨時(shí)數(shù)組,

char TmpHC[] = {'0'}; 

再往上走，父親是權(quán)值8，走左子樹(shù)為0，0寫(xiě)入臨時(shí)數(shù)組，

char TmpHC[] = {'0','0'}; 

再往上走，父親是權(quán)值14，走右子樹(shù)為1，1寫(xiě)入臨時(shí)數(shù)組，

char TmpHC[] = {'0','0','1'}; 

倒序?qū)懟毓蚵幋a數(shù)組就是100。其他的大家自己可以算一下，是不是這樣，至于和老師講的可能有不一樣的地方，例如最后形成的編碼，只是由于數(shù)組中選出兩個(gè)最小的值，哪個(gè)是左子樹(shù)索引，哪個(gè)是右子樹(shù)索引，不一樣導(dǎo)致，但不影響編碼。最終得出的哈夫曼編碼如下：

2023-3--[Info]--HaffmanCode            :
[ Index | Code    ]
[ 1     | 100     ]
[ 2     | 11      ]
[ 3     | 101     ]
[ 4     | 00      ]
[ 5     | 01      ]

2、銷(xiāo)毀哈夫曼編碼

（1）定義

Status DestoryHaffmanCode(HaffmanCode HC,HaffmanTreeLentype ArrayLen)
{JudgeAllNullPointer(HC);HaffmanTreeLentype i;for(i = 0; i < ArrayLen; i++){free(HC[i]);HC[i] = NULL;}free(HC);HC = NULL;Log("Destory HaffmanCode    : OK\n",Info);return SuccessFlag;
}

（2）參數(shù)

四、虛機(jī)測(cè)試

[gbase@czg2 Tree]$ make
gcc -Wall -g ../Log/Log.c BinaryTree.c HaffmanTree.c main.c -o TestBinaryTree -I ../Log/
[gbase@czg2 Tree]$ ./TestBinaryTree 
2023-3--[Info]--Init Global Array      : OK
2023-3--[Info]--Init Binary Tree       : OK
2023-3--[Info]--New Binary Search Tree : OK
2023-3--[Info]--PreOrderTraverse       : [6 ,3 ,2 ,1 ,5 ,8 ,7 ], CurSize : 7
2023-3--[Info]--InOrderTraverse        : [1 ,2 ,3 ,5 ,6 ,7 ,8 ], CurSize : 7
2023-3--[Info]--PostOrderTraverse      : [1 ,2 ,5 ,3 ,7 ,8 ,6 ], CurSize : 7
2023-3--[Info]--PreOrderTraverseNoRcs  : [6 ,3 ,2 ,1 ,5 ,8 ,7 ], CurSize : 7
2023-3--[Info]--InOrderTraverseNoRcs   : [1 ,2 ,3 ,5 ,6 ,7 ,8 ], CurSize : 7
2023-3--[Info]--PostOrderTraverseNoRcs : [1 ,2 ,5 ,3 ,7 ,8 ,6 ], CurSize : 7
2023-3--[Info]--LevelOrderBinaryTree   : [6 ,3 ,8 ,2 ,5 ,7 ,1 ], CurSize : 7
2023-3--[Info]--SqQueue Data           :
Data           : [1 ,2 ,3 ,0 ,0 ,4 ,5 ,0 ,6 ,0 ,0 ,7 ,0 ,0 ,0 ]
FrontIndex     : 0
RearIndex      : 15
SqQueueLen     : 15
2023-3--[Info]--Init Binary Tree       : OK
2023-3--[Info]--PreOrderTraverse       : [1 ,2 ,3 ,4 ,5 ,6 ,7 ], CurSize : 7
2023-3--[Info]--InOrderTraverse        : [3 ,2 ,5 ,6 ,4 ,7 ,1 ], CurSize : 7
2023-3--[Info]--PostOrderTraverse      : [3 ,6 ,5 ,7 ,4 ,2 ,1 ], CurSize : 7
2023-3--[Info]--PreOrderTraverseNoRcs  : [1 ,2 ,3 ,4 ,5 ,6 ,7 ], CurSize : 7
2023-3--[Info]--InOrderTraverseNoRcs   : [3 ,2 ,5 ,6 ,4 ,7 ,1 ], CurSize : 7
2023-3--[Info]--PostOrderTraverseNoRcs : [3 ,6 ,5 ,7 ,4 ,2 ,1 ], CurSize : 7
2023-3--[Info]--LevelOrderBinaryTree   : [1 ,2 ,3 ,4 ,5 ,7 ,6 ], CurSize : 7
2023-3--[Info]--Init Binary Tree       : OK
2023-3--[Info]--Copy Tree              : OK
2023-3--[Info]--PreOrderTraverse       : [1 ,2 ,3 ,4 ,5 ,6 ,7 ], CurSize : 7
2023-3--[Info]--InOrderTraverse        : [3 ,2 ,5 ,6 ,4 ,7 ,1 ], CurSize : 7
2023-3--[Info]--PostOrderTraverse      : [3 ,6 ,5 ,7 ,4 ,2 ,1 ], CurSize : 7
2023-3--[Info]--Tree Depth             : 4
2023-3--[Info]--Tree Depth             : 5
2023-3--[Info]--Tree Depth             : 5
2023-3--[Info]--Tree Node Num          : 7
2023-3--[Info]--Tree Node Num          : 7
2023-3--[Info]--Tree Node Num          : 7
2023-3--[Info]--Tree Leaves Node Num   : 3
2023-3--[Info]--Tree Leaves Node Num   : 3
2023-3--[Info]--Tree Leaves Node Num   : 3
2023-3--[Info]--Create HaffmanTree     : OK
2023-3--[Info]--HaffmanTree            :
[ Index | Weight | ParentIndex | LeftChildIndex | RightChildIndex ]
[ 0     | 0      | 0           | 0              | 0               ]
[ 1     | 2      | 6           | 0              | 0               ]
[ 2     | 4      | 8           | 0              | 0               ]
[ 3     | 2      | 6           | 0              | 0               ]
[ 4     | 3      | 7           | 0              | 0               ]
[ 5     | 3      | 7           | 0              | 0               ]
[ 6     | 4      | 8           | 1              | 3               ]
[ 7     | 6      | 9           | 4              | 5               ]
[ 8     | 8      | 9           | 6              | 2               ]
[ 9     | 14     | 0           | 7              | 8               ]
2023-3--[Info]--Create HaffmanCode     : OK
2023-3--[Info]--HaffmanCode            :
[ Index | Code    ]
[ 1     | 100     ]
[ 2     | 11      ]
[ 3     | 101     ]
[ 4     | 00      ]
[ 5     | 01      ]
2023-3--[Info]--Destory HaffmanCode    : OK
2023-3--[Info]--Destory HaffmanTree    : OK
2023-3--[Info]--Destroy BT Node        : OK
2023-3--[Info]--Destroy BT Node        : OK
2023-3--[Info]--Destroy BT Node        : OK
2023-3--[Info]--Destroy BT Node        : OK
2023-3--[Info]--Destroy BT Node        : OK
2023-3--[Info]--Destroy BT Node        : OK
2023-3--[Info]--Destroy BT Node        : OK
2023-3--[Info]--Destroy BT Node        : OK
2023-3--[Info]--Destroy BT Node        : OK
2023-3--[Info]--Destroy BT Node        : OK
2023-3--[Info]--Destroy BT Node        : OK
2023-3--[Info]--Destroy BT Node        : OK
2023-3--[Info]--Destroy BT Node        : OK
2023-3--[Info]--Destroy BT Node        : OK
2023-3--[Info]--Destroy BT Node        : OK
2023-3--[Info]--Destroy BT Node        : OK
2023-3--[Info]--Destroy BT Node        : OK
2023-3--[Info]--Destroy BT Node        : OK
2023-3--[Info]--Destroy BT Node        : OK
2023-3--[Info]--Destroy BT Node        : OK
2023-3--[Info]--Destroy BT Node        : OK