Huffman树

从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称作路径长度。树的路径长度是从树根到每个结点的路径长度之和。结点的带权路径长度为结点到树根之间的路径长度与结点上权的乘机，树的带权路径长度为树中所有叶子节点的带权路径长度之和。

头文件：

/***************************************************************************************************** 
 *Copyright: Yue Workstation 
 * 
 *FileName: HuffmanTree.h 
 * 
 *Function: Huffman树的数据结构定义 
 * 
 *Author: Abel Lee 
 * 
 *CreateOn: 2012-2-19 
 * 
 *Log: 2012-2-19 由Abel Lee创建 
 *****************************************************************************************************/ 

#ifndef HUFFMAN_TREE_H 
#define HUFFMAN_TREE_H 

#include "global.h" 

#define NUMBER 4 

typedef struct 
{ 
          int weight; 
          int parent, lchild, rchild; 
}HTNode, *HuffmanTree; 

void PrintHuffmanTree(HuffmanTree ht, int n); 

#endif

源文件：

/***************************************************************************************************** 
 *Copyright:Yue Workstation 
 * 
 *FileName: HuffmanTree.c 
 * 
 *Function: Huffman树的操作 
 * 
 *Author:Abel Lee 
 * 
 *CreateOn:2012-2-19 
 * 
 *Log:2011-5-3 由Abel Lee创建 
 *****************************************************************************************************/ 

#include "../inc/HuffmanTree.h" 

//最小数 
static int _min(HuffmanTree ht, int i) 
{ 
          int j=0; 
          int temp=0; 

          for(j = 0; j<i; ++j) 
          { 
              if (ht[j].parent == 0) 
              { 
                   temp = j; 
                   break; 
              } 
          } 
          for(j = temp; j<i; ++j) 
          { 
              if (ht[j].parent == 0 && ht[j].weight<ht[temp].weight) 
             { 
                  temp = j; 
             } 
          } 
          return temp; 
} 

//次小数 
static int _sec_min(HuffmanTree ht, int i) 
{ 
         int min = _min(ht, i); 
         int j=0; 
         int temp=0; 
         for(j = 0; j<i; ++j) 
         { 
               if (ht[j].parent == 0 && j != min) 
              { 
                  temp = j; 
                  break; 
               } 
          } 
         for(j = temp; j<i; ++j) 
        { 
             if (ht[j].parent == 0 && ht[j].weight<ht[temp].weight && j != min) 
             { 
                  temp = j; 
            } 
         } 
     return temp; 
} 

//打印赫夫曼树 
void PrintHuffmanTree(HuffmanTree ht, int n) 
{ 
     int i = 0; 
    int temp = 0; 
    int val = 0; 
    for (i = 0; i < n; ++i) 
    { 
        printf("%d:", ht[i].weight); 
        val = i; 
        temp = ht[i].parent; 
        while (temp) 
        { 
            if (ht[temp].lchild == val) 
            { 
                printf("0"); 
            } 
            else if (ht[temp].rchild == val) 
            { 
                printf("1"); 
            } 
            else 
            { 

            } 
            val = temp; 
            temp = ht[temp].parent; 
        } 
        printf("\n"); 
    } 
} 

/**************************************************************************************************** 
 *Function Name: Huffmancoding 
 * 
 *Function: 获取霍夫曼编码 
 * 
 *Parameter:    ht:huffman树 
 *              w:权值 
 *              n：数量 
 * 
 *Return Value: 无 
 * 
 *Author:Abel Lee 
 * 
 *Log:2012-2-19 
 ***************************************************************************************************/ 
void Huffmancoding(HuffmanTree ht,  int *w, int n) 
{//w 存放 n 个字符的权值，构造赫夫曼树 ht， 并求出 n 个字符的赫夫曼编码 hc 

 int m; 
 int i; 
 int min=0, sec_min=0; 
 HuffmanTree p; 

 if (n<=1) return; 
 m = 2*n-1; 
 ht = (HuffmanTree)malloc(m*sizeof(HTNode)); 
 p = ht; 

 for(i=0; i<n; ++i, ++p, ++w)//给叶子节点赋值,前n个为叶子节点 
 { 
        p->weight = *w; 
        p->parent = 0; 
        p->lchild = 0; 
        p->rchild = 0; 
 } 
 for(; i<m; ++i,++p)//给非叶子节点赋值,第n个到(2*n - 1)个为叶子节点 
 { 
        p->weight = 0; 
        p->parent = 0; 
        p->lchild = 0; 
        p->rchild = 0; 
 } 

 for(i = n; i<m; ++i) 
 { 
       min = _min(ht, i); 
       sec_min = _sec_min(ht, i); 
       ht[min].parent = ht[sec_min].parent = i; 
       ht[i].lchild = min; 
       ht[i].rchild = sec_min; 
       ht[i].weight = ht[min].weight + ht[sec_min].weight; 
 } 
 PrintHuffmanTree(ht, n); 
}