在上一篇博客中，我们主要介绍了四种查找的方法，包括顺序查找、折半查找、插入查找以及Fibonacci查找。上面这几种查找方式都是基于线性表的查找方式，今天博客中我们来介绍一下基于二叉树结构的查找，也就是我们今天要聊的二叉排序树。今天主要聊的是二叉排序树的查找、插入与删除的内容，二叉排序的创建过程其实就是不断查找与插入的过程，也就是说当我们在创建二叉排序树时，我们会先搜索该节点在二叉排序树中的位置，若没有找到该节点则返回该节点将要插入的父节点，然后将该结点插入。而二叉排序树结点的删除则有些复杂，分为几种情况讨论，下方会给出详细的介绍。

在本篇博客的开头，我们先聊聊什么是二叉排序树。说的直白一些，具有左子树上的值<根节点的值<右子树上的值的二叉树，我们称之为二叉排序树。基于二叉排序树的特点，有结合着中序遍历的特点（中序遍历是先遍历左子树，再遍历根节点，然后遍历右子树），我们不难发现，二叉排序树的中序遍历的结果是从小到大有序的。下方我们会先给出二叉排序树的创建，然后给出二叉排序树的节点删除的代码。废话少说，进入今天博客的主题。

 

一、二叉排序树的创建

上面也简单的提了一下，二叉排序树的创建无非就是不断查找和插入的过程，当我们查找某个值没有找到时，我们就会将该值插入到二叉排序树中。因为再查找的过程中可以确定该结点要插入的合适位置，所以插入就显得比较简单了。下方我们会先给出二叉排序树查找与插入的示意图，然后再给出相应的代码实现。最后给出中序遍历的结果，观察我们创建的二叉排序树的中序遍历是否是有序的。

 

1、二叉排序树的查找与插入的示意图

我们要将集合{62, 88, 58, 47, 35, 73, 51, 99, 37, 93}中的元素放入到我们的二叉排序树中去存储，如果对我们创建好的二叉排序树进行中序搜索的话，输出的结果就是上面集合的有序序列。下方就是我们二叉排序树从无到有的完整创建过程。