C語言實現哈夫曼樹的構建

哈夫曼樹（霍夫曼樹）又稱為最優樹.

1、路徑和路徑長度

在一棵樹中，從一個結點往下可以達到的孩子或孫子結點之間的通路，稱為路徑。通路中分支的數目稱為路徑長度。若規定根結點的層數為1，則從根結點到第L層結點的路徑長度為L-1。

2、結點的權及帶權路徑長度

若將樹中結點賦給一個有著某種含義的數值，則這個數值稱為該結點的權。結點的帶權路徑長度為：從根結點到該結點之間的路徑長度與該結點的權的乘積。

3、樹的帶權路徑長度

樹的帶權路徑長度規定為所有葉子結點的帶權路徑長度之和，記為WPL

#include
#include#include
/* 哈夫曼樹的結構體 */ 
typedef struct stHuNode { 
int data; //權值 
struct stHuNode* lchild, *rchild; 
}HUNODE; 
/* * 找出權值數組裡面,最小的兩個權值下標 
* 函數請參：HUNODE 
*pArray[] 存放節點的指針數組 int 
n 數組裡面的元素個數 int
* p1 存放最小權值的下標 int* p2 存放第二小權值的下標 
*/
 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++) 
 { /* 當前的下標下面是有節點的*/ 
 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; } /
    * * 函數功能：構建哈夫曼樹 
    * 函數請參：int
    * a 權值數組 int n 這個數組裡面有多少個數據 
    */ 
    HUNODE* createHuTree(int* a, int n) { 
    int index = 0; int fir_small = 0, sec_small = 0; 
    /* 定義一個指針數組,最大是100 */
     HUNODE *pArray[100]; HUNODE *pNewNode = NULL; 
     /* 先創建n個root節點*/ 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; 
       /* 把這個節點存放在指針數組中去 */ 
      pArray[index] = pNewNode; } 
      /* 構建哈夫曼樹 */ 
      for(index = 0; index < n-1; index++) { 
      /* fir_small 存放最小權值的下標 sec_small存放第二個小的權值下標*/ findSmallData(pArray,n,&fir_small,&sec_small); /* 
      分配節點內存 */ 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]; 
    /* 把新的節點放入到指針數組裡面去 */
     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; 
    /* 構建哈夫曼樹 */
     root = createHuTree(a,4); 
    /* 前序遍歷 */
     preOrderHuffMan(root); printf("

"); return 0; }