二叉搜索树 - CSP-J | C++ & Algorithm 编程研习社

二叉搜索树：让查找像猜数字一样快

你有没有玩过“猜数字”游戏？朋友心里想一个1到100之间的数，你每次猜一个数，他会告诉你“大了”还是“小了”。你每次都能排除一半的可能性，最多猜7次就能找到答案。二叉搜索树（BST）就是计算机里的一种“猜数字”结构，它把数据组织成一棵二叉树，让查找、插入和删除都变得非常高效，就像在有序表中进行二分查找一样。

想象你有一书架的书，为了快速找到某本书，你按书名的首字母排序：A开头的放左边，Z开头的放右边。每本书的位置都遵循一个规则：左边的书都比它小，右边的书都比它大。这就是二叉搜索树的基本思想——对于树中的每个节点，左子树所有节点的值都小于该节点的值，右子树所有节点的值都大于该节点的值。注意，这个规则对树中的每一个节点都成立，不仅仅是根节点。

一、什么是二叉搜索树？

二叉搜索树首先是一棵二叉树（每个节点最多有两个子节点），并且所有节点满足上述的“左小右大”性质。比如下图中，根节点是8，它的左子树（3,1,6,4,7）全部小于8，右子树（10,14,13）全部大于8。每个节点自己也是这样：节点3的左边（1）小于3，右边（6,4,7）大于3，但4和7又比6小/大？注意，节点6的左边（4）小于6，右边（7）大于6，完全满足。

        8
       / \
      3   10
     / \    \
    1   6    14
       / \   /
      4   7 13

这种“左小右大”的性质让查找变得非常简单：从根出发，如果目标值小于当前节点，就往左走；如果大于，就往右走；如果相等，就找到了。这个过程中，每走一步就能排除一半的节点（近似），所以查找速度非常快，平均时间复杂度和二分查找一样，是O(log n)。当然，如果树长得歪歪扭扭（比如插入顺序本来就排好序），查找会退化成链表O(n)，但那是后面要学的平衡树解决的问题。

二、查找过程详解

我们可以把查找看作在树中“走迷宫”，迷宫的规则就是比较大小。假设要查找上图中的数字6：

从根节点8开始，8 > 6，所以往左走。
到达节点3，3 < 6，所以往右走。
到达节点6，6 == 6，找到了！

只用了3步，而树中共有9个节点。如果换成线性查找（比如数组），最坏要比较9次。如果树更大，差距会更明显。

如果查找一个不存在的数，比如9：

根8 < 9，往右到10。
10 > 9，往左到？10的左孩子是空（图中10只有右孩子14，左孩子为空），所以没找到。

查找结束，返回False。

下面是一个生活例子：老师让同学们按照学号排队，学号小的站左边，大的站右边。现在老师想找学号15的同学，她就从队伍最前面的同学（比如学号1）开始问，学号1说“我后面比我大的往右边”，老师不断比较，最后找到。这就是现实中的“二叉搜索”。

三、插入操作详解

插入和查找非常相似，也是从根开始比较，只不过当遇到空位置时，就把新节点放进去。注意，二叉搜索树不允许重复值（通常约定），如果插入的值已经存在，可以忽略或者计数。

比如在刚才的树中插入数字5：

根8 > 5，往左到3。
3 < 5，往右到6。
6 > 5，往左。6的左孩子是4，不是空，继续比较。
4 < 5，往右。4的右孩子是空，所以把5挂在4的右边。

过程就像在适当的位置“扎个洞”，把新数据放进去。插入不会破坏树的结构（只要遵循规则），所以实现起来也很简单。

四、删除操作（了解即可）

删除稍微复杂，初学阶段重点掌握查找和插入就行。但简单提一下：删除一个节点时要考虑三种情况：

节点是叶子（没有孩子）：直接删掉。
节点只有一个孩子：让孩子顶替它的位置。
节点有两个孩子：需要从右子树中找最小的节点（或者左子树中最大的节点）来替换它，然后删除那个最小的节点。

举个例子，删除上面树中的节点3（有两个孩子），可以找右子树中最小的节点4（或者左子树中最大的节点1）来替换3，然后删除原来的4或1。这个过程需要保持树的性质不变。

五、新手最容易犯的错误

