1. 二叉搜索树相关概念
二叉搜索树（Binary Search Tree）满足下列条件：
- 对于根节点，左子树中所有节点的值 < 根节点的值 < 右子树中所有节点的值
- 任意节点的左、右子树也是二叉搜索树，同样满足条件 1
2. 二叉搜索树的操作
我们将二叉搜索树封装为一个类 BSTree，并声明一个 _root 变量，指向树的根节点。
2.1 查找节点
给定目标 val，声明一个节点 cur，从二叉搜索树的根节点 _root 出发，循环比较 cur->_key 和 val 之间的大小关系：
- 若
val < cur->_key，说明目标节点在cur的左子树，执行cur = cur->_left - 若
val > cur->_key，说明目标节点在cur的右子树，执行cur = cur->_right - 若
val == cur->_key，说明找到目标节点，跳出循环并返回该节点
与二分查找原理一致，每轮排除一半的情况，当二叉树平衡时，循环次数最多为二叉树的高度，时间复杂度为 O(log n)。
// 查找节点
Node* find(const K& val) {
Node* cur = _root;
while (cur) {
if (val < cur->_key) cur = cur->_left;
else if (val > cur->_key) cur = cur->_right;
else break;
}
return cur;
}
2.2 插入节点
给定一个待插入元素 val，为了保持左子树 < 根节点 < 右子树的性质，插入流程如下：
- 查找插入位置： 与查找操作相同逻辑，从根节点出发，根据当前节点值和
val的大小关系循环向下搜索，直到越过叶子节点（遍历到nullptr）跳出循环 - 在该位置插入节点：
new一个新节点，将新节点置于nullptr的位置
注意：
- 二叉搜索树不允许存在重复节点，否则将违反其定义。因此，若待插入节点在树中已存在，则不执行插入，直接返回。
- 为了实现插入节点，我们需要借助节点
pre保存上一轮循环的节点。这样在遍历至nullptr时，我们可以获取到其父节点，从而完成节点插入操作。
bool insert( K& val) {
(_root == ) {
Node* newNode = (val);
_root = newNode;
;
}
Node* cur = _root;
Node* curPre = ;
(cur) {
(val == cur->_key) ;
(val < cur->_key) {
curPre = cur;
cur = cur->_left;
} {
curPre = cur;
cur = cur->_right;
}
}
Node* newNode = (val);
(curPre->_left == cur) curPre->_left = newNode;
curPre->_right = newNode;
;
}
