哈夫曼樹定義
給定N個數值作為N個葉子結點的權值,構造一顆二叉樹,若該樹的帶權路徑長度達到最小,稱這樣的二叉樹為最優二叉樹,也叫哈夫曼樹。
哈夫曼樹是帶權路徑長度最小的樹,權值越大的節點距離根節點越近。
帶權路徑:根結點到第L層結點路徑的長度,長度為 L-1。
樹的帶權路徑長度:樹的所有葉子節點帶權路徑總和,簡稱 WPL(Weighted Path Length of Tree)。
Kotlin 中哈夫曼樹如何實現
1. 實現的流程
1。1 將陣列中所有元素建立為若干二叉樹
1。2 排序
1。3 取出最小權值的兩個二叉樹 並 建立新的二叉樹
1。4 把兩個最小權值的子樹從集合中移除 並 將新二叉樹放入集合
1。5 迴圈處理 1。2 - 1。4,直到集合的 size = 1 時停止
2. 實現的程式碼
/** * 將陣列轉換為赫夫曼樹 * */ fun createHuffmanTree(arr:IntArray):Node{ // 將陣列中所有元素建立為若干二叉樹 var nodeList:ArrayList
3. 賦值呼叫轉換方法
// 定義任意陣列var arr:IntArray = intArrayOf(3,7,8,29,5,11,23,14)// 轉換陣列 並 獲取哈夫曼樹的根節點var node:Node = createHuffmanTree(arr)Log。e(“==”, “根節點權值 = ${node。value}”)
執行結果
國際慣例
貼上完整原始碼
/** * @des 哈夫曼樹 * @author liyongli 20190222 * */class HuffmanTreeActivity : AppCompatActivity() { override fun onCreate(savedInstanceState: Bundle?) { super。onCreate(savedInstanceState) setContentView(R。layout。activity_huffman_tree) // 定義任意陣列 var arr:IntArray = intArrayOf(3,7,8,29,5,11,23,14) // 轉換陣列 並 獲取哈夫曼樹的根節點 var node:Node = createHuffmanTree(arr) Log。e(“”, “=============================”) Log。e(“”, “根節點權值為: ${node。value}”) Log。e(“”, “=============================”) } /** * 將陣列轉換為赫夫曼樹 * */ fun createHuffmanTree(arr:IntArray):Node{ // 將陣列中所有元素建立為若干二叉樹 var nodeList:ArrayList
本篇到此完結,更多Kotlin與資料結構
原創
內容持續更新中~
期待您點選
關注
或點選頭像瀏覽更多
移動端開發技術乾貨
!