Kotlin实现的二叉树数据结构

二叉树，树，二叉，倒树

小的key在左边，大的数在右边。

每个节点下可以有一个/两个节点

那就看看我们怎么实现这个数据结构吧

设计

一般来说，我们在写一个数据结构之前，先有思想，然后设计API。

BinaryTree 类

节点Node类

API设计

也就是BinaryTree的API设计，暴露什么方法出去。

• put(key:K,value:V) 添加数据
• delete(key:K):Node<K,V>? 删除节点
• get(key:K):Node<K,V>? 查找某个节点，有可能为null
• minKey():Node<K,V>? 查找key最小的节点
• maxKey():Node<K,V>? 查找key最大值的节点
• getDepthSize() 获取最大深度
• size() 节点数量
• 各种遍历方式

添加数据

/**
     * 添加节点
     */
    fun put(key: K, value: V) {
        root = put(root, key, value)
    }

    /**
     * 在某个节点下添加内容
     */
    private fun put(node: Node<K, V>?, key: K, value: V): Node<K, V> {
        if (node == null) {
            size++
            return Node<K, V>(key, value, null, null)
        }
        //判断在左边还是右边还是当前的位置
        //如果是当前的位置，那么就改值
        val cmp = key.compareTo(node.key)
        when {
            cmp < 0 -> {
                //在左边，递归调用，如果left为null的话，直接就返回了node了
                node.left = put(node.left, key, value)
            }
            cmp > 0 -> {
                //在右边
                node.right = put(node.right, key, value)
            }
            else -> {
                node.value = value
            }
        }
        return node
    }

要点是： - 有不有root - 放在左边还是右边 - 递归思想 - size要记得更新

添加的逻辑已经写在注释里了，脑补一下图哈。

查找节点

查找节点的时候，我们有key，还有root

这个好办，我们对比一下在左边还是右边即可，如果key一样，就是了。如果没有一样的，那就返回null了。

代码实现：

    /**
     * 获取内容
     */
    fun get(key: K): Node<K, V>? {
        return get(root, key)
    }

    /**
     * 在某个节点下获取节点
     */
    private fun get(node: Node<K, V>?, key: K): Node<K, V>? {
        if (node == null) {
            return null
        }
        //判断左右还是自己
        val cmp = key.compareTo(node.key)
        return when {
            cmp < 0 -> {
                //取左边
                get(node.left, key)
            }
            cmp > 0 -> {
                //取右边
                get(node.right, key)
            }
            else -> {
                //自己
                node
            }
        }
    }

删除数据

删除数据的话会比较复杂一点，也是递归思想。难点的话应该是在删除中间某个节点，然后得拼接回去。

思考之前可以先想一下case，传入的参数有key，你手上有的是root。怎么样去查找呢？找到以后还要删除，删除以后还要拼接。

设当前元素=要删除的元素

• 除了删除root，都是有父节点的，删除的方式就是通过父节点置空目标节点
• 如果当前元素没有左节点，没有右节点，直接删除，也就是直接通过父节点置空（left/right = null）
• 如果当前元素有左节点，没有右节点，那么就将当前节点的左节点链接到父节点（left/right=target.left）
• 如果当前节点有右节点，没有左节点的，那么就将当前的节点右节点链接到父节点（left/right=target.right）
• 如果当前元素有左节点和右节点，那么就拿到右节点的最小值替换当前节点，替换包括着链接当前节点的左右节点以及拼接到父节点。
• size要进行更新

