二叉排序树的定义及基本操作详解

创作时间:

作者:

@小白创作中心

二叉排序树的定义及基本操作详解

引用

CSDN

https://blog.csdn.net/weixin_44162361/article/details/119112155

二叉排序树（Binary Sort Tree，BST），也称二叉查找树，是一种特殊的二叉树结构。它具有以下特性：

若左子树非空，则左子树上所有结点的关键字值均小于根结点的关键字值；
若右子树非空，则右子树上所有结点的关键字值均大于根结点的关键字值；
左、右子树本身也分别是一棵二叉排序树。

由定义可知，二叉排序树是一个递归的数据结构，可以方便地使用递归算法对二叉排序树进行各种运算。根据二叉树的定义，可得左子树结点值＜根结点值＜右子树结点值。因此，对二叉排序树进行中序遍历，可以得到一个递增的有序序列。

二叉排序树的基本操作

1. 查找

二叉排序树的查找是从根结点开始的，沿某个分支逐层向下进行比较的过程。其查找过程描述如下：若二叉排序树非空，则将给定值与根结点的关键字比较，若相等，则查找成功；若不等，则当根结点的关键字值大于给定关键字值时，在根结点的左子树中查找；否则在根结点的右子树中查找。

2. 插入

二叉排序树作为一种动态集合，其特点是树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字等于给定值的结点时再进行插入的。由于二叉排序树是递归定义的，因此插入结点的过程如下：若原二叉排序树为空，则直接插入结点；否则，若关键字＜根结点关键字，则插入左子树，若关键字＞根结点关键字，则插入右子树。

3. 构造

构造一棵二叉排序树就是依次输入数据元素，并将它们插入二叉排序树中适当位置上的过程。构造二叉排序树的过程：每读入一个元素，就建立一个新结点，若二叉排序树为空，则将新结点作为二叉排序树的根结点；若二叉排序树非空，则将新结点的值与根结点的值比较，若小于根结点的值，则插入左子树，否则插入右子树。

4. 删除

在二叉排序树中删除一个结点时，不能把以该结点为根的子树上的结点都删除，必须先把被删除结点从存储二叉排序树的链表上摘下来，将因删除结点而断开的二叉链表重新链接起来，同时**确保二叉排序树的性质（左子树结点值＜根结点值＜右子树结点值）**不会丢失。

删除操作一般会出现三种情况：

若被删除结点z是叶结点，则直接删除，不会破坏二叉排序树的性质。
若结点z只有一棵左子树或右子树，则让z的子树成为z父结点的子树，替代z的位置。
若结点z有左、右两棵子树，则令z的直接后继（或直接前驱）替代z，然后从二叉排序树中删除这个直接后继（或直接前驱），这样就转换成了第一或第二种情况。