Kotlin遇見資料結構丨說說如何實現哈夫曼樹

Kotlin遇見資料結構丨說說如何實現哈夫曼樹

哈夫曼樹定義

給定N個數值作為N個葉子結點的權值,構造一顆二叉樹,若該樹的帶權路徑長度達到最小,稱這樣的二叉樹為最優二叉樹,也叫哈夫曼樹。

哈夫曼樹是帶權路徑長度最小的樹,權值越大的節點距離根節點越近。

帶權路徑:根結點到第L層結點路徑的長度,長度為 L-1。

樹的帶權路徑長度:樹的所有葉子節點帶權路徑總和,簡稱 WPL(Weighted Path Length of Tree)。

Kotlin遇見資料結構丨說說如何實現哈夫曼樹

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 = arrayListOf() for(value:Int in arr) { nodeList。add(Node(value = value)) } // 迴圈處理 while (nodeList。size > 1){ // 排序 Collections。sort(nodeList) // 取出最小權值的兩個二叉樹 並 建立新的二叉樹 var leftNode:Node = nodeList。get(nodeList。size-1) var righeNode:Node = nodeList。get(nodeList。size-2) var parentNode:Node = Node(value = (leftNode。value!! + righeNode。value!!), leftNode = leftNode, rightNode = righeNode) // 把兩個子樹從集合中移除 並 將新二叉樹放入集合 nodeList。remove(leftNode) nodeList。remove(righeNode) nodeList。add(parentNode) } // 經過不斷處理,最終其實只剩一個 Node 物件,也就是根節點 return nodeList。get(0) }

3. 賦值呼叫轉換方法

// 定義任意陣列var arr:IntArray = intArrayOf(3,7,8,29,5,11,23,14)// 轉換陣列 並 獲取哈夫曼樹的根節點var node:Node = createHuffmanTree(arr)Log。e(“==”, “根節點權值 = ${node。value}”)

執行結果

Kotlin遇見資料結構丨說說如何實現哈夫曼樹

國際慣例

貼上完整原始碼

/** * @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 = arrayListOf() for(value:Int in arr) { nodeList。add(Node(value = value)) } // 迴圈處理 while (nodeList。size > 1){ // 排序 Collections。sort(nodeList) // 取出最小權值的兩個二叉樹 並 建立新的二叉樹 var leftNode:Node = nodeList。get(nodeList。size-1) var righeNode:Node = nodeList。get(nodeList。size-2) var parentNode:Node = Node(value = (leftNode。value!! + righeNode。value!!), leftNode = leftNode, rightNode = righeNode) // 把兩個子樹從集合中移除 並 將新二叉樹放入集合 nodeList。remove(leftNode) nodeList。remove(righeNode) nodeList。add(parentNode) } // 經過不斷處理,最終其實只剩一個 Node 物件,也就是根節點 return nodeList。get(0) }}

本篇到此完結,更多Kotlin與資料結構

原創

內容持續更新中~

期待您點選

關注

或點選頭像瀏覽更多

移動端開發技術乾貨

Kotlin遇見資料結構丨說說如何實現哈夫曼樹