最簡哈夫曼樹是一種數據結構，是由德國數學家馮·哈夫曼發現的，又稱最優二叉樹，是一種帶權路徑長最短的樹。
基本介紹
簡介,套用,構建,編碼,
簡介
樹對於編程具有重大的意義，使某些看似不可能完成或很難完成的任務較為簡單，有條理的完成。
套用
#include<stdio.h>
最簡哈夫曼樹
#include<stdlib.h>
#include<string.h>
#include<conio.h>a
#include<graphics.h>
#define MAXVALUE 200 /*權值的最大值*/
#define MAXB99v 30 /*最大的編碼位數*/
#define MAXNODE 30 /*初始的最大的結點數*/
struct haffnode
{char data;
int weight;
int flag;
int parent; /*雙親結點的下標*/int leftchild; /*左孩子下標*/
哈夫曼樹
哈夫曼樹int rightchild; /*右孩子下標*/
};
struct haffcode
{int bit[MAXNODE];
int start; /*編碼的起始下標*/
char data;
int weight; /*字元權值*/
};
構建
/*函式說明*/
最簡哈夫曼樹
/************************************************************************/
void pprintf(struct haffcode haffcode[],int n);
/*輸出函式*/
void haffmantree(int weight[],int n,struct haffnode hafftree[],char data[]);
/*建立哈夫曼樹*/
void haffmancode(struct haffnode hafftree[],int n,struct haffcode haffcode[]);
/*求哈夫曼編碼*/
void test(struct haffcode haffcode[],int n);
/*測試函式*/
void end();
/*結束界面函式*/
/************************************************************************/void haffmantree(int weight[],int n,struct haffnode hafftree[],char data[])
/*建立葉結點個數為n，權值數組為weight[]的哈夫曼樹*/
{int i,j,m1,m2,x1,x2;
/*哈夫曼樹hafftree[]初始化，n個葉結點共有2n-1個結點*/
for(i=0;i<2*n-1;i++)
{if(i<n) {hafftree[i].data=data[i];
hafftree[i].weight=weight[i]; /*葉結點*/
}
else {hafftree[i].weight=0; /*非葉結點*/
hafftree[i].data='\0';
}
hafftree[i].parent=0; /*初始化沒有雙親結點*/
hafftree[i].flag=0;
hafftree[i].leftchild=-1;
sp; hafftree[i].rightchild=-1;
}
for(i=0;i<n-1;i++) /*構造哈夫曼樹n-1個非葉結點*/
編碼
本文描述在網上能夠找到的最簡單，最快速的哈夫曼編碼。該方法不使用任何擴展動態庫，比如STL或者組件。只使用簡單的C函式，比如：memset，memmove，qsort，malloc，realloc和memcpy。
因此，大家都會發現，理解甚至修改這個編碼都是很容易的。
背景
。因此，在檔案中出現頻率高的符號，使用短的位序列，而那些很少出現的符號，則用較長的位序列。編碼使用
哈夫曼樹
哈夫曼樹我用簡單的C函式寫這個編碼是為了讓它在任何地方使用都會比較方便。你可以將他們放到類中，或者直接使用這個函式。並且我使用了簡單的格式，僅僅輸入輸出緩衝區，而不象其它文章中那樣，輸入輸出檔案。
bool CompressHuffman(BYTE *pSrc,int nSrcLen,BYTE *&pDes,int &nDesLen);bool DecompressHuffman(BYTE *pSrc,int nSrcLen,BYTE *&pDes,int &nDesLen);
要點說明
速度
為了讓它（huffman.cpp）快速運行，我花了很長時間。同時，我沒有使用任何動態庫，比如STL或者MFC。它壓縮1M數據少於100ms（P3處理器，主頻1G）。
壓縮
壓縮代碼非常簡單，首先用ASCⅡ值初始化511個哈夫曼節點：
CHuffmanNode nodes[511];for(int nCount = 0; nCount < 256; nCount++) nodes[nCount].byAscii = nCount；然後，計算在輸入緩衝區數據中，每個ASCⅡ碼出現的頻率：for(nCount = 0; nCount < nSrcLen; nCount++) nodes[pSrc[nCount]].nFrequency++；然後，根據頻率進行排序：qsort(nodes,256,sizeof(CHuffmanNode),frequencyCompare）；現在，構造哈夫曼樹，獲取每個ASCⅡ碼對應的位序列：int nNodeCount = GetHuffmanTree(nodes）；構造哈夫曼樹非常簡單，將所有的節點放到一個佇列中，用一個節點替換兩個頻率最低的節點，新節點的頻率就是這兩個節點的頻率之和。這樣，新節點就是兩個被替換節點的父節點了。如此循環，直到佇列中只剩一個節點（樹根）。// parent nodepNode = &nodes[nParentNode++];// pop first childpNode->pLeft = PopNode(pNodes,nBackNode--,false);// pop second childpNode->pRight = PopNode(pNodes,nBackNode--,true);// adjust parent of the two poped nodespNode->pLeft->pParent = pNode->pRight->pParent = pNode;// adjust parent frequencypNode->nFrequency = pNode->pLeft->nFrequency + pNode->pRight->nFrequency；這裡我用了一個好的訣竅來避免使用任何佇列組件。我先前就直到ASCⅡ碼只有256個，但我分配了511個（CHuffmanNode）
兩個變數來操作佇列索引（int nParentNode = nNodeCount;nBackNode = nNodeCount –1）。
接著，壓縮的最後一步是將每個ASCⅡ編碼寫入輸出緩衝區中：int nDesIndex = 0;// loop to write codesfor(nCount = 0; nCount < nSrcLen; nCount++){ *(DWORD*)(pDesPtr+(nDesIndex>>3）） |= nodes[pSrc[nCount]].dwCode << (nDesIndex&7）； nDesIndex += nodes[pSrc[nCount]].nCodeLength;}(nDesIndex>>3）： >>3 以8位為界限右移後到達右邊位元組的前面
（nDesIndex&7）： &7 得到最高位. 注意：在壓縮緩衝區中，我們必須保存哈夫曼樹的節點以及位序列，這樣我們才能在解壓縮時重新構造哈夫曼樹（只需保存ASCⅡ值和對應的位序列）。
解壓縮比構造哈夫曼樹要簡單的多，將輸入緩衝區中的每個編碼用對應的ASCⅡ碼逐個替換就可以了。只要記住，這裡的輸入緩衝區是一個包含每個ASCⅡ值的編碼的位流。因此，為了用ASCⅡ值替換編碼，我們必須用位流搜尋哈夫曼樹，直到發現一個葉節點，然後將它的ASCⅡ值添加到輸出緩衝區中：
int nDesIndex = 0;DWORD nCode;while(nDesIndex < nDesLen){ nCode = (*(DWORD*)(pSrc+(nSrcIndex>>3）））>>(nSrcIndex&7）； pNode = pRoot; while(pNode->pLeft) { pNode = (nCode&1） pNode->pRight : pNode->pLeft; nCode >>= 1; nSrcIndex++; } pDes[nDesIndex++] = pNode->byAscii;}(nDesIndex>>3）： >>3 以8位為界限右移後到達右邊位元組的前面 (nDesIndex&7）： &7 得到最高位.
