【数据结构】初识二叉搜索树（Binary Search Tree）

1. 二叉搜索树的概念

二叉搜索树又称二叉排序树，它可能是一棵空树，也可能是具有以下性质的二叉树：

• 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值。
• 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值。
• 它的左右子树也分别为二叉搜索树。

2. 二叉搜索树的操作

int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };

1.1 二叉搜索树的查找

1. 从根开始比较、查找，比根大则往右边走查找，比根小则往左边走查找。
2. 最多查找高度次，若走到空还没找到，则这个值不存在。

1.2 二叉搜索树的插入

1. 树为空，则直接新增节点，赋值给 root 指针。
2. 树不空，按二叉搜索树性质查找插入位置，插入新节点。

1.3 二叉搜索树的删除

首先查找元素是否在二叉搜索树中，如果不存在，就返回；否则要删除的节点可能分下面四种情况：

1. 要删除的节点无孩子节点；
2. 要删除的节点只有左孩子节点；
3. 要删除的节点只有右孩子节点；
4. 要删除的节点有左、右孩子节点。

看起来待删除节点有 4 种情况，实际情况 a 可以与情况 b 或者情况 c 合并起来，因此真正的删除过程如下：

• 情况 b ：删除该节点且使被删除节点的双亲节点指向被删除节点的左孩子节点 - 直接删除；
• 情况 c ：删除该节点且使被删除节点的双亲节点指向被删除节点的右孩子节点 - 直接删除；
• 情况 d ：在它的右子树中寻找中序下的第一个节点（关键码最小），用它的值填补到被删除节点中，再来处理该节点的删除问题 - 替换法删除。

---

本文完