数据结构 | 二分搜索树及它的各种操作(kotlin实现)

简介: 在开始之前,应该先讲一下什么是二叉树。

什么是二叉树?

  • 链表一样,同样也是动态数据结构
  • 二叉树具有唯一的根节点
class Node<E> {
    var e: E? = null
    var left: Node<E>? = null
    var right: Node<E>? = null
}
  • 每个节点最多有两个节点
  • 二叉树具有天然递归结构
  • 每个节点的左子树和右字数也是二叉树
  • 二叉树不一定是满的

二叉树

一个null树也叫做二叉树,就算只有一个根节点,也是二叉树

左斜树&右斜树

二叉树中每个节点方向相同,全部节点只有左子节点的称为左斜树,只有右子节点的称为右斜树。

满二叉树

除最后一层无任何子节点外,每一层上的所有结点都有两个子结点的二叉树。

完全二叉树

完全二叉树是由满二叉树而引出来的,若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数(即1~h-1层为一个满二叉树),第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。

什么是二分搜索树(Binary Search Tree)?\

  • 二分搜索树是二叉树;
  • 二分搜索树的每个节点的值大于其左子树所有节点的值,小于其右子树的所有节点的值,简称 左小右大
  • 每一颗字数也是二分搜索树;
  • 存储的元素必须有可比较性;

二叉树的遍历

前序遍历

先遍历 节点e,再遍历左子树,最后遍历右子树

中序遍历

先遍历 左子树,再遍历节点e,最后遍历右子树

后序遍历

先遍历左子树,再遍历右子树,最后遍历节点e

举个栗子🌰

前序遍历

28,20,17,15,25,30,29,35

中序遍历

15,17,20,25,28,29,30,35

后序遍历

15,17,25,20,29,35,30,28

代码实现

这里实现一些比较经典的案例,比较简单的如前序遍历,中序遍历,后序遍历,使用递归,栈,队列 都可以简单实现。

二叉树的插入

 private fun add(node: Node<E>?, e: E): Node<E> {
        if (node == null) {
            ++size
            return Node(e)
        }
        if (node.e > e)
            node.left = add(node.left, e)
        else if (node.e < e)
            node.right = add(node.right, e)
        return node
    }

整体思路也非常简单,按照前序遍历的方式,我们先遍历左子树,然后再遍历右子树,通过递归的实现,非常容易。

二叉树的删除

   /**
     * 删除以node 为根的二分搜索树 值为e的节点
     * 返回 删除节点后新的二分搜索树的根
     * */
    private fun remove(node: Node<E>?, e: E): Node<E>? {
        //健壮性判断
        if (node == null) return node
        return when {
            //遍历左孩子
            e < node.e -> {
                node.left=remove(node.left, e)
                node
            }
            //否则遍历右孩子
            e > node.e -> {
                node.right=remove(node.right, e)
                node
            }
            else -> { //node.e==e
                //左孩子为null
                if (node.left == null) {
                    //先拿到当前右孩子
                    val rightNode = node.right
                    //删除右子树
                    node.right = null
                    //更新树的高度
                    --size
                    //返回删除后的右子树
                    return rightNode
                }
                //右孩子为null
                if (node.right == null) {
                    val leftNode = node.left
                    node.left = null
                    --size
                    return leftNode
                }
                //找到待删除节点左右子树均不为null的情况
                //找到比待删除节点大的最小节点,即删除节点右子树的最小节点
                // 用这个节点替代删除节点的位置
                val nodeSuccess = minimum(node.right!!)
                nodeSuccess.right = removeMin(node.right)
                nodeSuccess.left = node.left
                node.left = null
                node.right = null
                return nodeSuccess
            }
        }
    }

二分搜索树的层序遍历

bfs实现

