資料結構——HuffmanTree

Huffman tree

基本術語

• 路徑和路徑長度
  • 路徑：在一棵樹中，從一個結點往下可以達到的孩子或子孫結點之間的通路。
  • 結點的路徑長度：從一個結點到另一個結點的路徑上分支的數目。
• 結點的權及帶權路徑長度
  • 結點的權:将樹中結點賦予一個有着某種含義的數值。
  • 結點的帶權路徑長度：從根結點到該結點之間的路徑長度與該結點的權的乘積。
• 樹的帶權路徑長度
  • 樹中所有葉子結點的帶權路徑長度之和。
• 赫夫曼樹（ Huffman tree ）
  • 帶權路徑長度達到最小的二叉樹即為赫夫曼樹。

在所有含 n 個葉子結點、并帶相同權值的二叉樹中，必存在一棵其帶權路徑長度取最小值的樹，稱為“最優二叉樹”。

構造 Huffman tree

基本思想：使權大的結點靠近根

• 根據給定的 n 個權值 {w1, w2, …, wn}，構造 n 棵二叉樹的集合F = {T1, T2, … , Tn}，其中每棵二叉樹中均隻含一個帶權值 為 wi 的根結點,其左、右子樹為空樹;
• 在 F 中選取其根結點的權值為最小的兩棵二叉樹，分别作為左、

右子樹構造一棵新的二叉樹，并置這棵新的二叉樹根結點的權值為其左、右子樹根結點的權值之和;

• 從F中删去這兩棵樹，同時加入

剛生成的新樹;

• 重複上述兩步，直至 F 中隻含一棵樹為止。

哈夫曼構造算法實作

一棵有 n 個葉子結點的Huffman樹有 2n-1 個結點

• 采用順序存儲結構---一維結構數組
• 結點類型定義

  typedef struct {
      ElemType elem;  // 結點值
      int weight;  // 權值
      int parent, lch, rch;
  }HTNode, *HuffmanTree;           

• 構造HuffmanTree
• • 輸入初始n個葉子結點：置HT[1..n]的weight值
  • 進行以下n-1次合并，依次産生HT[i]，i=n+1..2n-1：
    • 在HT[1..i-1]中選兩個未被選過的weight最小的兩個結點HT[s1]和HT[s2] (從parent = 0 的結點中選)
    • 修改HT[s1]和HT[s2]的parent值： parent=i
    • 置HT[i]：weight=HT[s1].weight + HT[s2].weight ,lch=s1, rch=s2

Status CreatHuffmanTree(HuffmanTree HT, int n){
    if (n <= 1)  // 結點數量不合法
        return ERROR;
    int m = 2 * n - 1;
    int i;
    int s1, s2;
    HT = new HTNode[m + 1];  // 0号單元未用，HT[m]表示根結點   
    for (i = 1;i <= m;++i) {
        HT[i].lch = 0;
        HT[i].rch = 0;
        HT[i].parent = 0;
    }
    for (i = 1;i <= n;++i)
        // 輸入權值
        cin >> HT[i].weight;
    for (i = n + 1;i <= m;++i) {
        // 構造Huffman樹
        Select(HT, i - 1, &s1, &s2);  // 在HT[k](1≤k≤i-1)中選擇兩個其雙親域為0, 且權值最小的結點, 并傳回它們在HT中的序号s1和s2
        if (s1 != 0 && s2 != 0) {
            HT[s1].parent = i;
            HT[s2].parent = i;  //表示從F中删除s1,s2
            HT[i].lch = s1;
            HT[i].rch = s2;  //s1,s2分别作為i的左右孩子
            HT[i].weight = HT[s1].weight + HT[s2].weight;  //i 的權值為左右孩子權值之和
        }
    }
    return OK;
}           

哈夫曼樹的應用

哈夫曼編碼

• 算法實作

  Status CreatHuffmanCode(HuffmanTree HT, HuffmanCode& HC, int n) {
      if (n <= 1)
          return ERROR;
      int start, i;
      int f = 0, c;
      HC = new char* [n + 1];
      char* cd = new char[n];
      cd[n - 1] = '0';
      for (i = 1; i <= n; ++i) {
          while (f != 0) {
              // 從葉子結點開始向上回溯，直到根結點
              start = n - 1;
              c = i;
              f = HT[i].parent;
              if (HT[f].lch == c) cd[start] = '0';
              else cd[start] = '1';
              c = f;
              f = HT[f].parent;
          }
          HC[i] = new char[n - start];  // 編碼數組
          strcpy(HC[i], &cd[start]);
      }
      delete cd;
      cd = NULL;
      return OK;
  }           

• 重要結論
  • 哈夫曼編碼是不等長編碼
  • 哈夫曼編碼是字首編碼，即任一字元的編碼都不是另一字元編碼的字首
  • 哈夫曼編碼樹中沒有度為1的結點。若葉子結點的個數為n，則哈夫曼編碼樹的結點總數為 2n-1
  • 發送過程：根據由哈夫曼樹得到的編碼表送出字元資料
  • 接收過程：按左0、右1的規定，從根結點走到一個葉結點，完成一個字元的譯碼。反複此過程，直到接收資料結束