C語言實現哈夫曼樹的方法
本文實例為大傢分享瞭C語言實現哈夫曼樹的具體代碼,供大傢參考,具體內容如下
準備工作:
1、定義一個結構體,表示一個節點。其中,這個結構體有4個成員變量,分別表示是這個節點的權值,父節點及左右子節點的下標
2、定義一個整形數組,用於存放各個節點的權值
3、定義一個整形數組,用於存放哈夫曼編碼,當然也可以定義一個整形數組來存放哈夫曼編碼
構建哈夫曼樹:
1、給這個哈夫曼樹創建一個結構體數組,其中分配的空間是2 * n – 1,因為我們都知道哈夫曼樹的性質有一個是:給定n個葉子節點,那麼由這n個葉子節點構成 的哈夫曼樹一共含有2 * n – 1個節點。
2、結構體數組前面n個用於存放n個葉子節點,然後後面的n – 1個節點用於存放父節點。這時候,我們需要遍歷這個結構體數組,將所有的節點的進行初始化,即節點的權值就是結構體數組各個下標對應的值,然後節點的父節點及子節點的下標為-1,表示的是這個節點沒有父節點,同時也沒有子節點。
3、遍歷數組,將獲取數組中兩個最小的葉子節點,然後將他們的權值合並構成一個新節點。在這一步中,我們同時需要知道這兩個最小節點在結構體數組中的下標,隻有這樣,我們才可以知道它的父節點的左右子節點的下標,在初始化父節點的時候需要用到。
4、如果已經進行瞭n – 1次數操作,表明已經構建完成瞭。
獲取哈夫曼編碼:
1、由於我們將所有節點的權值都賦值給瞭一個數組,並且哈夫曼樹中的節點的下標和這個數組的下標是一一對應的,那麼我們隻需要首先在數組中獲取這個數字的下標,就表示他在哈夫滿樹中的下標也是這個,然後往它的父節點方向走,如果當前節點時它父節點的右子節點,那麼就將1存放到數組arr2中,否則字符將0存放到數組arr2中。重復這一步,直到當前的節點的父節點為空,及已經遍歷到瞭根節點。
2、重復步驟一,存放數字的數組已經遍歷完瞭,這時候已經將所有數字的哈夫曼編碼都已經輸出瞭
#include<stdio.h> #define MAX_SIZE 1000 typedef struct NODE Node; struct NODE{ int weight;//節點的權值 int parent,lchild,rchild; }; /* 初始化或者更改節點的信息,比如,如果這個節點是一個新節點,那麼 就需要將這個節點初始化成一個葉子節點,否則需要修改這個節點的父節點 */ void initNode(Node &node,int weight,int parent,int lchild,int rchild){ node.weight = weight; node.lchild = lchild; node.rchild = rchild; node.parent = parent; } /* 1、有n個葉子節點,那麼構建哈夫曼樹的時候,需要分配n * 2 - 1個內存空間,前n 個表示的是新輸入的葉子節點,後面n - 1表示的是葉子節點的父節點 2、遍歷這個數組,將進行初始化,即給這些節點的權值賦值,並且將他的左右子節 點、父節點賦初始值為-1,從而構建瞭n個葉子節點 3、遍歷數組,從而將從這個數組中跳出兩個值最小的葉子節點,同時需要標記他們的下標,從而可以知道當前最小值節點的父節點的左右子節點的下標,方便下次尋找 最小值的葉子結點的時候不會再找到已經找過的葉子節點 4、將新節點插入到數組的最後。 5、重復3,4的操作,直到隻有一個節點,那麼這個節點就是哈夫曼樹的根節點 */ void createHuffmanTree(Node *node,int *arr,int n){ //n表示有n個葉子節點,arr數組存放的是所有葉子節點的值 int i,j,min1,min2,x1,x2,total;//min1:第一個最小值,min2:第二個最小值,x1:第一個最小值的下標,x2:第二個最小值的下標 for(i = 0; i < n; i++){ initNode(node[i],arr[i],-1,-1,-1);//調用initNode方法,從而將節點進行初始化 } total = n * 2 - 1;//total表示的是哈夫曼所有節點的個數 for(i = n; i < total; i++){ //i之所以從n開始,是因為第一個父節點這個下標(前n個節點是葉子節點) min1 = 65432;//定義兩個最小值 min2 = min1; x1 = x2 = 0;//假設兩個最小值的下標都是0 for(j = 0; j < i; j++){ //判斷當前下標的節點是否為葉子節點 if(node[j].parent == -1){ //如果當前節點的parent等於-1,表示這個節點是一個葉子節點,那麼我們需要判斷他是否一個最小節點 if(node[j].weight < min1){ //如果當前這個節點的值比min1小,那麼我們需要更新min2,min1,同時需要更新兩者對應的下標 min2 = min1; x2 = x1; min1 = node[j].weight; x1 = j; }else if(node[j].weight < min2){ /* 如果當前這個節點比第一個最小值要大,那麼我們需要判斷 他是否比第二個最小值小,如果是,那麼更新min2,並且更新x2 */ min2 = node[j].weight; x2 = j; } } } /* 找到兩個最小節點之後,我們需要將這兩個節點的父節點指向i, 然後將i這個節點進行初始化,並且新節點的左子節點比右子節點小 從而構建唯一的哈夫曼樹 */ node[x1].parent = i; node[x2].parent = i; initNode(node[i],min1 + min2,-1,x1,x2);//初始化合並之後的新節點 } } void huffmanCode(Node *node,int child,int *str){ //str表示的是這個葉子節點的哈夫曼編碼 int i,parent,j = 0,e; parent = node[child].parent;//獲取當前這個葉子節點的父節點 while(parent != -1){ if(node[parent].lchild == child){ //如果當前這個節點是父節點的左子節點,那麼就將0壓入到數組中,否則將1壓入數組中 str[j++] = 0; }else{ str[j++] = 1; } child = parent; parent = node[child].parent; } e = j;//當退出循環的時候,j表示的是這個數的哈夫曼編碼的長度,所以需要從下標為j - 1開始逆序輸出,才是這個數的哈夫曼編碼 for(j = e - 1; j>= 0; j--) printf("%d",str[j]); printf("\n"); } int main(){ Node node[MAX_SIZE]; int arr[MAX_SIZE];//定義一個整形數組,用於存放所有葉子節點的權值 int arr2[MAX_SIZE];//arr2用於存放一個數字的哈夫曼編碼 int n,i,j,e; printf("請輸入葉子節點的個數:"); scanf("%d",&n); for(i = 0; i < n; i++) scanf("%d",&arr[i]); createHuffmanTree(node,arr,n);//構建哈夫曼樹 /* 獲取哈夫曼編碼: 1、將遍歷數組arr,從而獲得各個葉子節點的權值以及下標 2、通過這個下標,我們從這個節點向根節點走去,如果當前節點是父節點的左子 節點,那麼將0壓入到數組中,否則將1壓入到數組arr2中 3、逆序輸出arr2 */ for(i = 0; i < n; i++){ huffmanCode(node,i,arr2);//調用這個方法,將當前下標對應的數字的哈夫曼編碼輸出 } return 0; }
以上就是本文的全部內容,希望對大傢的學習有所幫助,也希望大傢多多支持WalkonNet。