👉二叉搜索树的概念👈
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树：
若它的左子树不为空，则左子树上所有节点的值都小于根节点的值。
若它的右子树不为空，则右子树上所有节点的值都大于根节点的值。
它的左右子树也分别为二叉搜索树。
因为二叉搜索树的左子树所有节点的键值比根节点的小，右子树所有节点的键值比根节点的大，所以查找的效率就会比较高，查找效率为O(h)，h为树的高度。
二叉搜索树也被称为二叉排序树的原因是：二叉搜索树中序遍历的结果是升序的。
二叉搜索树中的键值是不允许修改的，如果可以修改的话，就有可能不再是二叉搜索树了。
👉模拟实现二叉搜索树👈
节点的定义
template <class K> struct BSTreeNode { BSTreeNode<K>* _left; BSTreeNode<K>* _right; K _key; BSTreeNode(const K& key) : _left(nullptr) , _right(nullptr) , _key(key) {} };
因为键值可以是多种类型的，所以我们树的节点定义成模板类。同时还提供了节点的构造函数，new节点时可以调用节点的构造函数初始化。
插入操作（非递归）
插入的具体过程如下：
树为空，则直接新增节点，赋值给 root 指针。
树不空，按二叉搜索树性质查找插入位置，插入新节点。即当前节点的值小于插入节点的值，往右走；当前节点的值大于插入节点的值，往左走；直至当前节点为空，找到插入位置。走过过程中，还需要记录前一个节点才能完成插入。
插入可能从左边插入，也有可能从右边插入。我们可以通过比较前一个节点的值与插入节点的值的大小，就可以知道从哪一边插入节点。
当二叉搜索树中已经存在插入的值时，插入失败，返回false。因为二叉搜索树中不允许重复的值存在。
bool Insert(const K& key) { if (_root == nullptr) { _root = new Node(key); return true; } Node* cur = _root; Node* parent = nullptr; while (cur) { if (cur->_key < key) // 当前节点的值小于插入节点的值，往右走 { parent = cur; cur = cur->_right; } else if(cur->_key > key) // 当前节点的值大于插入节点的值，往左走 { parent = cur; cur = cur->_left; } else { return false; // 插入失败 } } // 插入节点 cur = new Node(key); // 判断从哪边插入节点 if (parent->_key < key) // 从右边插入节点 parent->_right = cur; else parent->_left = cur; return true; // 插入成功 }
现在插入节点的接口已经写完了，那么我们再写一个中序遍历接口Inorder来验证一下我们写得对不对。因为中序遍历首先要有根节点才能进行遍历，而根节点_root是私有的，在类外无法拿到它。但是遍历是需要根节点的，那怎么解决呢？我们可以在类里定义一个公有的辅助函数帮我们拿到根节点_root，然后就可以遍历了。但是个人比较推荐第二种方法：在类里定义一个私有的中序遍历的子函数_Inorder，Inorder函数调用子函数_Inorder来完成中序遍历。
public: void Inorder() { _Inorder(_root); cout << endl; } private: // 中序遍历的子函数 void _Inorder(Node* root) { if (root == nullptr) return; _Inorder(root->_left); cout << root->_key << endl; _Inorder(root->_right); }
注：二叉搜索树的中序遍历结果是没有重复元素的升序序列。
查找操作（非递归）
查找操作的逻辑和插入操作的逻辑是一样的，具体步骤如下：
从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。
最多查找高度次，走到到空，还没找到，这个值不存在。
bool Find(const K& key) { if (_root == nullptr) return false; Node* cur = _root; while (cur) { if (cur->_key < key) // 当前节点的值比要查找的值小，往右走 cur = cur->_right; else if (cur->_key > key) // 当前节点的值比要查找的值大，往左走 cur = cur->_left; else return true; // 找到了 } return false; // 没找到 }
删除操作（非递归）
首先查找元素是否在二叉搜索树中，如果不存在，则返回
false，否则要删除的结点可能分下面四种情况：要删除的结点无孩子结点
要删除的结点只有左孩子结点
要删除的结点只有右孩子结点
要删除的结点有左、右孩子结点
看起来待删除节点有四种情况，实际情况 1 可以与情况 2或者 3 合并起来，因此真正的删除过程如下：
情况 2：删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点（直接删除）
情况 3：删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点（直接删除）
情况 4：找出删除节点左子树最大值的节点或者是右子树最小值的节点，并与删除节点进行值交换。交换后，上述两个节点就成了要删除的替换节点。替换节点要么没有孩子，要么只有一个孩子，可以转化为前面的三种情况（替换法删除）
bool Erase(const K& key) { Node* parent = nullptr; Node* cur = _root; while (cur) { if (cur->_key < key) { parent = cur; cur = cur->_right; } else if (cur->_key > key) { parent = cur; cur = cur->_left; } else { // 开始删除 if (cur->_left == nullptr) // 待删除节点没有左孩子 { if (cur == _root) // 待删除节点为根节点 { _root = cur->_right; } else { if (cur == parent->_left) // 删除节点在父节点的左边 parent->_left = cur->_right; else // 删除节点在父节点的右边 parent->_right = cur->_right; } delete cur; cur = nullptr; // 可不写 } else if (cur->_right == nullptr) // 待删除节点没有右孩子 { if (cur == _root) // 待删除节点为根节点 { _root = cur->_left; } else { if (cur == parent->_left) // 删除节点在父节点的左边 parent->_left = cur->_left; else // 删除节点在父节点的右边 parent->_right = cur->_left; } delete cur; } else // 待删除节点有左右孩子(替换法删除) { // 找到右子树的最小节点进行替换 Node* minParent = cur; // minParent不能设置为nullptr Node* min = cur->_right; while (min->_left) { minParent = min; min = min->_left; } swap(cur->_key, min->_key); // 因为替换节点是右子树的最小节点,没有左孩子 if (minParent->_left == min) // 替换节点在父节点的左边 minParent->_left = min->_right; else minParent->_right = min->_right; delete min; } return true; } } return false; // 删除失败 }
测试删除接口
void BSTreeTest2() { BSTree<int> t; int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 , 5 }; for (auto e : a) { t.Insert(e); } for (auto e : a) { t.Erase(e); t.Inorder(); } cout << endl; }
如果想要啊检验自己是否掌握删除操作的老铁，可以做做力扣上的这道题：删除二叉搜索树中的节点。
