最簡哈夫曼樹
哈夫曼樹（Huffman Tree）是一種二叉樹，用於數據壓縮和編碼。它是一種特殊的完全二叉樹，其每個節點的權值都不會小於其左子樹和右子樹的權值。在數據壓縮中，哈夫曼樹用於構建變長碼表，使得出現頻率高的字元或數據塊具有較短的編碼。
最簡哈夫曼樹是指一棵哈夫曼樹，其中沒有任何節點擁有相同的權值。在這種樹中，每個節點的權值都是唯一的，這意味著在構建樹的過程中，權值相同的節點不會被選中作為父節點。
構建最簡哈夫曼樹的步驟如下：
-
初始化：將所有數據項（字元或數據塊）作為葉節點，並給它們賦予相應的權值（頻率）。
-
排序：將這些葉節點按照權值從小到大排序。
-
組合：從排序後的列表中選擇兩個權值最小的節點，將它們合併為一個新的節點，並將它們的權值相加作為新節點的權值。這個新節點成為一棵二叉樹的根節點。
-
更新：從列表中移除剛才選擇的兩個節點，並將新節點添加到列表的末尾。
-
重複：重複步驟3和步驟4，直到列表中只剩下一個節點，即根節點。
這樣構建出來的哈夫曼樹就是最簡哈夫曼樹，因為在樹的構建過程中，沒有任何兩個節點擁有相同的權值。這種樹結構保證了樹的總權值最小，從而使得編碼效率最高。