哈夫曼树的构造

每次把权值最小的两棵二叉树合并

例如：1 2 3 4 5

生成的哈夫曼树如下

我们利用最小堆来获得两个最小的值，并把新的节点插入堆中。也可以先排序，删除两个最小的，再把新值插入，但是效率没有最小堆高。

 1 typedef struct TreeNode *HuffmanTree;
 2 struct TreeNode{
 3  int weight;
 4  HuffmanTree Left,Right;
 5 }
 6 HuffmanTree Huffman(MinHeap H)
 7 {//假设H->Size个权值已经存在H->Elements[]->weight
 8    int i;
 9    HuffmanTree T;
10    BuildMinHeap(H);
11    for(i=1;i<H->Size;i++)
12    {
13       T=malloc(sizeof(struct TreeNode));
14       T->Left=DeleteMin(H);
15       T->Right=DeleteMin(H);
16       T->weight=T->Left->weight+T->Right->weight;
17       Insert(H,T);
18    }
19    T=DeleteMin(H);
20    return T;
21 }

View Code

整体复杂度为O(NlogN)。