在日常數據查找中，我們常常會遇到“如何快速找到目標”的問題。比如在通訊錄裏找一個聯繫人，或者在字典裏查一個單詞。如果數據是無序的，我們可能需要逐個檢查，效率很低；如果數據是有序的，雖然可以用二分查找（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)的效率。
下次遇到需要快速查找的場景時，不妨想想二叉搜索樹的“按規則縮小範圍”思路，它就像爲數據結構安裝了“導航系統”，讓查找變得高效而有序！