二叉排序树(BST)

文章目录

二叉排序树(BST)1. 基本概念2. 二叉排序树增删结点2.1 增加结点2.2 删除结点2.2.1 删除叶子结点2.2.2 删除只有左子树的结点2.2.3 删除只有右子树的结点2.2.4 删除既有左子树又有右子树的结点 3. 总结与参考链接

1. 基本概念

  二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树，在一般情况下，查询效率比链表结构要高。

二叉排序树的特点：

若左子树不空，则左子树上所有结点的值均小于它的根结点的值；若右子树不空，则右子树上所有结点的值均大于它的根结点的值；左、右子树也分别为二叉排序树；如果有键值相等的结点，可以放在左子树或右子树中，但是整棵树中必须保持一致，要么都放在左子树中，要么都放在右子树中。

{5, 3, 7, 1, 4, 6, 9, 2, 8} 构成的二叉排序树如下所示：

2. 二叉排序树增删结点

2.1 增加结点

每次插入结点，都需要从根结点开始遍历，找到一个空位置插入。如果待插入结点的值比当前结点小，就在当前结点的左子树中寻找插入位置。如果待插入节点的值比当前结点大，就在当前结点的右子树中寻找插入位置。

2.2 删除结点

删除结点较为复杂一点，一共需要考虑4种情况：

(1)待删除结点没有子树，即待删除结点是叶子结点。(2)待删除结点只有左子树。(3)待删除结点只有右子树。(4)待删除结点既有左子树又有右子树。

2.2.1 删除叶子结点

删除叶子结点时，先命中待删除结点，再命中待删除结点的父结点。将父结点对应的分支置空即可，例如上图删除结点4时，父结点3的右分支置空。注意：根结点比较特殊，如果删除结点为根结点，且根结点是叶子结点，即这棵二叉树中只有根结点，那么直接将根结点置空即可。

2.2.2 删除只有左子树的结点

先命中待删除结点，再命中其父结点。将父结点对应的分支指向待删除结点的左子树的根结点即可。例如上图中父结点7的右分支直接指向了删除结点9的左子树的根结点，结点9没有其他引用，则被删除，与单链表类似。注意：根结点比较特殊，如果删除结点是根结点，且根结点只有左子树，那么直接把根结点指向左子结点即可。

2.2.3 删除只有右子树的结点

先命中待删除结点，再命中其父结点。将父结点对应的分支指向待删除结点的右子树的根结点即可。例如上图中父结点3的左分支直接指向了删除结点1的右子树的根结点，结点1没有其他引用，被删除，与单链表类似。注意：根结点比较特殊，如果删除结点是根结点，且根结点只有右子树，那么直接把根结点指向右子结点即可。

  只有左子树或只有右子树的结点被删除后，删除结点的子树相当于是嫁接到了删除结点的父结点上了。

2.2.4 删除既有左子树又有右子树的结点

  删除结点最麻烦的情况就是待删除结点同时拥有左子树和右子树，例如上图中的结点3、5、7。有两种解决方案：

方案一：先命中待删除结点，再命中待删除结点左子树中最大结点（最右下结点）maxNode，这个结点一定是叶子结点，将 maxNode 的值保存下来，然后删除 maxNode 结点，最后用保存下来的值覆盖待删除结点的值。

方案二：先命中待删除结点，再命中待删除结点右子树中的最小结点（最左下结点）minNode，这个结点一定是叶子结点，将 minNode 的值保存下来，然后删除 minNode 结点，最后用保存下来的值覆盖待删除结点的值。

方案一与方案二是对称的，下面是用方案一删除结点3的图示：

注意：前三种情况删除结点时都需要考虑根结点，但是这种同时拥有左右子树的结点，根结点不再特殊。

3. 总结与参考链接

左子树中的结点都比根结点小，右子树中的结点都比根结点大。最左下结点的值最小，最右下结点的值最大。排序二叉树使用中序遍历将按照升序输出。添加结点时，按照规则插入到树中的空位置即可。删除结点时，根据删除结点拥有子树数量不同，可以分为以下四种情况分别处理： (1)删除结点没有子树，即叶子结点，根结点特殊处理。(2)删除结点只有左子数，根结点特殊处理。（可以理解为将删除结点的左子树嫁接到删除结点的父结点上）(3)删除结点只有右子树，根结点特殊处理。（可以理解为将删除结点的右子树嫁接到删除结点的父结点上）(4)删除结点既有左子树也有右子树，根结点不特殊处理。 需要注意的是，插入结点与删除结点后，依然保持二叉排序树的特点。

参考链接：

实现代码，GitHub地址：https://github.com/Jacks5320/DataStructure百度百科：二叉排序树