~~~ /* 根據Huffman樹的構造原理進行構造 ... 哈夫曼樹在編碼壓縮的領域有很好的應用,利用Huffman進行編碼可以保證數據傳輸 的無二義性 。 但是要注意的是 對于出現頻率大的數據我們應該盡量放在離根節點近的地方進行編碼 , 出現頻率小的數據我們可以放在距離根節點小的地方。 這樣可以提高數據的傳輸效率 。 */ #include "stdio.h" #include "malloc.h" ///節點聲明 typedef struct node{ node *lChild ; node *rChild ; int data ;//權值 }TreeNode ; TreeNode * CreateHuffmanTree(int a[],int n) ; //數組a表示權的數組 n是個數 void FindLittle(int *x1,int *x2 ,TreeNode**pArr,int n) ; //查找出2個權值最小的節點的下標 TreeNode * CreateHuffmanTree(int a[],int n) //數組a表示權的數組 n是個數 { TreeNode**pArr=(TreeNode**)malloc(sizeof(TreeNode*)*n); //動態產生指針數組 TreeNode*p =NULL;//用于返回哈夫曼樹的根節點的指針 int k1,k2 ; //k1代表最小權 k2代表次小權 用于做為 FindLittle的參數查找最小權下標 for(int i=0;i<n;i++) { pArr[i]=new TreeNode ; //為節點指針數組動態分配指向的對象 pArr[i]->data=a[i] ; pArr[i]->lChild=pArr[i]->rChild=NULL ;//初始化每個節點的左右節點都是空 } ///因為哈夫曼樹是循環的從節點數組中找出權值最小的兩個節點進行組合 并從數組中刪除這兩個節點,并把合并后的節點添加到數組中。 for(i=0;i<n-1;i++) //因為最后還剩下一個節點所以就會挑選n-1次 { FindLittle(&k1,&k2,pArr,n) ; //查找2個最小權節點下標 p=new TreeNode; //循環組合最后的p指向的節點便是最終的pRoot p->data=pArr[k1]->data+pArr[k2]->data ; p->lChild=pArr[k1] ; p->rChild=pArr[k2] ; pArr[k1]=p ; //將合并后的新節點賦值給pArr最小的那個下標 pArr[k2]=NULL ; // 次下標設置NULL, k1和k2也可以反過來這個具體我們自己定 } free(pArr) ;//釋放指針數組 return p; } void FindLittle(int *x1,int *x2 ,TreeNode**pArr,int n) //查找出2個權值最小的節點的下標 { int k1,k2; //保存權最小的兩個節點下標 k1=-1 ; //表示沒有找到數據 for(int i=0;i<n;i++) //找出其中的前兩個元素不為NULL的下標 { if(pArr[i]!=NULL&&k1==-1) { k1=i ; //第一個下標 continue ; } if(pArr[i]!=NULL) { k2=i ; break;//找到第二個下標退出循環 } } ////// 最小權的2個下標的搜索實現////////// for(i=k2;i<n;i++) //我們是先獲取k1 后獲取k2所以一開始 一定是從k2開始循環的 { if(pArr[i]!=NULL) { if(pArr[i]->data<pArr[k1]->data ) //如果下標k1的權 小于當前下標的元素的權 { k2=k1; //此時還是k1<k2滿足我們返回的結果 k1=i ; } else if(pArr[i]->data<pArr[k2]->data) { k2=i ; } } } *x1=k1 ; *x2=k2 ; } ///哈夫曼樹的先序遍歷 void PreHufOrder(TreeNode*p) //先序遍歷 { if(p!=NULL) { printf("%d ",p->data) ; PreHufOrder(p->lChild) ; PreHufOrder(p->rChild) ; } } //中序遍歷 void InHufOrder(TreeNode*p) { if(p!=NULL) { InHufOrder(p->lChild) ; printf("%d ",p->data) ; InHufOrder(p->rChild) ; } } //后續遍歷 void PostHufOrder(TreeNode*p) { if(p!=NULL) { InHufOrder(p->lChild) ; InHufOrder(p->rChild) ; printf("%d ",p->data) ; } } //清空樹 void ClearHufTree(TreeNode*p) { if(p!=NULL) { ClearHufTree(p->lChild) ; ClearHufTree(p->rChild) ; delete p ; } } int main() { int a[]={3,5,3,8,7,9,4,2,4,5,6,3,2,3} ; //權值 TreeNode*p=::CreateHuffmanTree(a,sizeof(a)/sizeof(int)) ; //創建huffman樹 printf("Huffman前序遍歷:\n") ; PreHufOrder(p) ; //前序遍歷huffmanTree printf("\n"); printf("Huffman后序遍歷:\n") ; PostHufOrder(p) ;//后序遍歷 printf("\n"); printf("Huffman中序遍歷:\n") ; InHufOrder(p) ;//中序遍歷 printf("\n"); ClearHufTree(p) ;//清空樹 return 0 ; } ~~~