1. 引入
例：將百分制的考試成績轉(zhuǎn)換為五分制成績停做。
如何根據(jù)不同的查找頻率構(gòu)造更有效的搜索樹
2. 哈夫曼樹的定義
3. 哈夫曼樹的構(gòu)造
將權(quán)值從小到大進(jìn)行排序晤愧，每次把權(quán)值最小的兩顆二叉樹合并形成一個新的二叉樹，新二叉樹權(quán)值為兩個合并二叉樹權(quán)值的和蛉腌。
typedef struct TreeNode *HuffmanTree;
struct TreeNode{
int Weight;
HuffmanTree Left;
HuffmanTree Right;
};
// 假設(shè)H->Size個權(quán)值已經(jīng)存在H->Elements[]->Weight里
HuffmanTree Huffman( MinHeap H )
{
int i;
HuffmanTree T;
BuildMinHeap(H); // 將H->Elements[]按權(quán)值調(diào)整為最小堆
for(i = 1; i < H->Size; i++)
{
T = (HuffmanTree)malloc(sizeof(struct TreeNode)); // 建立新結(jié)點(diǎn)
T->Left = DeleteMin(H); // 從最小堆中刪除一個結(jié)點(diǎn)养涮， 作為新T的左子結(jié)點(diǎn)
T->Right = DeleteMin(H); // 從最小堆中刪除一個結(jié)點(diǎn)，作為新T的右子結(jié)點(diǎn)
T->Weight = T->Left->Weight + T->Right->Weight; // 計(jì)算新權(quán)值
Insert(H, T); // 將新T插入最小堆中
}
T = DeleteMin(H); // T為根結(jié)點(diǎn)【有一點(diǎn)不理解的：返回根結(jié)點(diǎn)后這個Huffman樹是否已經(jīng)構(gòu)造好了眉抬，怎么構(gòu)造的？通過堆懈凹？】
return T;
}
整體時間復(fù)雜度O(NlogN)
4.哈夫曼樹的特點(diǎn)
5. 哈夫曼編碼
用Huffman構(gòu)造編碼二叉樹：
