最優二叉樹

最優二叉樹概念

．樹的路徑長度
　　樹的路徑長度是從樹根到樹中每一結點的路徑長度之和在結點數目相同的二叉樹中完全二叉樹的路徑長度最短

．樹的帶權路徑長度(Weighted Path Length of Tree簡記為WPL)
　　結點的權在一些應用中賦予樹中結點的一個有某種意義的實數
　　結點的帶權路徑長度結點到樹根之間的路徑長度與該結點上權的乘積
　　樹的帶權路徑長度(Weighted Path Length of Tree)定義為樹中所有葉結點的帶權路徑長度之和通常記為 
                                           
　其中     
　　n表示葉子結點的數目
　　w_i和l_i分別表示葉結點k_i的權值和根到結點ki之間的路徑長度
　　樹的帶權路徑長度亦稱為樹的代價

．最優二叉樹或哈夫曼樹
　　在權為wlw…wn的n個葉子所構成的所有二叉樹中帶權路徑長度最小(即代價最小)的二叉樹稱為最優二叉樹或哈夫曼樹
　【例】給定個葉子結點abc和d分別帶權和構造如下圖所示的三棵二叉樹(還有許多棵)它們的帶權路徑長度分別為
        (a)WPL=*+*+*+*=
        (b)WPL=*+*+*+*=
        (c)WPL=*+*+*+*=
　其中(c)樹的WPL最小可以驗證它就是哈夫曼樹

　注意
　　① 葉子上的權值均相同時完全二叉樹一定是最優二叉樹否則完全二叉樹不一定是最優二叉樹
　　② 最優二叉樹中權越大的葉子離根越近
　　③ 最優二叉樹的形態不唯一WPL最小

構造最優二叉樹

．哈夫曼算法
　　哈夫曼首先給出了對於給定的葉子數目及其權值構造最優二叉樹的方法故稱其為哈夫曼算法其基本思想是
　　()根據給定的n個權值w_lw…wn構成n棵二叉樹的森林F={TT…T_n}其中每棵二叉樹T_i中都只有一個權值為w_i的根結點其左右子樹均空
　　()在森林F中選出兩棵根結點權值最小的樹(當這樣的樹不止兩棵樹時可以從中任選兩棵)將這兩棵樹合並成一棵新樹為了保證新樹仍是二叉樹需要增加一個新結點作為新樹的根並將所選的兩棵樹的根分別作為新根的左右孩子(誰左誰右無關緊要)將這兩個孩子的權值之和作為新樹根的權值
　　()對新的森林F重復()直到森林F中只剩下一棵樹為止這棵樹便是哈夫曼樹
　用哈夫曼算法構造哈夫曼樹的過程見【動畫演示】
　注意
　　① 初始森林中的n棵二叉樹每棵樹有一個孤立的結點它們既是根又是葉子
　　② n個葉子的哈夫曼樹要經過n次合並產生n個新結點最終求得的哈夫曼樹中共有n個結點
　　③ 哈夫曼樹是嚴格的二叉樹沒有度數為的分支結點
  
．哈夫曼樹的存儲結構及哈夫曼算法的實現
（） 哈夫曼樹的存儲結構
　　用一個大小為n的向量來存儲哈夫曼樹中的結點其存儲結構為
  #define n //葉子數目
  #define m *n//樹中結點總數
  typedef struct { //結點類型
      float weight //權值不妨設權值均大於零
      int lchildrchildparent //左右孩子及雙親指針
    }HTNode
  typedef HTNode HuffmanTree[m] //HuffmanTree是向量類型
　注意
　　因為C語言數組的下界為故用表示空指針樹中某結點的lchildrchild和parent不等於時它們分別是該結點的左右孩子和雙親結點在向量中的下標
　　這裡設置parent域有兩個作用其一是使查找某結點的雙親變得簡單其二是可通過判定parent的值是否為來區分根與非根結點

（）哈夫曼算法的簡要描述
　　在上述存儲結構上實現的哈夫曼算法可大致描述為(設T的類型為HuffmanTree)
　()初始化
　　將T[．．m]中n個結點裡的三個指針均置為空(即置為)權值置為
　()輸人
　　讀人n個葉子的權值存於向量的前n個分量(即T[．．n])中它們是初始森林中n個孤立的根結點上的權值
　()合並
　　對森林中的樹共進行n次合並所產生的新結點依次放人向量T的第i個分量中(n≤i≤m)每次合並分兩步
　　　①在當前森林T[．．i]的所有結點中選取權最小和次小的兩個根結點[p]和T[p]作為合並對象這裡≤pp≤i
　　　② 將根為T[p]和T[p]的兩棵樹作為左右子樹合並為一棵新的樹新樹的根是新結點T[i]具體操作
　　將T[p]和T[p]的parent置為i
　　將T[i]的lchild和rchild分別置為p和p
　　新結點T[i]的權值置為T[p]和T[p]的權值之和
　注意
　　合並後T[pl]和T[p]在當前森林中已不再是根因為它們的雙親指針均已指向了T[i]所以下一次合並時不會被選中為合並對象
哈夫曼算法模擬演示過程【參見動畫模擬】

（）哈夫曼算法的求精
  void CreateHuffmanTree(HuffmanTree T)
    {//構造哈夫曼樹T[m]為其根結點
      int ipp
      InitHuffmanTree(T) //將T初始化
      InputWeight(T) //輸入葉子權值至T[．．n]的weight域
      for(i=ni<mi++){//共進行n次合並新結點依次存於T[i]中
          SelectMin(Ti&p&p)
          //在T[．．i]中選擇兩個權最小的根結點其序號分別為p和p
          T[p]parent=T[p]parent=i
          TIi]child=p //最小權的根結點是新結點的左孩子
          T[j]rchild=p //次小權的根結點是新結點的右孩子
          T[i]weight=T[p]weight+T[p]weight
        } // end for
    }
上述算法中調用的三個函數【參見練習】
【例】以個權值為例執行CreateHuffmanTree求最優二叉樹的過程【參見動畫模擬】

 

From:http://tw.wingwit.com/Article/program/sjjg/201311/23014.html