大家好，我是鸭血粉，冒着掉头发的风险给大家总结了这篇文章。祝愿我明年还是单身大家可以学习一下~所谓二叉查找树，就是按照二进制的点来查找。每次查询只需要选择其中一颗子树进行搜索，从而减少搜索次数，提高查询效率！1.简介在上一篇文章中，我们对树型数据结构做了一些基础的介绍。今天我们继续讲一个非常常用的动态搜索树：二叉搜索树。二叉搜索树，英文全称：BinarySearchTree，缩写：BST，是计算机科学中最早投入实际应用的一种树结构，其特点如下：如果左子树不为空，则上的所有节点左子树的每个节点的值都小于其根节点的值；如果右子树不为空，则右子树上所有节点的值都大于等于其根节点的值；它的左右子树也分别是二叉搜索树；特征的定义比较广泛，所以树的结构也多种多样，比如下图：上图中的a、b、c三个图都满足了上面的特征，也叫二叉搜索树，虽然是一种通过中序遍历可以得到有效数组：[1,2,3,4,5,6,7,8]，但是在查找效率上，有一定的区别，比如查询目标是8的从根目录开始查询内容，结构如下图a5次；图b3次；图c8次；可见不同的形状需要不同的搜索次数，关于这一点，我们在后面介绍平衡二叉搜索树、红黑树等数据结构时会详细介绍。虽然二叉搜索树在不同形状下的搜索效率不同，但它是学习其他树结构的基础。了解了二叉搜索树的算法之后，相信理解其他的二叉树结构会容易很多。2.算法思路2.1．添加新元素就是给二叉树添加元素，比较简单。如果二叉树为空，则默认第一个元素是根节点。如果二叉树不为空，则根据上述特征添加左右节点。2.2.搜索元素意味着从根节点搜索元素。如果根节点为空，则直接返回空值。如果不为空，则根据左子树小于父节点，右子树大于父节点的特点。判断，然后递归查找元素，直到找到目标元素。2.3.Delete删除一个元素，就是把要删除的元素从二叉树中移除，逻辑稍微复杂一点。同样先判断根节点是否为空，如果为空则直接返回，如果不为空再考虑情况。对于被删除的节点，右子树为空，只需将被删除元素的左子树的父节点移动到被删除元素的父节点，然后移除被删除的元素。被删除节点左子树为空的场景和上面类似，只需要将被删除元素右子树的父节点移动到被删除元素的父节点，然后移除被删除元素。对于删除的节点，左右子树不为空的场景稍微复杂一点。首先定位到要删除的目标元素，根据左子节点的内容一定小于当前节点的内容，找到目标元素的左子树。通过递归遍历找到目标元素左子树的右子树，找到结束元素，用目标元素替换，最后移除结束元素。2.4.遍历二叉树有两种遍历方式：层次遍历，从根节点开始；深度遍历，分为前序、中序、后序遍历三种方式；2.4.1、hierarchicaltraversal层次遍历算法思路比较简单，从根节点开始，从左到右层次遍历元素。2.4.2.深度遍历深度遍历根据遍历的起始位置可以分为三种类型，分别是前序遍历、中序遍历和后序遍历。每种遍历方式的输出结果都是不同的。前序遍历：从根开始->左子树->右子树中序遍历：从最左子树开始->树根->右子树后序遍历：从最左子树开始->右子树subtree->Finallytotheroot虽然遍历二叉树的方法有很多种，但是只要掌握了思路和原理，实现起来就会容易很多。3、代码实践首先创建一个实体数据结构BSTNode，内容如下：然后，创建一个二叉搜索树操作类BinarySearchTree，内容如下：最后我们来测试一下，代码内容如下：输出结果:========插入元素========插入关键字key=5插入根节点插入关键字key=2插入关键字key=7插入关键字key=1插入关键字key=6插入关键字key=4插入关键字key=8插入关键字key=3插入关键字key=9插入关键字key=10========中序遍历元素=========key:1key:2key:3key:4key:5key:6key:7key:8key:9key:10========查找key为9的元素========搜索关键字key=9搜索路径[5->7->8->9->]，查找成功查找结果：true========删除key为10的元素========删除关键字key=10开始查找目标元素[5->7->8->9->10->]，搜索成功删除结果：true========再次按顺序遍历元素=========key:1键:2键:3key:4key:5key:6key:7key:8key:94.总结二叉搜索树作为树型中非常重要的一种数据结构，有着非常广泛的应用，但是二叉搜索树具有很高的灵活性，不同的插入顺序，可能会导致树的形状有比较大的差异。比如开篇介绍的图c，在某些情况下会变成一个长长的链表。这时候查询效率会大大降低。如何解决这个问题嗯，平衡二叉树就派上用场了，在后面的文章中介绍！（第一句是段子，呸呸呸，情人节快乐）
