Kotlin遇見數據結構丨說說如何實現哈夫曼樹

給定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 = 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}")

運行結果

國際慣例

貼上完整源碼

/** * @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與數據結構原創內容持續更新中~

期待您點擊關注或點擊頭像瀏覽更多移動端開發技術乾貨！