当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<Node> = 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<Node> = 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与数据结构原创内容持续更新中~
期待您点击关注或点击头像浏览更多移动端开发技术干货！
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2019.02.22 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
