赫夫曼樹（huffman tree）又稱為最優樹，是一類帶權路徑長度最短的樹。本文僅讨論最優二叉樹。
樹的路徑長度是指從樹根到樹中其餘各個結點的路徑長度之和。對具有n個結點的二叉樹而言，完全二叉樹具有最短的樹的路徑長度。
若在二叉樹中，樹葉結點帶有權值，則有：結點的帶權路徑長度定義為從樹根到該結點之間的路徑長度與該結點上所帶權值之積。
若樹中有n個樹葉結點，且每個樹葉結點均帶有權值，則有：樹的帶權路徑長度定義為樹中所有樹葉結點的帶權路徑長度之和，可記為：
有時，也将樹的路徑長度稱為内路徑長度，而将樹的帶權路徑長度稱為樹的外路徑長度。
構造最優樹的赫夫曼算法：
①根據給定的n個權值，構成n棵二叉樹的集合f，其中每棵樹中隻有一個帶有權值的根結點，其左右子樹均為空樹。
②在f中選取兩棵根結點的權值最小的樹，并以它們作為左右子樹構造一棵新的二叉樹，且置新的二叉樹根結點的權值為其左、右子樹上根結點的權值之和。
③在f中删除這兩棵樹，同時将新得到的二叉樹加入f中。
重複②③步驟，知道f隻含一棵樹而知。這棵樹便是所求的的赫夫曼樹。
具有n個樹葉結點的赫夫曼（二叉）樹總的結點個數為2n-1。由于樹中的結點個數是确定的，是以，選擇靜态樹表作為存儲結構，結合即将讨論的赫夫曼編碼，最終選擇靜态三叉樹表作為建立赫夫曼樹的存儲結構。靜态三叉樹表結點結構如下：
huffmantree類聲明如下：
huffmantree類實作如下：
赫夫曼樹的一個重要應用是在通信中構造最優的字首編碼，進而使得電文長度達到最短。
通常有兩類二進制編碼：
①等長編碼：編碼的二進制長度取決于電文中出現的字元個數。
②不等長編碼：各字元的二進制編碼長度不等。它的好處是可以使傳送電文的字元串總長度盡可能的短。
通常各個字元在電文中出現的次數是不相同的，若對出現次數較多的字元采用盡可能短的編碼，則傳送電文的總長便可減少。
在實用的不等長編碼中，任一一個字元的編碼都不能是另一個字元編碼的字首，這種編碼成為字首編碼。
赫夫曼編碼表的結點結構定義如下：
赫夫曼編碼類實作如下：
主函數如下：
程式輸入：
程式輸出：