一、什麼是哈夫曼樹（Huffman Tree）

如果我們將百分制的考試成績轉換成五分制的成績，我們可以使用如下所示的程式：

/* c語言實現 */    if( score < 60 )  grade =1;  else if( score < 70 ) grade =2;  else if( score < 80 ) grade =3;  else if( score < 90 ) grade =4;  else grade =5;

通過上述的程式碼，我們可以構造出如下圖所示的判定樹：

如果在上述五分制的成績中，我們考慮學生成績的分布的概率，如下圖所示：

通過學生成績分布的概率和上述的判定樹，我們可以得到學生成績的查找效率為：
[ 0.05× 1+0.15 ×2+0.4× 3+0.3 ×4+0.1× 4 = 3.15 ]
從學生成績分布的概率中，可以看出70-79和80-89分布中的學生較多，然而他們的查找效率確是較低的，因此我們可以按照如下方式修改程式碼和判定樹：

/* c語言實現 */    if( score < 80 )  {    if( score < 70 );     if( score < 60 ) {       grade =1;     } else grade = 2;    else grad=3;  }  else if( score < 90 ) grade =4;  else grade =5;

通過此次修改，學生成績的查找效率為：
[ 0.05× 3+0.15 ×3+0.4× 2+0.3 ×2+0.1× 2 = 2.2 ]
通過上述的例子，我們可以思考一個問題：如何根據結點不同的查找頻率構造更有效的搜索樹？

1.1 哈夫曼樹的定義

帶權路徑長度（WPL）：設二叉樹有n個葉子結點，每個葉子結點帶有權值(w_k)，從根節點到每個葉子結點的長度為(l_k)，則每個葉子結點的帶權路徑長度之和就是：(WPL = sum_{k=1}^nw_kl_k)

最優二叉樹或哈夫曼樹：WPL最小的二叉樹

例：有五個葉子結點，它們的權值為 {1, 2, 3, 4, 5} ，用此權值序列可以構造出形狀不同的多個二叉樹。

二、哈夫曼樹的構造

每次把權值最小的兩顆二叉樹合併

/* c語言實現 */    typedef struct TreeNode *HuffmanTree;  struct TreeNode{    int Weight;    HuffmanTree Left, Right;  }    HuffmanTree Huffman( MinHeap H )  {    // 假設H->Size個權值已經存在H->Elements[]->Weight里    int i; HuffmanTree T;    BuildMinHeap(H); // 將H->Elements[]按權值調整為最小堆    for (i = 1; i < H->Size; i++)    {      // 做H->Size-1次合併      T = malloc(sizeof(struct TreeNode)); // 建立新結點      T->Left = DeleteMin(H); // 從最小堆中刪除一個結點，作為新T的左子結點      T->Right = DeleteMin(H); // 從最小堆中刪除一個結點，作為新T的右子結點      T->Weight = T->Left->Weight+T->Right->Weight; // 計算新權值      Insert(H, T); // 將新T插入最小堆    }    T = DeleteMin(H);    return T;  }

# python語言實現    # 節點類  class Node(object):      def __init__(self, name=None, value=None):          self._name = name          self._value = value          self._left = None          self._right = None      # 哈夫曼樹類  class HuffmanTree(object):        # 根據Huffman樹的思想：以葉子節點為基礎，反向建立Huffman樹      def __init__(self, char_weights):          self.a = [Node(part[0], part[1]) for part in char_weights]  # 根據輸入的字元及其頻數生成葉子節點          while len(self.a) != 1:              self.a.sort(key=lambda node: node._value, reverse=True)              c = Node(value=(self.a[-1]._value + self.a[-2]._value))              c._left = self.a.pop(-1)              c._right = self.a.pop(-1)              self.a.append(c)          self.root = self.a[0]          self.b = list(range(10))  # self.b用於保存每個葉子節點的Haffuman編碼,range的值只需要不小於樹的深度就行        # 用遞歸的思想生成編碼      def pre(self, tree, length):          node = tree          if (not node):              return          elif node._name:              print(node._name + '的編碼為:')              for i in range(length):                  print(self.b[i])              print()              return          self.b[length] = 0          self.pre(node._left, length + 1)          self.b[length] = 1          self.pre(node._right, length + 1)        # 生成哈夫曼編碼      def get_code(self):          self.pre(self.root, 0)      if __name__ == '__main__':      # 輸入的是字元及其頻數      char_weights = [('a', 5), ('b', 4), ('c', 10), ('d', 8), ('f', 15), ('g', 2)]      tree = HuffmanTree(char_weights)      tree.get_code()

上述過程的時間複雜度為：O(N logN)