/** bfs-层序遍历 */
fun bfsTraverse(node: Node<Int>?): List<List<Int>>? {
    return node?.let { it ->
        val arrayList: ArrayList<ArrayList<Int>> = ArrayList()
        val queue = LinkedList<Node<Int>>()
        queue.add(it)
        while (queue.isNotEmpty()) {
            var count = queue.size
            val tempList = ArrayList<Int>()
            while (count > 0) {
                val temp = queue.pop()
                tempList.add(temp.e)
                temp.left?.let {
                    queue.add(it)
                }
                temp.right?.let {
                    queue.add(it)
                }
                --count
            }
            arrayList.add(tempList)
        }
        arrayList
    }
}

dfs实现(按层输出)

/* 层序遍历-普通arraylist */
private fun getBstList(
    node: Node<E>?,
    height: Int,
    arrayList: ArrayList<LinkedList<String>>
): ArrayList<LinkedList<String>> {
    //如果当前高度为null,就新增一个子list
    if (arrayList.size <= height) {
        arrayList.add(LinkedList())
    }
    if (node == null) {
        val nullLists = arrayList[height]
        nullLists.add("#")
        return arrayList
    }
    //拿到子list,开始增加
    val lists = arrayList[height]
    //计算什么位置时增加下标
    lists.add(node.e.toString())
    getBstList(node.left, height + 1, arrayList)
    getBstList(node.right, height + 1, arrayList)
    return arrayList
}

更多方法

相关的更多实现方法这里就不一一列举了

  • 前,中,后序遍历
  • 寻找树中最小元素,最大元素
  • 寻找树中最小元素节点,最大元素节点
  • 二分搜索树删除最小值,最大值所在节点,并返回最小值,最大值
目录
相关文章
|
2月前
|
算法
数据结构之博弈树搜索(深度优先搜索)
本文介绍了使用深度优先搜索(DFS)算法在二叉树中执行遍历及构建链表的过程。首先定义了二叉树节点`TreeNode`和链表节点`ListNode`的结构体。通过递归函数`dfs`实现了二叉树的深度优先遍历,按预序(根、左、右)输出节点值。接着,通过`buildLinkedList`函数根据DFS遍历的顺序构建了一个单链表,展示了如何将树结构转换为线性结构。最后,讨论了此算法的优点,如实现简单和内存效率高,同时也指出了潜在的内存管理问题,并分析了算法的时间复杂度。
67 0
|
12天前
|
存储 C++
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
【数据结构——树】哈夫曼树(头歌实践教学平台习题)【合集】目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果:任务描述 本关任务:编写一个程序构建哈夫曼树和生成哈夫曼编码。 相关知识 为了完成本关任务,你需要掌握: 1.如何构建哈夫曼树, 2.如何生成哈夫曼编码。 测试说明 平台会对你编写的代码进行测试: 测试输入: 1192677541518462450242195190181174157138124123 (用户分别输入所列单词的频度) 预
50 14
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
|
12天前
|
Java C++
【C++数据结构——树】二叉树的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数(简单示例,手动构建) TreeNode*create
37 12
|
12天前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
37 10
|
13天前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
37 2
|
3月前
|
存储 算法 搜索推荐
探索常见数据结构:数组、链表、栈、队列、树和图
探索常见数据结构:数组、链表、栈、队列、树和图
137 64
|
2月前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
88 5
|
2月前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
126 16
|
2月前
|
算法
数据结构之文件系统模拟(树数据结构)
本文介绍了文件系统模拟及其核心概念,包括树状数据结构、节点结构、文件系统类和相关操作。通过构建虚拟环境,模拟文件的创建、删除、移动、搜索等操作,展示了文件系统的基本功能和性能。代码示例演示了这些操作的具体实现,包括文件和目录的创建、移动和删除。文章还讨论了该算法的优势和局限性,如灵活性高但节点移除效率低等问题。
80 0
|
3月前
|
存储 算法 关系型数据库
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
这篇文章主要介绍了多路查找树的基本概念,包括二叉树的局限性、多叉树的优化、B树及其变体(如2-3树、B+树、B*树)的特点和应用,旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
40 0
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)

热门文章

最新文章