哈夫曼樹定義
給定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與數據結構原創內容持續更新中~
期待您點擊關注或點擊頭像瀏覽更多移動端開發技術乾貨！
分享到:
