二叉排序树（简称BST） 又称二叉查找（搜索）树，其定义为：二叉排序树或者是空树，或者是满足如下性质（BST性质）的二叉树：
①： 若它的左子树非空，则左子树上所有结点值（指关键字值）均小于根结点值；
②： 若它的右子树非空，则右子树上所有结点值均大于根结点值；
③： 左、右子树本身又各是一棵二叉排序树。
注意：二叉排序树中没有相同关键字的结点。
二叉排序树的中序遍历序列有什么特点？
答：中序遍历二叉排序树会得到一个升序的序列。
二叉排序树的结点类型如下：
看一个已经排好序的二叉排序树：
（每一个结点的左子树中所有的结点都比该结点小）
（每一个结点的右子树中所有的结点都比该结点大）
二叉排序树上的查找：
二叉排序树的插入和生成（动态查找）：
前面讲的顺序表的查找都是静态查找。
注意：在二叉排序树中插入一个关键字为k的新结点，要保证插入后仍满足BST性质。
插入过程：
（1）若二叉排序树T为空，则创建一个key域为k的结点，将它作为根结点；
（2）否则将k和根结点的关键字比较，若两者相等，则说明树中已有此关键字k，无须插入，直接返回0；
（3）若k< T->key，则将k插入根结点的左子树中。
（4）否则将它插入右子树中。
举个栗子：
由面的序列画出其二叉排序树：
过程解析：
将第一个数25作为根结点
然后从左往右一个一个数比较
比25小的放在左子树，比25大的放在右子树
然后每经过一个结点都要和该结点进行比较
比该结点小就放左子树，比该结点大就放右子树
特点：
根结点的最左下结点是关键字最小的结点
根结点的最右下结点是关键字最大的结点
（就比如上图中的最左下的是2最右下的是74）
二叉排序树的结点删除：
（1）被删除的结点是叶子结点：直接删去该结点
（2）被删除的结点只有左子树或者只有右子树，用其左子树或者右子树替换它（结点替换）。
（3）被删除的结点既有左子树，也有右子树 。 以其中序前驱值替换之（值替换） ，然后再删除该前驱结点。前驱是左子树中最大的结点。 也可以用其后继替换之，然后再删除该后继结点。后继是右子树中最小的结点。
过程分析图示：
平衡二叉排序树：
查找效率分析：
BST是一种查找效率比较高的组织形式，但其平均查找长度受树的形态影响较大，形态比较均匀时查找效率很好，形态明显偏向某一方向时其效率就大大降低。因此，希望有更好的二叉排序树，其形态总是均衡的，查找时能得到最好的效率，这就是平衡二叉排序树。
最后看两个例题：
例题1：
例题2：
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.mushiming.com/mjsbk/4163.html