這篇文章主要講解了C語(yǔ)言怎么實(shí)現(xiàn)哈夫曼樹的構(gòu)建，內(nèi)容清晰明了，對(duì)此有興趣的小伙伴可以學(xué)習(xí)一下，相信大家閱讀完之后會(huì)有幫助。
成都創(chuàng)新互聯(lián)公司-專業(yè)網(wǎng)站定制、快速模板網(wǎng)站建設(shè)、高性價(jià)比冷水灘網(wǎng)站開發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫(kù),直接使用。一站式冷水灘網(wǎng)站制作公司更省心,省錢,快速模板網(wǎng)站建設(shè)找我們，業(yè)務(wù)覆蓋冷水灘地區(qū)。費(fèi)用合理售后完善，10余年實(shí)體公司更值得信賴。
哈夫曼樹（霍夫曼樹）又稱為最優(yōu)樹.
1、路徑和路徑長(zhǎng)度
在一棵樹中，從一個(gè)結(jié)點(diǎn)往下可以達(dá)到的孩子或?qū)O子結(jié)點(diǎn)之間的通路，稱為路徑。通路中分支的數(shù)目稱為路徑長(zhǎng)度。若規(guī)定根結(jié)點(diǎn)的層數(shù)為1，則從根結(jié)點(diǎn)到第L層結(jié)點(diǎn)的路徑長(zhǎng)度為L(zhǎng)-1。
2、結(jié)點(diǎn)的權(quán)及帶權(quán)路徑長(zhǎng)度
若將樹中結(jié)點(diǎn)賦給一個(gè)有著某種含義的數(shù)值，則這個(gè)數(shù)值稱為該結(jié)點(diǎn)的權(quán)。結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度為：從根結(jié)點(diǎn)到該結(jié)點(diǎn)之間的路徑長(zhǎng)度與該結(jié)點(diǎn)的權(quán)的乘積。
3、樹的帶權(quán)路徑長(zhǎng)度
樹的帶權(quán)路徑長(zhǎng)度規(guī)定為所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和，記為WPL
#include#include #include /* 哈夫曼樹的結(jié)構(gòu)體 */ typedef struct stHuNode { int data; //權(quán)值 struct stHuNode* lchild, *rchild; }HUNODE; /* * 找出權(quán)值數(shù)組里面,最小的兩個(gè)權(quán)值下標(biāo) * 函數(shù)請(qǐng)參：HUNODE *pArray[] 存放節(jié)點(diǎn)的指針數(shù)組 int n 數(shù)組里面的元素個(gè)數(shù) int* p1 存放最小權(quán)值的下標(biāo) int* p2 存放第二小權(quán)值的下標(biāo) */ int findSmallData(HUNODE *pArray[] ,int n,int* p1, int* p2) { int index = 0; int fir_small = 0xffff, sec_small = 0xffff; if(pArray == NULL) { return 1; } for(index = 0; index < n; index++) { /* 當(dāng)前的下標(biāo)下面是有節(jié)點(diǎn)的*/ if(pArray[index] != NULL) { if(pArray[index]->data < fir_small) { sec_small = fir_small; fir_small = pArray[index]->data; *p2 = *p1; *p1 = index; } else if(pArray[index]->data < sec_small) { sec_small = pArray[index]->data; *p2 = index; } } } return 0; } /* * 函數(shù)功能：構(gòu)建哈夫曼樹 * 函數(shù)請(qǐng)參：int* a 權(quán)值數(shù)組 int n 這個(gè)數(shù)組里面有多少個(gè)數(shù)據(jù) */ HUNODE* createHuTree(int* a, int n) { int index = 0; int fir_small = 0, sec_small = 0; /* 定義一個(gè)指針數(shù)組,最大是100 */ HUNODE *pArray[100]; HUNODE *pNewNode = NULL; /* 先創(chuàng)建n個(gè)root節(jié)點(diǎn)*/ memset(pArray,0,sizeof(HUNODE)*n); for(index = 0; index < n; index++) { pNewNode = (HUNODE*)malloc(sizeof(HUNODE)); memset(pNewNode,0,sizeof(HUNODE)); pNewNode->data = a[index]; pNewNode->lchild = NULL; pNewNode->rchild = NULL; /* 把這個(gè)節(jié)點(diǎn)存放在指針數(shù)組中去 */ pArray[index] = pNewNode; } /* 構(gòu)建哈夫曼樹 */ for(index = 0; index < n-1; index++) { /* fir_small 存放最小權(quán)值的下標(biāo) sec_small存放第二個(gè)小的權(quán)值下標(biāo)*/ findSmallData(pArray,n,&fir_small,&sec_small); /* 分配節(jié)點(diǎn)內(nèi)存 */ pNewNode = (HUNODE*)malloc(sizeof(HUNODE)); memset(pNewNode,0,sizeof(HUNODE)); pNewNode->data = pArray[fir_small]->data + pArray[sec_small]->data; /* 最小的是左孩子，第二小的是右孩子 */ pNewNode->lchild = pArray[fir_small]; pNewNode->rchild = pArray[sec_small]; /* 把新的節(jié)點(diǎn)放入到指針數(shù)組里面去 */ pArray[fir_small] = NULL; pArray[sec_small] = pNewNode; } return pNewNode; } /* 前序遍歷該二叉樹 */ void preOrderHuffMan(HUNODE* root) { if(root) { printf("%d ",root->data); preOrderHuffMan(root->lchild); preOrderHuffMan(root->rchild); } } int main() { int a[4] = {7,5,2,4}; HUNODE* root = NULL; /* 構(gòu)建哈夫曼樹 */ root = createHuTree(a,4); /* 前序遍歷 */ preOrderHuffMan(root); printf("\n"); return 0; }
看完上述內(nèi)容，是不是對(duì)C語(yǔ)言怎么實(shí)現(xiàn)哈夫曼樹的構(gòu)建有進(jìn)一步的了解，如果還想學(xué)習(xí)更多內(nèi)容，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道。
重慶分公司
重慶分公司
