[JAVA]Huffman Tree : 建立樹並取得帶權路徑長度/前序遍歷

資料結構 Huffman樹

1、介紹
(1) 給定n 個權值作為n 個葉子結點,構造一棵二叉樹,若該樹的帶權路徑長度(wpl)達到最小,稱這樣的二叉樹為最優二叉樹,也稱為哈夫曼樹(Huffman Tree), 還有的書翻譯為霍夫曼樹。
(2) 赫夫曼樹是帶權路徑長度最短的樹,權值較大的結點離根較近
2、重要概念和舉例說明
(1) 路徑和路徑長度:在一棵樹中,從一個結點往下可以達到的孩子或孫子結點之間的通路,稱為路徑。通路
中分支的數目稱為路徑長度。若規定根結點的層數為1,則從根結點到第L 層結點的路徑長度為L-1
(2) 結點的權及帶權路徑長度:若將樹中結點賦給一個有著某種含義的數值,則這個數值稱為該結點的權。結點的帶權路徑長度為:從根結點到該結點之間的路徑長度與該結點的權的乘積
(3) 樹的帶權路徑長度:樹的帶權路徑長度規定為所有葉子結點的帶權路徑長度之和,記為WPL(weighted path length) ,權值越大的結點離根結點越近的二叉樹才是最優二叉樹。

...繼續閱讀 »

[JAVA]基數排序法(Radix sort)

需要二維陣列:第一維用來表示第幾個桶,第二維用來儲存符合x位數基數的值
需要一維陣列:用來表示二維陣列的每個桶,儲存幾個值
每個桶的空間:以待排序陣列長度為基準
步驟:1. 先找出最大值,並得出最大值位數 => 基數排序進行的次數,假設最大值為百位數,那基數排序會排序3次
2. 求出個位數基數,將值依序放入二維陣列中
3. 紀錄每個桶放入幾個數 => 入一維陣列
4. 取出二維陣列的值放回原待排序陣列,並清空二維陣列、一維陣列做為下一次排序使用

...繼續閱讀 »