RodneyX

這個就不談原理了，很簡單的，按課本上寫的哈夫曼樹構(gòu)造的算法描述直接寫就是了。這里采用常規(guī)操作，用小頂堆來加快構(gòu)造速度，見http://www.rzrgm.cn/RodneyTang/p/19013567

代碼如下

/*****file:HuffmanTree.h*****/
#ifndef HUFFMANTREE_H
#define HUFFMANTREE_H
#include<stdlib.h>
#define ASCIInum 128
#define INVALID 128

typedef struct HuffmanNode {
    char data;
    int weight;
    struct HuffmanNode *left, *right;
}HuffmanNode;

typedef struct HuffmanTree {
    HuffmanNode *root;
}HuffmanTree;

//only support ASCII
double ASCII_probability[ASCIInum];
//void compute_probability()
void _adjust_minHeap_HuffmanTree(HuffmanNode **nodes_pointers, int pos, int length);
void create_HuffmanTree(HuffmanTree &HT);

#endif


/*****file:HuffmanTree.cpp*****/
#include "HuffmanTree.h"

void _adjust_minHeap_HuffmanTree(HuffmanNode **nodes_pointers, int pos, int length) {
    int i = pos, k;
    HuffmanNode *sift = nodes_pointers[pos];
    while(true) {
        k = i * 2 + 1;
        if(k < length && k + 1 < length && nodes_pointers[k]->weight > nodes_pointers[k + 1]->weight)
            ++k;
        if(k < length && sift->weight > nodes_pointers[k]->weight) {
            nodes_pointers[i] = nodes_pointers[k];
            i = k;
        }
        else {
            nodes_pointers[i] = sift;
            break;
        }
    }
}

void create_HuffmanTree(HuffmanTree &HT) {
    HuffmanNode **nodes_pointers = (HuffmanNode**)malloc(sizeof(HuffmanNode*) * ASCIInum);
    for(int i = 0; i < ASCIInum; ++i) {
        nodes_pointers[i] = (HuffmanNode*)malloc(sizeof(HuffmanNode));
        nodes_pointers[i]->data = i;
        nodes_pointers[i]->weight = ASCII_probability[i];
        nodes_pointers[i]->left = nodes_pointers[i]->right = nullptr;
    }

    //create minHeap
    for(int i = (ASCIInum - 1) / 2; i >= 0; --i)
        _adjust_minHeap_HuffmanTree(nodes_pointers, i, ASCIInum);
    
    //create Huffman Tree
    HuffmanNode *p = nullptr, *lchild = nullptr, *rchild = nullptr;
    for(int i = 0; i < ASCIInum - 1; ++i) {
        lchild = nodes_pointers[0];
        nodes_pointers[0] = nodes_pointers[ASCIInum - 1 - i];
        _adjust_minHeap_HuffmanTree(nodes_pointers, 0, ASCIInum - 1 - i);

        rchild = nodes_pointers[0];

        p = (HuffmanNode*)malloc(sizeof(HuffmanNode));
        p->weight = lchild->weight + rchild->weight;
        p->data = INVALID;
        p->left = lchild;
        p->right = rchild;

        nodes_pointers[0] = p;
        _adjust_minHeap_HuffmanTree(nodes_pointers, 0, ASCIInum - 1 - i);
    }
    HT.root = nodes_pointers[0];
    free(nodes_pointers);
}