一. 什么是二叉搜索树？
二叉搜索树也称为二叉排序树。它或者是一个空树或者是有如下性质的二叉树：
- 左子树上的所有节点的值小于根节点
- 右子树上的所有节点的值大于根节点
- 不存在值相同的节点
- 它的左右子树也分别为二叉搜索树
二. 为什么要有二叉搜索树？
二叉搜索树也叫二叉排序树，所以他有两个作用，搜索和排序。
作用一：搜索
注意二叉搜索树中不存在key相同的节点
如果根节点的key等于要查找的key，返回true
根节点的key < 要查找的key，到右子树中去寻找
根节点的key > 要查找的key，到左子树中去寻找
到最后根节点为空，找不到返回false
作用二：排序
中序遍历二叉搜索树，我们可以得到顺序排列的数组
说明：一般查找的功能用的比较多，很少会用它来排序。
三. 二叉搜索树的实现
接下来实现的功能包括：查找一个数、中序遍历、插入节点和删除节点这些操作。
3.1 基本框架
结构包括二叉树搜索树的节点类BSNode和二叉树搜索树类本身BSTree
二叉搜索树的节点结构
二叉搜索树主体结构框架（查找，中序遍历，插入节点和删除节点这些操作等都在这里面实现）
3.2 销毁二叉搜索树（析构函数）
析构函数的作用就是销毁整棵树，结合后序遍历+销毁节点即可完成。遍历操作有两点需要注意：
1.确保能够销毁所以节点，所以需要后序遍历：通过根节点找到左子树并销毁，同理根据根节点找到右子树并销毁，最后才来销毁根节点。
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指向一个动态开辟的节点，作为整棵树的跟节点
树不空，按二叉搜索树性质寻找插入的位置
3.4.1 代码实现
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 补充说明
1.刚开始可能不好理解为什么插入都是插入到最后的空的位置上，不会插入到两个节点的之间嘛？这是二叉搜索树的性质决定的：根节点永远大于它的左子树，小于它的右子树并且不会有相同的节点，所以比较下来，插入的节点一定会一直往下走，走到空位置处完成插入。
2.插入前，我们要查找插入的位置和记录插入位置的父亲节点，这里一开始我们是把这个父亲节点置为空的，后面这个父亲节点连接插入的节点时，有没有可能发生空指针的访问呢？其实不会
3.5 删除节点
首先查找元素是否在二叉搜索树中，如果不存在，则返回false, 否则要删除的结点按照结构可以分下面四种情况：
a. 要删除的结点没有孩子
b. 要删除的结点只有左孩子
c. 要删除的结点只有右孩子
d. 要删除的结点有左、右孩子
看起来需要删除的节点有4种情况，实际a可以与b或者c合并起来处理。那么真正的删除过程如下：
情况b：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子
情况c：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子
情况d：在它的右子树中寻找值最小的那个节点（就是他的右子树的最左边的那个节点），用它替换被删除节点。
3.5.1 代码实现
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 补充说明
