一、二叉搜索树概念
二叉搜索树又称二插排序树，它要么是一个空树，要么就是具有以下性质的二叉树：
- 若它的左子树不为空，则左子树上所有节点的值都小于（大于）根节点的值。
- 若它的右子树不为空，则右子树上所有节点的值都大于（小于）根节点的值。
- 它的左右子树也分别为二叉搜索树。
二、二叉搜索树的操作
2.1 二叉搜索树的查找
- 从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。
- 最多查找高度次，走到空还没找到，说明这个值不存在。
小Tips：这里最多查找高度次的时间复杂度并不是 O ( l o g N ) O(logN)O(logN)，这是建立在比较理想的情况下，即这颗二叉树是一颗满二叉树或者完全二叉树。在极端情况下，这棵二叉树只有一条路径，此时最多查找高度次的时间复杂度就是 O ( N ) O(N)O(N)。
2.2 二叉搜索树的插入
插入的具体过程如下：
- 树为空：则直接新增节点，赋值给 root 指针。
- 树不为空：先按二叉搜索树的性质寻找插入位置，插入新节点。
2.3 二叉搜索树的删除
首先查找元素是否在二叉搜索树中，如果不存在，则返回，否则要删除的结点可能分下面四种情况:
- 要删除的结点没有孩子结点。
- 要删除的结点只有左孩子结点。
- 要删除的结点只有右孩子结点。
- 要删除的结点有左、右孩子节点。
虽然看起来删除一个结点有 4 中情况，但实际上情况1可以和情况2或者情况3合并起来，因此真正的删除过程如下：
- 情况一（要删除的结点只有左孩子）：删除该节点且使被删除节点的双亲结点指向被删除结点的左孩子结点----直接删除。
- 情况二（要删除的结点只有右孩子）：删除该结点且使被删除结点的双亲结点指向被删除结点的右孩子结点-----直接删除。
- 情况三（要删除的结点有左、右孩子）：在它的左子树中寻找出关键码最大的结点，用它的值填补到被删除结点中，再来处理该结点的删除问题----替换法删除。
三、二叉搜索树的实现
二插搜索树只是一种结构，它本质上是由一个个结点链接而成，因此我们首先需要定义一个结点类，这个结点用来存储数据。有了结点类之后就需要定义一个二叉搜索树的类，这个类主要是用来维护结构的，实现增删查改等功能，因为它是维护结构的，因此这个类里面的成员变量只需要一个根节点即可，有了这个根节点就能对整个数的结构进行维护管理。
3.1 BinarySearchTreeNode（结点类）
template <class K> struct BinarySearchTreeNode { typedef BinarySearchTreeNode<K> TNode; BinarySearchTreeNode(const K& val = K()) :_val(val) ,_left(nullptr) ,_right(nullptr) {} K _val; TNode* _left; TNode* _right; };
3.2 BinarySearchTree（二叉搜索树类）
3.2.1 框架
template <class K> class BinarySearchTree { typedef BinarySearchTreeNode<K> BSTNode; typedef BinarySearchTree<K> Self; public: BinarySearckTree() :_root(nullptr) {} private: BSTNode* _root; };
3.2.2 insert（插入）
非递归版：
bool insert(const K& val) { if (_root == nullptr) { _root = new BSTNode(val); return true; } BSTNode* newnode = new BSTNode(val); BSTNode* cur = _root; BSTNode* parent = nullptr; while (cur) { if (val < cur->_val) { parent = cur; cur = cur->_left; } else if (val > cur->_val) { parent = cur; cur = cur->_right; } else { return false;//相等就说明树中已经有了，就应该插入失败 } } //if (parent->_left == cur)//左右都是空，每次就走上面这个了 if(val < parent->_val) { parent->_left = newnode; } else { parent->_right = newnode; } return true; }
小Tips：需要单独考虑根节点为空的情况。用 cur 找到该结点应该要插入的位置，用 parent 指向该位置的双亲结点，以实现链接关系。最后还需要判断插入到双亲结点的左侧还是右侧。我们实现的这个二叉搜索树要求存储相同值的结点在一个二叉搜索树中只能出现一次，因此当插入一个值 val 的时候，如果检测到树中已经有一个结点存的是 val，那么就应该返回 false，表明插入失败。
递归版：
//插入(递归---版本一) private: bool _InsertR(BSTNode*& root, BSTNode* parent, const K& key) { if (root == nullptr)//为空说明就是在该位置插入 { BSTNode* newnode = new BSTNode(key); if (parent != nullptr) { if (key < parent->_val) { parent->_left = newnode; } else { parent->_right = newnode; } } else { root = newnode; } return true; } //root不为空说明还没有找到待插入的位置，还得继续找 if (key < root->_val) { return _InsertR(root->_left, root, key); } else if (key > root->_val) { return _InsertR(root->_right, root, key); } else { return false; } } public: //插入(递归) bool InsertR(const K& key) { return _InsertR(_root, _root, key); }
//插入(递归---版本二) private: bool _InsertR(BSTNode*& root, const K& key) { if (root == nullptr)//为空说明就是在该位置插入 { root = new BSTNode(key); return true; } //root不为空说明还没有找到待插入的位置，还得继续找 if (key < root->_val) { return _InsertR(root->_left, key); } else if (key > root->_val) { return _InsertR(root->_right, key); } else { return false; } } public: //插入(递归) bool InsertR(const K& key) { return _InsertR(_root, key); }
小Tips：在空树的时候执行插入，是需要改变根节点 _root 的，即需要对指针进行修改，因此这里需要使用引用或者二级指针。
3.2.3 InOrder（中序遍历）
private: void _InOrder(BSTNode* root) const { if (root == nullptr) { return; } _InOrder(root->_left); cout << root->_val << " "; _InOrder(root->_right); } public: void InOrder() { _InOrder(_root); cout << endl; }
小Tips：这里的中序遍历用的是递归的方式来实现的，但是递归函数一定是需要一个参数的，要中序遍历整个二叉树，用户一定是要把根节点 _root 传给这个函数，但是根节点 _root 是私有的成员变量，用户是访问不到的，因此我们不能直接提供中序遍历函数给用户。正确的做法是，虽然用户访问不到根结点，但是类里面可以访问呀，所以我们可以在类里面实现一个中序遍历的子函数 _InOrder，在这个子函数中实现中序遍历的逻辑，然后我们再去给用户提供一个中序遍历的函数接口 InOrder，由它去调用 _InOrder。这样以来用户就可以正常去使用中序遍历啦。
3.2.4 find（查找）
非递归版：
bool find(const K& key) { BSTNode* cur = _root; while (cur) { if (key < cur->_val) { cur = cur->_left; } else if (key > cur->_val) { cur = cur->_right; } else { return true; } } return false; }
递归版：
private: bool _FindR(BSTNode* root, const K& key) { if (root == nullptr) { return false; } if (key < root->_val) { return _FindR(root->_left, key); } else if (key > root->_val) { return _FindR(root->_right, key); } else { return true; } } public: bool FindR(const K& key) { return _FindR(_root, key); }
3.2.5 erase（删除）
非递归版：
bool erase(const K& key) { BSTNode* cur = _root; BSTNode* parent = nullptr; //先找需要删除的结点 while (cur) { if (key < cur->_val) { parent = cur; cur = cur->_left; } else if (key > cur->_val) { parent = cur; cur = cur->_right; } else { //到这里说明cur就是待删除的节点 if (cur->_left == nullptr)//如果cur只有一个孩子(只有右孩子)，直接托孤 { if (parent == nullptr)//说明删除的是根结点 { _root = _root->_right; } else if (cur == parent->_left)//判断cur是左孩子还是右孩子 { parent->_left = cur->_right; } else if(cur == parent->_right) { parent->_right = cur->_right; } } else if(cur->_right == nullptr)//如果cur只有一个孩子(只有左孩子) { if (parent == nullptr)//说明删除的是根结点 { _root = _root->_left; } else if (cur == parent->_left)//判断cur是左孩子还是右孩子 { parent->_left = cur->_left; } else if (cur == parent->_right) { parent->_right = cur->_left; } } else//到这里说明cur有两个孩子 { BSTNode* parent = cur; BSTNode* leftmax = cur->_left;//找到左孩子中最大的那个 while (leftmax->_right) { parent = leftmax; leftmax = leftmax->_right; } swap(cur->_val, leftmax->_val); cur = leftmax; //有一种极端情况就是左边只有一条路径 if (leftmax == parent->_left) { parent->_left = leftmax->_left; } else { parent->_right = leftmax->_left; } } delete cur; return true; } } return false; }
小Tips：在上面的代码中我们始终让 cur 指向待删除节点，parent 指向待删除结点的双亲，也就是 cur 的双亲。删除大体上就分为2. 3小节中提到的三种情况。但是里面任然有一些细节需要我们注意，比如删除根结点的情况，即 parent == nullptr 的时候。在情况一和情况二中，我们还需要判断待删除结点 cur 是其双亲结点 parent 的左孩子还是右孩子，以保证让 cur 的孩子和 parent 建立正确的链接关系。情况三，待删除的结点有两个孩子，我们这里的做法是，找出 cur 左子树中最大的那个节点 leftmax，让它来替换 cur，帮助 cur 带“孩子”。找到左子树中值最大的结点很容易，从 cur 的左孩子开始，一路往右即可。找到后交换 cur 和 leftmax 中存储的值。交换后 leftmax 就变成了要删除的结点，所以所以此时需要让 cur 重新指向 leftmax 这个结点。由于要删除 leftmax 结点，为了方便后面修改链接关系，这里我们还需要找到 leftmax 的双亲结点，因此在这个局部域中我们重新定义了一个 parent，它和外面那个 parent 并不冲突，优先使用局部的，但是注意里面这个 parent 表示的意义和外面 parent 的意义是有所不同的，前者表示 cur 左树中最大节点的双亲结点，后者表示 cur 的双亲结点。最后我们需要通过修改链接关系来实现 cur 结点的删除，这里的链接关系有以下两种情形：
情形一：
小Tips：Step2 中的交换是交换节点中的值，并不是交换两个结点。最终 leftmax 和 cur 指向同一个结点。
情形二：
小Tips：情形二与情形一最大的不同点体现在两个地方，第一情形二中的 parent 就是 cur，只说明我们在定义 parent 赋初值的时候不能让 parent = nullptr，应该让 parent = cur，否则后面修改链接关系会出现访问空指针的问题。第二点不同在于修改链接关系，情形二是让 parent 的左孩子指向 leftmax 的左孩子；情形一是让 parent 的右孩子指向 leftmax 的左孩子。因此在修改链接关系的时候要进行判断，看是哪种情形。在第二点不同里面又有一个相同点，即无论是 parent 的左孩子，还是 parent 的右孩子，最终都指向了 leftmax 的左孩子，这是为什么呢？原因其实很简单，leftmax 的右孩子一定为空，而左孩子则不一定为空。为什么可以肯定右孩子一等为空，因为 leftmax 是左子树中最大的那个结点，如果它的右孩子不为空，说明当前这个 leftmax 一定不是最大的那个结点。因此在修改链接关系的时候，要让 parent 与 leftmax 的左孩子建立连接。最后需要注意，交换完之后，只能通过修改链接关系去删除 cur 结点，不能通过递归调用去删除，因为这个函数每次都是从根节点开始查找的，交换后这棵树暂时不满足二叉搜索树的结构，以情形一为例，它就找不到存储8的结点。
递归版：
private: //删除递归版 bool _eraseR(BSTNode*& root, const K& key) { if (root == nullptr) { return false; } if (key < root->_val) { return _eraseR(root->_left, key); } else if (key > root->_val) { return _eraseR(root->_right, key); } else { //相等了，需要进行删除了 BSTNode* del = root; if (root->_left == nullptr)//左为空 { root = root->_right; } else if (root->_right == nullptr)//右为空 { root = root->_left; } else//左右都不为空 { BSTNode* parent = root; BSTNode* leftmax = root->_left;//找到左孩子中最大的那个 while (leftmax->_right) { parent = leftmax; leftmax = leftmax->_right; } swap(root->_val, leftmax->_val); return _eraseR(root->_left, key); } delete del; del = nullptr; return true; } } public: //删除递归版 bool eraseR(const K& key) { return _eraseR(_root, key); }
小Tips：在交换后，虽然整棵树可能不满足二叉搜索树的结构，但是 root 结点的左子树一定是满足二叉搜索树的，因为我们交换的是 root 结点的 _val 和左子树中最大的那个 _val，而 root 结点的 _val 一定是比左子树中最大的那个 _val 还要大的，所以交换完之后 root 的左子树任然满足二叉搜索树的结构，此时我们就可以通过递归调用去 root 的左子树中找要删除的结点，并且交换后待删除的结点一定变成了情况一或者情况二中的一种。递归版中对情况一和情况二的处理变简单了许多，因为 root 是一个引用，如果发现 root 的一个孩子为空，直接把 root 的另一个孩子赋值给它即可，在赋值之前记得保存一下 root 的值，这个值指向的结点就是要删除的结点，把这个值保存下来后面才能去 delete，否则赋值后就没有指针指向该结点，那就没办法释放这个结点的空间资源，就会造成内存泄漏。非递归中即使用了引用也不能这样搞，因为非递归中，一个引用始终是在一个函数栈帧里面，而引用是不能改变指向的。但是递归就不一样了，每一次递归调用都会开辟新的函数栈帧，每一个函数栈帧中 root 都是不同结点的别名。
