数据结构哈夫曼树

赫夫曼树，别名“哈夫曼树”、“最优树”以及“最优二叉树”。学习哈夫曼树之前，首先要了解几个名词。 哈夫曼树相关的几个名词 路径 ： 在一棵树中，一个结点到另一个结点之间的通路，称为 路径。

（1）构建结点（2）代码实现（3）构建哈夫曼树

1）构建结点

typedef struct {
    int weight;
    int parent, left, right;
}HTNode, *HuffmanTree;

2）代码实现

void Select(HuffmanTree HT, int end, int *s1, int *s2)
{
    int min1, min2;
    int i = 1;
 
    while(HT[i].parent != 0 && i <= end){
        i++;
    }
    min1 = HT[i].weight;
    *s1 = i;
   
    i++;
    while(HT[i].parent != 0 && i <= end){
        i++;
    }
 
    if(HT[i].weight < min1){
        min2 = min1;
        *s2 = *s1;
        min1 = HT[i].weight;
        *s1 = i;
    }else{
        min2 = HT[i].weight;
        *s2 = i;
    }
 
    for(int j=i+1; j <= end; j++)
    {
        if(HT[j].parent != 0){
            continue;
        }
 
        if(HT[j].weight < min1){
            min2 = min1;
            min1 = HT[j].weight;
            *s2 = *s1;
            *s1 = j;
        }
 
        else if(HT[j].weight >= min1 && HT[j].weight < min2){
            min2 = HT[j].weight;
            *s2 = j;
        }
    }
}

3）构建哈夫曼树

void CreateHuffmanTree(HuffmanTree *HT, int *w, int n)
{
    if(n<=1) return; 
    int m = 2*n-1; 
    *HT = (HuffmanTree) malloc((m+1) * sizeof(HTNode)); 
    HuffmanTree p = *HT;
 
    for(int i = 1; i <= n; i++)
    {
        (p+i)->weight = *(w+i-1);
        (p+i)->parent = 0;
        (p+i)->left = 0;
        (p+i)->right = 0;
    }
 
    for(int i = n+1; i <= m; i++)
    {
        (p+i)->weight = 0;
        (p+i)->parent = 0;
        (p+i)->left = 0;
        (p+i)->right = 0;
    }
 
    for(int i = n+1; i <= m; i++)
    {
        int s1, s2;
        Select(*HT, i-1, &s1, &s2);
        (*HT)[s1].parent = (*HT)[s2].parent = i;
        (*HT)[i].left = s1;
        (*HT)[i].right = s2;
        (*HT)[i].weight = (*HT)[s1].weight + (*HT)[s2].weight;
    }
}