1. 二叉搜索树相关概念
如下图所示，二叉搜索树 (binary search tree) 满足下列条件：
- 对于根节点，左子树中所有节点的值 < 根节点的值 < 右子树中所有节点的值
- 任意节点的左、右子树也是二叉搜索树，同样满足条件 1
而下图就不是二叉搜索树。
2. 二叉搜索树的操作
我们将二叉搜索树封装为一个类 BSTree，并声明一个 _root 变量，指向树的根节点。
// 节点类
template<class K>
struct BSTNode {
BSTNode<K>* _left;
BSTNode<K>* _right;
K _key;
// 构造
BSTNode(const K& val):_left(nullptr),_right(nullptr),_key(val){}
};
// 二叉搜索树类
template<class K>
class BSTree {
public:
typedef BSTNode<K> Node;
private:
Node* _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(logn)。
// 查找节点
Node* find(const K& val) {
Node* cur = _root;
while(cur) {
if(val < cur->_key) cur = cur->_left;
else (val > cur->_key) cur = cur->_right;
;
}
cur;
}