通过递归的实现方式如下：

 /**
     * 删除节点
     */
    fun delete(key: K): Node<K, V>? {
        return delete(root, key)
    }

    private fun delete(node: Node<K, V>?, key: K): Node<K, V>? {
        //如果节点为null，直接返回null
        if (node == null) {
            return null
        }
        val cmp = key.compareTo(node.key)
        when {
            cmp < 0 -> {
                //删除左边
                node.left = delete(node.left, key)
            }
            cmp > 0 -> {
                node.right = delete(node.right, key)
            }
            else -> {
                size--
                //找到了对应点了
                //否则，先找到key对应的节点
                //否则进行删除操作

                //必须先判断右边，因为如果只有左边的话，那么把左边拿到去链接即可
                if (node.right == null) {
                    //如果右则为null，直接链接左边
                    return node.left
                }
                //如果右边不为null，左边为null,那么返回去链接上即可
                if (node.left == null) {
                    return node.right
                }
                //到这里,左右都不为null
                //1、找到目标节点的右则最小Key节点
                var miniNode = node.right
                while (miniNode?.left != null) {
                    miniNode = miniNode.left
                }
                //到这里就找到了目标节点右则节点的最小key的节点了

                //2、以目标节点右侧最小节点为接点
                //3、接点的右则为目标节点的右侧
                //4、接点的左侧为目标节点的左侧
                miniNode?.left = node.left
                miniNode?.right = node.right
                //5、接点为目标节点父节点的左侧
                //6、删除目标节点右侧最小节点
                var miniFather = node.right
                while (miniFather?.left != null) {
                    if (miniFather.left?.left == null) {
                        miniFather.left = null
                    } else {
                        miniFather = miniFather.left
                    }
                }
                return miniNode
            }
        }
        return null
    }

获取最大key的节点

最左侧的，是不是是小的呀？

    /**
     * 查找最小值key值的数据
     */
    fun miniKeyNode(): Node<K, V>? {
        //最小key值就是最左边的值
        if (root == null) {
            return null
        }
        if (root?.left == null && root?.right == null) {
            return root
        }
        var miniNode = root!!.left
        while (miniNode?.left != null) {
            miniNode = miniNode.left
        }
        return miniNode
    }

另外一种方法则是通过递归的方式查找

 /**
     * 查找最小的节点
     */
    fun miniNode(): Node<K, V>? {
        return findMiniNode(root)
    }

    /**
     * 查找当前节点以下最小key的节点
     */
    private fun findMiniNode(node: Node<K, V>?): Node<K, V>? {
        if (node == null) {
            return null
        }
        if (node.left !== null) {
            return findMiniNode(node.left)
        }
        return node
    }

查找最大key值的节点

思想跟查找最小key值节点是一样的

  /**
     * 找最大的key值
     */
    fun maxKeyNode(): Node<K, V>? {
        if (root == null) {
            return null
        }
        if (root?.left == null && root?.right == null) {
            return root
        }
        var maxKeyNode = root?.right
        while (maxKeyNode?.right != null) {
            maxKeyNode = maxKeyNode.right
        }
        return maxKeyNode
    }

递归的实现方式

    fun maxNode(): Node<K, V>? {
        return findMaxNode(root)
    }

    private fun findMaxNode(node: Node<K, V>?): Node<K, V>? {
        if (node == null) {
            return null
        }
        if (node.right != null) {
            return findMaxNode(node.right)
        }
        return node
    }

遍历

数据结构一般都提供遍历方式吧

在二叉树中，遍历方式：

• 前序遍历
• 中须遍历
• 后序遍历
• 层遍历

前序遍历

前序遍历主是先遍root，然后遍历左边，再遍历右边

代码如下：

 /**
     * 获取到Key列表:前序遍历方式，先遍历root节点，再遍历左节点，再表呢右节点
     */
    fun getPreKeyList(): List<K> {
        val keys = ArrayList<K>()
        preKeyList(root, keys)
        return keys
    }

    private fun preKeyList(node: Node<K, V>?, keys: java.util.ArrayList<K>) {
        //如果节点为null，那么就返回
        if (node == null) {
            return
        }
        //开始添加key
        keys.add(node.key)
        if (node.left != null) {
            preKeyList(node.left, keys)
        }
        //遍历右边
        if (node.right != null) {
            preKeyList(node.right, keys)
        }
    }

中序遍历

中序嘛，也就是root在中间。先遍历左边的，再到root,再到右边的。

代码如下实现：

    fun getMidKeyList(): List<K> {
        val keys = ArrayList<K>()
        midKeyList(root, keys)
        return keys
    }

    private fun midKeyList(node: Node<K, V>?, keys: java.util.ArrayList<K>) {
        if (node == null) {
            return
        }
        //先遍历左边的
        if (node.left != null) {
            midKeyList(node.left, keys)
        }
        //中间
        keys.add(node.key)
        //右边
        if (node.right != null) {
            midKeyList(node.right, keys)
        }
    }

后序遍历

会了前面两个，相信就会后序遍历了吧。

后序遍历，先遍历左边的，再到右边的，再到root