忘记处理重复值：插入时如果遇到相等值，不能直接覆盖（除非你想替换），通常应该忽略或计数。如果继续递归往左或往右，会导致无限循环或逻辑错误。
插入时没有更新父节点指针：尤其是在递归写法中，容易忘记把新节点连接到父节点的左边还是右边。迭代写法中要小心用cur指向当前节点，当找到空位时，要区分是左孩子还是右孩子。
查找时忘记比较等于的情况：死循环在while里，只判断小于和大于，没有等于时的break或return。
树为空时直接访问根节点：插入第一个节点时，要特殊处理，让self.root = new_node。
对树的形状没有概念：如果插入顺序是升序（如1,2,3,4...），树会退化成一条直线，查找变慢。这是二叉搜索树的一个缺陷，后面可以通过平衡树来改善。

六、完整可运行的示例代码

下面代码不仅包含插入和查找，还加入了中序遍历（可以按升序输出所有节点），方便验证树的结构是否正确。代码中变量用简短英文单词，每行变量定义写中文注释。

class BSTNode:
    """二叉搜索树节点"""
    def __init__(self, val):
        self.val = val          # 节点的值
        self.left = None        # 左子节点
        self.right = None       # 右子节点

class BinarySearchTree:
    """二叉搜索树类"""
    def __init__(self):
        self.root = None        # 树的根节点

    def insert(self, val):
        """插入一个值（迭代实现）"""
        new_node = BSTNode(val) # 创建新节点
        if self.root is None:   # 如果树为空
            self.root = new_node
            return
        cur = self.root          # 从根开始
        while True:
            if val < cur.val:    # 比当前节点小，往左
                if cur.left is None:
                    cur.left = new_node
                    break
                else:
                    cur = cur.left
            elif val > cur.val:  # 比当前节点大，往右
                if cur.right is None:
                    cur.right = new_node
                    break
                else:
                    cur = cur.right
            else:                # 值已存在，不重复插入
                break

    def search(self, val):
        """查找一个值，存在返回True，否则False"""
        cur = self.root
        while cur:
            if val == cur.val:
                return True
            elif val < cur.val:
                cur = cur.left
            else:
                cur = cur.right
        return False

    def inorder_traversal(self, node, result_list):
        """中序遍历（左-根-右），结果存入result_list（升序）"""
        if node is None:
            return
        self.inorder_traversal(node.left, result_list)
        result_list.append(node.val)
        self.inorder_traversal(node.right, result_list)

    def print_sorted(self):
        """打印所有节点的值（升序）"""
        result = []
        self.inorder_traversal(self.root, result)
        print("升序排列:", result)

# ---------- 测试 ----------
bst = BinarySearchTree()
# 插入一系列数字
test_values = [8, 3, 10, 1, 6, 14, 4, 7, 13]
for v in test_values:
    bst.insert(v)

print("查找6:", bst.search(6))   # 输出 True
print("查找9:", bst.search(9))   # 输出 False
bst.print_sorted()               # 输出升序排列: [1, 3, 4, 6, 7, 8, 10, 13, 14]

# 尝试插入重复值（不会改变树）
bst.insert(6)
bst.print_sorted()               # 仍然 [1,3,4,6,7,8,10,13,14]

你可以自己运行这段代码，看看结果。试着想一想，如果插入顺序是[1,2,3,4,5]，树会变成什么样子？用print_sorted依然能输出正确顺序，但查找速度会变慢，因为树长成了一根直线。

七、相关知识点指引

二叉搜索树是很多高级树结构的基石。理解了它之后，你可以继续学习：

平衡二叉树（AVL）：自动保持树的左右子树高度差不超过1，避免退化成链表。
红黑树：一种近似平衡的二叉搜索树，常用于C++ STL的map和set。
树的各种遍历：前序、中序、后序、层序遍历，对解决不同问题很有用。
二叉搜索树的应用：实现集合、映射、字典等数据结构，也用于表达式解析、文件系统的目录结构等。

如果你对CSP-J考试来说，需要重点掌握二叉搜索树的查找和插入，以及中序遍历可以得到升序序列这个特点。记住，二叉搜索树的核心思想就是“左小右大”，所有操作都围绕这个规则展开。

例题精讲