- 一. 什么是二叉搜索树？
- 二. 为什么要有二叉搜索树？
- 作用一：搜索
- 作用二：排序
- 三. 二叉搜索树的实现
- 3.1 基本框架
- 3.2 销毁二叉搜索树（析构函数）
- 3.3 查找节点
- 3.4 插入节点
- 3.4.1 代码实现
- 3.4.2 补充说明
- 3.5 删除节点
- 3.5.1 代码实现
- 3.5.2 补充说明
二叉搜索树也称为二叉排序树。它或者是一个空树或者是有如下性质的二叉树：
- 左子树上的所有节点的值小于根节点
- 右子树上的所有节点的值大于根节点
- 不存在值相同的节点
- 它的左右子树也分别为二叉搜索树
二. 为什么要有二叉搜索树？
二叉搜索树也叫二叉排序树，所以他有两个作用，搜索和排序。
作用一：搜索- 注意二叉搜索树中不存在key相同的节点
- 如果根节点的key等于要查找的key，返回true
- 根节点的key < 要查找的key，到右子树中去寻找
- 根节点的key > 要查找的key，到左子树中去寻找
- 到最后根节点为空，找不到返回false
中序遍历二叉搜索树，我们可以得到顺序排列的数组
说明：一般查找的功能用的比较多，很少会用它来排序。
三. 二叉搜索树的实现
接下来实现的功能包括：查找一个数、中序遍历、插入节点和删除节点这些操作。
3.1 基本框架结构包括二叉树搜索树的节点类BSNode和二叉树搜索树类本身BSTree
二叉搜索树的节点结构
3.2 销毁二叉搜索树（析构函数）二叉搜索树主体结构框架（查找，中序遍历，插入节点和删除节点这些操作等都在这里面实现）
析构函数的作用就是销毁整棵树，结合后序遍历+销毁节点即可完成。遍历操作有两点需要注意：
- 确保能够销毁所以节点，所以需要后序遍历：通过根节点找到左子树并销毁，同理根据根节点找到右子树并销毁，最后才来销毁根节点。
- 如果遍历操作是递归完成的，不应把递归主体直接放到析构函数里，这样会造成析构函数的递归调用问题，因为析构函数的调用结束代表对象已经销毁，this随即指针失效。一定要用递归也行，把递归的整个主体封装成一个函数，让析构函数调用它，这样是安全的。
void Destroy(BSNode* root)
{
// 空树的话什么都不用干
if (root==nullptr)
{
return;
}
// 1、销毁左子树
Destroy(root->_left);
// 2、销毁右子树
Destroy(root->_right);
// 3、销毁根节点
delete root;
}
// 析构函数
~BSTree()
{
Destroy(_root);
// 最后把根节点置为空，防止野指针
_root = nullptr;
}
3.3 查找节点
首先说明二叉搜索树中不存在key相同的节点，查找节点的步骤如下：
- 如果根节点的key等于要查找的key，返回true
- 根节点的key < 要查找的key，到右子树中去寻找
- 根节点的key > 要查找的key，到左子树中去寻找
- 如果最后根节点为空，说明找不到返回false
bool Find(const T& key)
{
// 从根节点开始
BSNode* cur = _root;
// 当根节点不为空时继续
while (cur)
{
if (cur->_key == key)
{
return true;
}
else if (cur->_key < key)
{
cur = cur->_right;
}
else if (cur->_key > key)
{
cur = cur->_left;
}
}
// 根节点为空，就是空树，找不到了
return false;
}
3.4 插入节点
- 如果是空树的话，直接让_root指向一个动态开辟的节点，作为整棵树的跟节点
- 树不空，按二叉搜索树性质寻找插入的位置
bool Insert(const T& key)
{
// 空树情况的处理
if (!_root)
{
_root = new BSNode(key);
return true;
}
BSNode* parent = nullptr;//记录需要插入位置的父亲
BSNode* cur = _root; //记录需要插入的位置
while (cur)
{
parent = cur;
// 已经有key了，插入失败
if (cur->_key == key)
{
return false;
}
else if (cur->_key < key)
{
cur = cur->_right;
}
else
{
cur = cur->_left;
}
}
// 最后一定是在空的位置插入的
cur = new BSNode(key);
// 判断要插在左边还是右边
if (parent->_key < key)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
return true;
}
3.4.2 补充说明
-
刚开始可能不好理解为什么插入都是插入到最后的空的位置上，不会插入到两个节点的之间嘛？这是二叉搜索树的性质决定的：根节点永远大于它的左子树，小于它的右子树并且不会有相同的节点，所以比较下来，插入的节点一定会一直往下走，走到空位置处完成插入。
-
插入前，我们要查找插入的位置和记录插入位置的父亲节点，这里一开始我们是把这个父亲节点置为空的，后面这个父亲节点连接插入的节点时，有没有可能发生空指针的访问呢？其实不会
首先查找元素是否在二叉搜索树中，如果不存在，则返回false, 否则要删除的结点按照结构可以分下面四种情况：
a. 要删除的结点没有孩子
b. 要删除的结点只有左孩子
c. 要删除的结点只有右孩子
d. 要删除的结点有左、右孩子
看起来需要删除的节点有4种情况，实际a可以与b或者c合并起来处理。那么真正的删除过程如下：
情况b：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子
情况c：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子
情况d：在它的右子树中寻找值最小的那个节点（就是他的右子树的最左边的那个节点），用它替换被删除节点。
bool Erase(const T& key)
{
// 空树的话算删除失败
if (!_root)
{
return false;
}
// 1、找到要删除的节点和它的父亲节点
BSNode* parent = nullptr;
BSNode* cur = _root;
while (cur)
{
if (cur->_key == key)
{
break;
}
else if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else
{
parent = cur;
cur = cur->_left;
}
}
// 不存在要删除的节点，删除失败
if (cur == nullptr)
{
return false;
}
// 2、开始删除节点
// 情况a：要删除的节点没有左孩子
if (cur->_left == nullptr)
{
// 要删除的节点为根节点的情况（必须要先处理，因为这时parent为空）
// 如果先处理else的话会发生空指针的访问
if (cur == _root)
{
_root = cur->_right;
}
else// 让父亲指向要删除节点的右子树
{
if (parent->_left == cur)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
}
// 删除节点
delete cur;
}
else if (cur->_right == nullptr)// 情况b：要删除节点没有右孩子
{
// 同样的，先处理删除根节点的情况
if (cur == _root)
{
_root = _root->_left;
}
else// 让父亲节点指向要删除节点的左子树
{
if (parent->_left == cur)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
}
// 删除节点
delete cur;
}
else // 情况c：要删除的节点有两个孩子
{
// 记录要删除节点的右子树的最小值节点的父亲
BSNode* minParent = cur;
// 记录要删除节点的右子树的最小值节点（即右子树的最左边的节点）
BSNode* minRight = cur->_right;
// 查找要删除节点的右子树的最小节点
while (minRight->_left)
{
minParent = minRight;
minRight = minRight->_left;
}
// 交换要删除节点和最小节点的值
cur->_key = minRight->_key;
// 删除前把最小节点的右子树连接到它的父亲上
if (minParent->_left == minRight)
{
minParent->_left = minRight->_right;
}
else
{
minParent->_right = minRight->_right;
}
delete minRight;
}
return true;
}
3.5.2 补充说明