代码实现：

  fun getEndKeyList(): List<K> {
        val keys = ArrayList<K>()
        endKeyList(root, keys)
        return keys
    }

    private fun endKeyList(node: Node<K, V>?, keys: java.util.ArrayList<K>) {
        if (node == null) {
            return
        }
        if (node.left != null) {
            endKeyList(node.left, keys)
        }
        if (node.right != null) {
            endKeyList(node.right, keys)
        }
        keys.add(node.key)
    }

层遍历

层遍历的思想很简单，从第上往下，第一层开始，往下开始遍历。

先遍历当前层，然后如果当前层有左右的话，添加到一个集合/队列里，然后遍历队列里的内容，添加到集合中，再判断队列里的所有Item是否有左右，有的话继续添加到新的队列中，继续如此操作即可。

代码实现：

  fun getLayerKeyList(): List<K> {
        val keys = ArrayList<K>()
        if (root != null) {
            val layItems = ArrayList<Node<K, V>?>()
            layItems.add(root)
            layerKeyList(layItems, keys)
        }
        return keys
    }

    private fun layerKeyList(layItems: ArrayList<Node<K, V>?>, keys: java.util.ArrayList<K>) {
        val nextItems = ArrayList<Node<K, V>?>()
        layItems.forEach {
            if (it == null) {
                return
            }
            //添加到集合里
            keys.add(it.key)
            //如果有左边
            if (it.left != null) {
                nextItems.add(it.left)
            }
            if (it.right != null) {
                nextItems.add(it.right)
            }
        }
        if (nextItems.size > 0) {
            layerKeyList(nextItems, keys)
        }
        layItems.clear()
    }

获取最大深度

树结构的最大深度，指的就是层数，也就是从上往下数。

代码也不难，很简单。

    fun getDepthSize(): Int {
        return computeDepthSize(root)
    }

    private fun computeDepthSize(node: Node<K, V>?): Int {
        if (node == null) {
            return 0
        }
        var leftDepth = 0
        if (node.left != null) {
            leftDepth = computeDepthSize(node.left)
        }

        var rightDepth = 0
        if (node.right != null) {
            rightDepth = computeDepthSize(node.right)
        }

        //说明没有子节点了，算自己一层吧
        if (leftDepth == 0 && rightDepth == 0) {
            return 1
        }

        //左边大，返回左边的
        if (leftDepth > rightDepth) {
            return leftDepth + 1
        }

        //右边大返回右边的，等于随便返回一个都行的
        if (leftDepth <= rightDepth) {
            return rightDepth + 1
        }

        return 0
    }

测试

测试数据

测试代码：

fun main() {
    val binaryTree = BinaryTree<Int, String>()
    binaryTree.put(10, "张三")
    binaryTree.put(4, "李四")
    binaryTree.put(23, "王五")
    binaryTree.put(24, "赵六")
    binaryTree.put(20, "田七")
    binaryTree.put(1, "王八")
    binaryTree.put(50, "天八")
    binaryTree.put(0, "墨十")
    //获取
    val result = binaryTree.get(23)
    println(result)
    //binaryTree.delete(23)
    //val deleteResult = binaryTree.get(23)
    //println(deleteResult)
    //最key值
    val maxKeyNode = binaryTree.maxKeyNode()
    val miniKeyNode = binaryTree.miniKeyNode()
    println("maxKeyNode==> $maxKeyNode")
    println("miniKeyNode==> $miniKeyNode")
    //遍历
    val preKeySet = binaryTree.getLayerKeyList()
    for (i in preKeySet) {
        println("key == > $i")
    }
    //深度
    val depthSize = binaryTree.getDepthSize()
    println("depthSize == > $depthSize")
}

输出：

key is == > 23 value is == > 王五
maxKeyNode==> key is == > 50 value is == > 天八
miniKeyNode==> key is == > 0 value is == > 墨十
key == > 10
key == > 4
key == > 23
key == > 1
key == > 20
key == > 24
key == > 0
key == > 50
depthSize == > 4

Process finished with exit code 0

以上代码实现可能与其他教程有所不同，实现方式是不唯一的。但是思想是一样的。

算法跟编程语言无关，只是思想，不同的编程语言，不同的写法也是可以实现的，效果一样即可。