一、概念
1、定义
性质
1、空树是二叉搜索树。
2、若它的左子树不为空，则右子树所有结点的值均小于它的根结点的值。
3、若它的右子树不为空，则右子树上所有结点的值均大于它的根结点的值。
4、它的左右子树均为二叉搜索树。
对于任意一棵子树而言，它的根结点的值一定大于左子树所有结点的值，且一定小于右子树所有结点的值。
2、应用
二叉搜索树的前提是二叉树，并采用了递归的方式进行定义，它的结点间满足偏序关系，左子树根结点的值一定比父节点小，右子树根结点的值一定比父结点大。
二叉搜索树为了提高搜索速度，对其进行中序遍历，得到的序列是一个递增序列。
二、二叉搜索树的链式存储
一般用孩子表示法定义一个二叉搜索树的结点。
二叉搜索树需要有一个数据域（结点值），二叉搜索树结点的左儿子结点的指针，没有左儿子结点时，值为空。二叉搜索树结点的右儿子结点的指针，没有右儿子时，值为空。
三、结点查找
概念
在树上查找某个数是否存在。
步骤
对于要查找的数val， 从根结点出发，分四种情况判断。
1、若为空树， 直接返回false。
2、若 val 的值小于根结点的值， 则递归返回左子树的 查找结果。
3、若 val 的值大于根结点的值， 则递归返回右子树的 查找结果。
4、若找到val， 则直接返回true。
四、结点插入
概念
给定一个值，生成结点后，插入到树上某个位置，并且保持这棵树还是二叉搜索树。
步骤
对于要插入的数 val，从根结点出发，分四种情况判断。
1、若为空树，则创建一个值为 val 的结点并返回。
2、若 val 的值小于树根结点的值，则递归执行插入左子树，并返回插入结果作为新的左子树。
3、若 val 的值大于树根结点的值，则递归执行插入右子树，并返回插入结果作为新的右子树。
4、直接返回当前树的根结点。
五、结点删除
概念
在树上删除给定值的结点
步骤
对于要删除的数val，从根结点出发，分七种情况讨论
1、如果当前结点为空，则直接返回空树。
2、如果要删除的值小于当前结点的值，则递归调用左子树，进行结点的删除。
3、如果要删除的值大于当前结点的值，则递归调用右子树，进行结点的删除。
4、如果当前结点是一个叶子结点，即没有左子树和右子树，那么删除该节点，并返回空树。
5、如果当前结点只有右子树而没有左子树，那么删除当前结点并返回右子树。
6、如果当前结点只有左子树而没有右子树，那么删除当前结点并返回左子树。
7、如果当前结点既有左子树又有右子树，那么找到当前结点右子树中的最小值的结点（即右子树中最左边的结点），将当前结点的值替换为这个最小值的结点的值，然后递归删除右子树中该最小值的结点。
六、总结
二叉搜索树的 查找 、插入 、和 删除 完全取决于二叉搜索树的形状，若接近完全二叉树，则为O(log n)，如果是斜树，则这三个操作近似成线性表，则为O(n)。
标签：左子,结点,val,十三,右子,二叉,搜索 From： https://blog.csdn.net/2302_80881466/article/details/144509799