在日常数据查找中，我们常常会遇到“如何快速找到目标”的问题。比如在通讯录里找一个联系人，或者在字典里查一个单词。如果数据是无序的，我们可能需要逐个检查，效率很低；如果数据是有序的，虽然可以用二分查找（O(log n)），但需要预先排序。有没有一种数据结构，既能保持有序，又能在插入和查找时保持高效呢？答案就是二叉搜索树（Binary Search Tree，简称BST）。
一、什么是二叉搜索树？¶
二叉搜索树是一种特殊的二叉树，它的每个节点包含以下特性：
- 每个节点最多有左、右两个子节点（左子树和右子树）。
- 对于任意一个节点，左子树中所有节点的值都小于该节点的值。
- 右子树中所有节点的值都大于该节点的值。
举个例子，我们可以构建一个简单的二叉搜索树：
5
/ \
3 7
/ \ / \
2 4 6 8
这里根节点是5，左子树的所有值（2、3、4）都小于5，右子树的所有值（6、7、8）都大于5。每个子节点也遵循同样的规则，比如3的左子树是2（<3），右子树是4（>3）；7的左子树是6（<7），右子树是8（>7）。
二、为什么二叉搜索树能高效查找？¶
普通的数组查找（无序）需要逐个检查，时间复杂度是O(n)；有序数组可以用二分查找（O(log n)），但插入新元素时需要移动大量数据。而二叉搜索树通过“左小右大”的规则，每次查找可以排除一半的节点，因此查找效率稳定在O(log n)。
为什么能排除一半节点？因为每次比较后，目标值要么小于当前节点，要么大于当前节点，要么等于。如果小于，就只需要在左子树继续；如果大于，就只需要在右子树继续。这就像在一本按字母排序的字典里查单词，你会先翻到中间页，比较首字母后，要么去左半本，要么去右半本，而不是一页页翻。
三、二叉搜索树的查找过程（核心）¶
查找一个目标值的步骤非常直观，我们可以用“比较-递归缩小范围”的思路实现：
- 从根节点开始，将目标值与当前节点的值比较。
- 如果目标值 等于 当前节点值：找到目标，返回当前节点。
- 如果目标值 小于 当前节点值：目标一定在左子树中，递归查找左子树。
- 如果目标值 大于 当前节点值：目标一定在右子树中，递归查找右子树。
- 如果子树为空（即找不到目标），返回空或提示“未找到”。
举个例子：查找目标值4¶
假设我们有上面的二叉搜索树：
5
/ \
3 7
/ \ / \
2 4 6 8
- 第一步：从根节点5开始，目标4 < 5 → 进入左子树（根为3）。
- 第二步：当前节点是3，目标4 > 3 → 进入右子树（根为4）。
- 第三步：当前节点是4，目标4 = 4 → 找到目标，返回4。
整个过程中，我们只检查了3个节点（5→3→4），而不是遍历7个节点，效率大大提升！
四、如何用代码实现查找？¶
1. 递归实现（直观易懂）¶
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def search_bst(root, target):
# 递归终止条件：节点为空或找到目标
if root is None or root.val == target:
return root
# 目标小于当前节点，递归左子树
elif target < root.val:
return search_bst(root.left, target)
# 目标大于当前节点，递归右子树
else:
return search_bst(root.right, target)
2. 迭代实现（用循环代替递归）¶
def search_bst_iterative(root, target):
current = root
while current is not None:
if current.val == target:
return current
elif target < current.val:
current = current.left
else:
current = current.right
return None # 未找到
五、总结¶
二叉搜索树通过“左小右大”的结构特性，让查找过程每次排除一半节点，从而实现高效查找（O(log n)）。核心步骤是：从根节点开始，比较目标值与当前节点值，递归缩小到左/右子树继续查找。
需要注意的是，如果二叉搜索树“不平衡”（比如所有节点都在左子树，退化成链表），查找效率会退化为O(n)。但只要构建时保持平衡（如后续学习的红黑树、AVL树），就能稳定保持O(log n)的效率。
下次遇到需要快速查找的场景时，不妨想想二叉搜索树的“按规则缩小范围”思路，它就像为数据结构安装了“导航系统”，让查找变得高效而有序！