此篇算是用C++讲高阶数据结构第一篇，在C++完结之前高阶数据结构内容都放在④⑤两个专栏，等后面C++完结还会学图和算法的内容。
先讲二叉搜索树是因为讲解 map 和 set 的特性需要二叉搜索树做铺垫，理解搜索二叉树有助于更好地理解 map 和 set 的特性。第二个原因是为了后期讲解查找效率极高的平衡搜索二叉树，随后再讲完红黑树，我们就可以模拟实现 map 和 set 了。
1. 二叉搜索树（BinarySearchTree）
概念：搜索二叉树（二叉搜索树）又称为二叉排序树，它或者是一颗空树，
或者是具有以下性质的二叉树：
- 若其左子树不是空，则左子树上所有节点的值都小于根结点的值
- 若其右子树不是空，则右子树上所有结点的值都大于根结点的值
- 其左右子树必须都是二叉搜索树
至于叫它 "搜索二叉树"，还是 "二叉搜索树"，都是可以的，就是叫搜索二叉树的英文缩写不太好。
结论：任意一个子树都需要满足，左子树的值 < 根 < 右子树的值，才能构成二叉搜索树。
1.1 二叉搜索树的优势和劣势
既然叫搜索二叉树，它肯定是用来搜索的，当满足搜索二叉树时你将可以快速地查找任意的值。
举个例子： 查找7
放到以前我们如果不用二分查找，可能会选择用暴力的方式去从头到尾遍历一遍。
但现在学了搜索二叉树，我们就可以轻松找到这个7了，7 比 8(根节点) 小，
根据搜索二叉树的性质，它必然不会出现在右子树 (右边大) ...
搜索二叉树查找一个值的最坏情况，也只是查找高度次。
二叉搜索树的时间复杂度：O(N)
上面的例子会让人误以为搜索二叉树的增删查改的时间复杂度是O（logN），
但实际上是O（N），因为这棵树是有可能会 蜕化 的，极端情况下会蜕化成一个 "单边树"
比如按有序插入：
最差情况：二叉搜索树退化为单边树（或类似单边），其平均比较次数为：O（N）
最优情况：二叉搜索树为完全二叉树（或接近完全二叉树），其平均比较次数为：O（logN）
对于时间复杂度的分析我们要做一个悲观主义者，根据最差情况去定时间复杂度：O（N）
1.2 二叉搜索树的改良
如果搜索二叉树退化成了单边树，其性能也就失去了，能否进行改进让它保持性能？
如何做到不论按照上面次序插入关键码，二叉搜索树的性能均能达到最优？
搜索二叉树由于控制不了极端情况，与 O（logN）失之交臂，但平衡二叉搜索树做到了。
严格意义上来说满二叉树才是O（logN），完全二叉树是接近O（logN）。
而平衡搜索二叉树维持左右两边均匀程度，让它接近完全二叉树，从而让效率趋近O（logN）。
后面我们学的各种树（AV树，红黑树）可以说都是二叉搜索树的改良。
2. 二叉搜索树的实现
2.1 二叉搜索树的定义
此时我们的BinarySearchTree就缩写成BSTree了。
这里我们用模板，模板参数我们给了一个K，表示 key 的意思（模板参数并非一定要用 T）。
template<class K> class BSTreeNode { public: BSTreeNode(const K& key) :_left(nullptr) , _right(nullptr) , _key(key) {} BSTreeNode<K>* _left; BSTreeNode<K>* _right; K _key; };
下面我们来定义整个树，BSTreeNode 有些长了，这里将其 typedef 成 Node 。
构造函数都没必要写，它自己生成的就够用了：
template<class K> class BSTree { typedef BSTreeNode<K> Node; protected: Node* _root = nullptr; };
2.2 二叉搜索树的插入
二叉搜索树的插入是会“去重”的。
我们先来实现最简单的插入操作：
- 如果树为空，则直接新增结点，赋值给 root 指针。
- 如果树不为空，按二叉搜索树性质查找插入位置，插入新节点。
Insert 的实现我们可以用递归，也可以用非递归，这一块递归比非递归更难理解。
秉着先难后易的态度，我们先讲比较难理解的非递归版本
Step1：首先检查是否有根结点 _root，如果没有我们就 new 一个结点出来作为根结点。此时插入成功，返回 true。
Step2：插入就需要找到插入位置，我们定义一个 cur 变量，从根节点开始，
根据搜索二叉树 性质，将 cur 结点的值与插入的值 进行大小比较。
如果插入的值大于当前结点值，则将 cur 结点向右移动 cur=cur->_right ；
如果插入的值小于当前节点值，就将 cur 结点向左移动 cur=cur->_left。
值得注意的是，还需要额外记录一下 cur 的父结点，
因为你不知道什么时候会碰到nullptr结束。
并且当我们找到插入位置后，仅仅 new 上一个新结点给 cur 是完成不了插入操作的。
因为直接这么做 cur 也只是一个局部变量而已，需要 cur 跟上一层（cur 的父亲）相链接才行。
为了能找到上一层，所以我们还需要额外定义一个 prev 变量来记录 cur 的父结点，
在我们更换 cur 结点时记录父结点的位置 prev=cur 即可。
当然了，还有一种插入失败的情况，就是判断大小时出现等于的情况，返回 false 即可。
（重复的值是不允许插入的，默认情况是不允许冗余的！但是也有针对这个的变形，后续再说）
Step3：插入。new 一个新结点给 cur，此时 cur 只是一个局部变量，必须要和父亲链接，
此时应该链接父亲的左边，还是链接父亲的右边？我们不知道，所以我们需要再做一个比较：
如果父节点的值大于插入的值，则将 cur 链接到父亲左边 prev->_left=cur；
反之将 cur 链接到父亲右边 prev->_right=cur。
最后，插入成功返回 true。
insert 代码：
bool Insert(const K& key) { if (_root == nullptr) { _root = new Node(key); return true; } Node* prev = nullptr; Node* cur = _root; while (cur != nullptr) // 找到要插入的位置 { if (key < cur->_key) // 要插入的值比当前值小 { prev = cur; // 记录cur，等下cur更新就是cur的父亲 cur = cur->_left; // 到左边插入 } else if (key > cur->_key) { prev = cur; cur = cur->_right; } else { return false; // 相等，插入失败 } } cur = new Node(key); // 走到这，cur就是要插入的位置 if (key < prev->_key) // 如果key比cur的父亲小 { prev->_left = cur; // 插入到父亲的左孩子 } else { prev->_right = cur; } return true; }
再写一个中序遍历来测试一下插入的效果：
void InOrder(Node* root) { if (root == nullptr) { return; } InOrder(root->_left); cout << root->_key << " "; InOrder(root->_right); }
模拟出一个测试用例：
void TestBSTree1() { BSTree<int> t; int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 }; for (const auto& e : a) { t.Insert(e); } t.InOrder(); // 没法传根 }
此时会出现一个问题，因为根是私有的，我们没办法把根传过去。
此时我们可以选择在类内部写一个成员函数 GetRoot 去取根，但是这里我们可以选择这么做：
干脆将刚才我们实现的中序设为 protected 保护，然后再写一个 InOrder 放在公有的区域。
这就是在类内访问 _root 了，没有什么问题。
如此一来我们在类外就可以直接调用 InOrder，并且也不需要传递参数了。
BinarySearchTree.h：
#pragma once #include <iostream> using namespace std; template<class K> class BSTreeNode { public: BSTreeNode(const K& key) :_left(nullptr) , _right(nullptr) , _key(key) {} BSTreeNode<K>* _left; BSTreeNode<K>* _right; K _key; }; template<class K> class BSTree { typedef BSTreeNode<K> Node; public: bool Insert(const K& key) { if (_root == nullptr) { _root = new Node(key); return true; } Node* prev = nullptr; Node* cur = _root; while (cur != nullptr) // 找到要插入的位置 { if (key < cur->_key) // 要插入的值比当前值小 { prev = cur; // 记录cur，等下cur更新就是cur的父亲 cur = cur->_left; // 到左边插入 } else if (key > cur->_key) { prev = cur; cur = cur->_right; } else { return false; // 相等，插入失败 } } cur = new Node(key); // 走到这，cur就是要插入的位置 if (key < prev->_key) // 如果key比cur的父亲小 { prev->_left = cur; // 插入到父亲的左孩子 } else { prev->_right = cur; } return true; } void InOrder() { _InOrder(_root); cout << endl; } protected: void _InOrder(Node* root) { if (root == nullptr) { return; } _InOrder(root->_left); cout << root->_key << " "; _InOrder(root->_right); } Node* _root = nullptr; };
Test.c:
#include "BinarySearchTree.h" void TestBSTree1() { BSTree<int> t; int arr[] = { 8, 3, 1, 10, 2, 2, 3, 6, 4, 7, 14, 13 }; for (const auto& e : arr) { t.Insert(e); } t.InOrder(); } int main() { TestBSTree1(); return 0; }
2.3 二叉搜索树的查找
二叉搜索树的查找 Find 实现很容易，用和刚才一样的思路，从根结点开始查找。
从根开始，如果要查找的值大于 cur 目前的值，则让 cur 往右走，反之往左走。
当查找得值与 cur 的值相等时则说明找到了，返回 true。
当 cur 触及到空（while 循环结束）则说明找不到，返回 false。
代码：
bool Find(const K& key) { Node* cur = _root; while (cur != nullptr) { if (key < cur->_key) { cur = cur->_left; } else if (key > cur->_key) { cur = cur->_right; } else { return true; } } return false; }
从C语言到C++_24(二叉搜索树)概念+完整代码实现+笔试题（中）：https://developer.aliyun.com/article/1521942?spm=a2c6h.13148508.setting.21.50c04f0eHmAr4x
