CC++ & Algorithm

二叉排序树（BST）：一棵会“大小排序”的树

困难4
语言版本：C++Python
概述：二叉排序树是一种特殊的二叉树，它让所有左子树的节点值都小于根，所有右子树的节点值都大于根，因此中序遍历就能得到从小到大的有序序列。

二叉排序树（BST）：一棵会“大小排序”的魔法树

你有没有试过在一堆杂乱无章的卡片里快速找到一张数字牌？如果卡片是按大小排好的，你就能很快找到。二叉排序树（也叫二叉查找树）就是一棵能自动帮数字“排队”的树——它把每个数字放到合适的位置，让小的往左走，大的往右走。这样，你只要顺着树枝比较大小，就能像玩“猜数字”游戏一样，又快又准地找到任何数字。

二叉排序树的规则——就像教室里的座位安排

想象教室里有两排座位：左边坐成绩低的同学，右边坐成绩高的同学。每个同学坐的位置都遵守一个规则：比前面同学成绩低的坐左边，比前面同学高的坐右边。二叉排序树的规则和这个一模一样：

  • 每个节点（就像每个同学）都有一个数值，我们叫它“键”（key）
  • 左子树（左边所有同学）的键都小于当前节点的键
  • 右子树（右边所有同学）的键都大于当前节点的键
  • 每个子树（左或右）本身也是一棵二叉排序树，规则递归适用

这个规则的魔法之处在于：如果你按中序遍历（先看左边所有同学，再看中间同学，最后看右边所有同学）的顺序报名字，报出来的就是按成绩从小到大排好的顺序！

为什么要用二叉排序树？——生活中的例子

例1：猜数字游戏

老师心里想了一个1~100之间的数字。你猜30，老师说“小了”；你猜70，老师说“大了”……每次猜数后，你就把范围缩小一半。二叉排序树工作方式完全相同：你从树根（相当于第一次猜的数）开始，如果目标数比根小，就只去左子树找；比根大，就去右子树找。这种“每次排除一半”的特性，让查找变得飞快。

例2：整理零花钱记录

假设你每天得到零花钱，想把它们按金额从小到大记在本子上。如果你直接把数字写在空白处，以后要想找某个金额的日期就很麻烦。但如果你用二叉排序树来存，每次拿到新钱时，和树根比一比：小的放左边，大的放右边。等存好后，只要按中序遍历，就能得到从少到多的完整列表，还能快速查找某一天有没有收到10元钱。

例3：排队买冰淇淋

同学们按身高排队买冰淇淋，如果队伍排成二叉排序树的样子（不是直线，而是一棵分叉的树），那么每个人都能在O(log n)步内找到自己的位置——比直接插队快多啦！

新手容易犯的几个错误

  1. 忘记处理重复值
    如果插入一个已有数字，有些实现会把它放在右边（等于或大于），有些会拒绝插入。实际应用中要根据需求决定：比如统计票数时，重复值应该累计计数，而不是再建一个新节点。

  2. 插入时没有递归到正确位置
    新手容易只比较了根节点，就以为“大于就放右孩子”，但右孩子可能已经存在。正确做法是：如果右孩子存在，就继续递归到右子树里；如果右孩子位置为空，才创建新节点。

  3. 中序遍历顺序混淆
    有的同学会搞成“先根、再左、再右”，这是前序遍历。要记住中序遍历是“左→根→右”，才能得到升序序列。

  4. 树退化成链表
    如果插入的数字本身已经排好序（比如依次插入1,2,3,4,5），那么所有节点都会挤到一边，树就变成一根“斜线”，查找速度直线下降。这时候就要用到平衡二叉树（如AVL树、红黑树）来纠正。

完整可运行的代码示例（更详细版）

下面我们用Python实现一个功能更完整的二叉排序树，包含插入、查找、中序遍历、以及删除节点（删除是难点，但值得了解）。代码中每行变量都加了中文注释，方便理解。

class BSTNode:
    """树节点类，每个节点代表一个数字"""
    def __init__(self, key):  # key 是存储的数字
        self.key = key        # 当前节点的值
        self.left = None      # 左孩子指针
        self.right = None     # 右孩子指针

class BinarySearchTree:
    """二叉排序树类"""
    def __init__(self):
        self.root = None  # 树根初始为空
    
    def insert(self, key):
        """插入一个新值到树中"""
        if self.root is None:
            self.root = BSTNode(key)
        else:
            self._insert_recursive(self.root, key)
    
    def _insert_recursive(self, node, key):
        """递归插入，找到正确位置"""
        if key < node.key:                # 新值比当前节点小
            if node.left is None:         # 左边空位，直接放
                node.left = BSTNode(key)
            else:                         # 左边有节点，继续往左找
                self._insert_recursive(node.left, key)
        else:                             # 新值大于等于当前节点（此处允许相等放右边）
            if node.right is None:
                node.right = BSTNode(key)
            else:
                self._insert_recursive(node.right, key)
    
    def search(self, key):
        """查找某个值是否存在，返回True/False"""
        return self._search_recursive(self.root, key)
    
    def _search_recursive(self, node, key):
        """递归查找"""
        if node is None:                  # 找到空节点，说明不存在
            return False
        if key == node.key:               # 找到了
            return True
        elif key < node.key:              # 比当前小，去左边找
            return self._search_recursive(node.left, key)
        else:                             # 比当前大，去右边找
            return self._search_recursive(node.right, key)
    
    def inorder(self):
        """中序遍历，返回从小到大排序的列表"""
        result = []
        self._inorder_recursive(self.root, result)
        return result
    
    def _inorder_recursive(self, node, result):
        """递归中序：左→根→右"""
        if node:
            self._inorder_recursive(node.left, result)
            result.append(node.key)
            self._inorder_recursive(node.right, result)
    
    def find_min(self, node):
        """找到以node为根的树的最小值（最左边节点）"""
        current = node
        while current.left:
            current = current.left
        return current
    
    def delete(self, key):
        """从树中删除指定值的节点（如果存在）"""
        self.root = self._delete_recursive(self.root, key)
    
    def _delete_recursive(self, node, key):
        """递归删除，返回删除后的新子树根"""
        if node is None:
            return None
        
        # 先找到要删除的节点
        if key < node.key:
            node.left = self._delete_recursive(node.left, key)
        elif key > node.key:
            node.right = self._delete_recursive(node.right, key)
        else:  # 找到要删除的节点
            # 情况1：没有左孩子，直接用右孩子代替
            if node.left is None:
                return node.right
            # 情况2：没有右孩子，直接用左孩子代替
            elif node.right is None:
                return node.left
            # 情况3：有两个孩子，用右子树的最小节点代替
            else:
                # 找到右子树中最小的节点
                min_node = self.find_min(node.right)
                # 把最小节点的值赋给当前节点
                node.key = min_node.key
                # 删除右子树中的那个最小节点
                node.right = self._delete_recursive(node.right, min_node.key)
        return node

# ---------- 使用示例 ----------
# 模拟一个班级的考试成绩：小明、小红、小刚等人的分数
scores = [85, 70, 95, 60, 75, 90, 100, 65, 80]
bst = BinarySearchTree()

print("插入分数：", scores)
for s in scores:
    bst.insert(s)

print("中序遍历结果（从小到大）：", bst.inorder())
# 输出：[60, 65, 70, 75, 80, 85, 90, 95, 100]

# 查找
print("查找 75 分是否在树里：", bst.search(75))   # True
print("查找 99 分是否在树里：", bst.search(99))   # False

# 删除一个节点
print("\n删除 70 分...")
bst.delete(70)
print("删除后中序遍历：", bst.inorder())
# 输出：[60, 65, 75, 80, 85, 90, 95, 100]  （70被删掉了）

# 再插入一个新分数
print("\n插入 77 分...")
bst.insert(77)
print("插入后中序遍历：", bst.inorder())
# 输出：[60, 65, 75, 77, 80, 85, 90, 95, 100]

思考题：你能用二叉排序树解决吗？

  1. 找最接近的数：给你一棵已经建好的二叉排序树，如何找到树中与某个目标值最接近的数？（提示：比较沿途节点与目标值的差，记录最小差值）
  2. 检查两棵二叉树是否相同：如果两棵树的形状和每个节点的值都一模一样，它们就是相同的。如何用中序遍历来判断？（注意：只靠中序遍历的顺序相同不能保证树相同，因为不同的树可能有相同的中序序列）
  3. 用中序遍历判断二叉排序树是否正确：如果一棵二叉树的中序遍历结果是递增的，那么它一定是一棵二叉排序树吗？答案是不一定——因为中序遍历只保证数值顺序，但不保证子树间的结构关系。需要额外检查每个节点的值是否比左子树所有值大、比右子树所有值小。

相关指引——学完这个，下一步学什么？

  • 平衡二叉树（AVL树）：让树的高度始终接近log N，解决“斜线”性能下降问题。适合追求稳定效率的场景。
  • 红黑树：一种更实用的平衡树，STL的map和set底层就用它。规则比AVL稍宽松，但插入删除性能更好。
  • 堆（Heap）：另一种特殊树，用来快速找到最大或最小值（比如优先级队列），但不是有序的。
  • B树/B+树：用在数据库和文件系统中，每个节点可以存多个值，减少磁盘读写次数。

要记住：二叉排序树是所有高级树结构的基础。把它的插入、查找、删除、遍历搞熟练，后面学平衡树就会轻松很多。

例题精讲

1单选题

二叉排序树（BST）中，中序遍历得到的序列是什么？

A递增有序序列
B递减有序序列
C无序序列
D随机序列
2判断题

在二叉排序树中，若某个节点只有左子树，则该节点的值一定大于其所有左子树节点的值。

3填空题
完成以下Python函数，实现向二叉排序树中插入一个节点。
class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def insert(root, data):
    if root is None:
        return TreeNode(data)
    if ___:
        root.left = insert(root.left, data)
    else:
        root.right = insert(root.right, data)
    return root
4单选题

在二叉排序树中，删除一个既有左子树又有右子树的节点时，通常的做法是：

A直接删除该节点，将左子树接到父节点
B直接删除该节点，将右子树接到父节点
C用该节点的前驱节点（左子树中的最大值）或后继节点（右子树中的最小值）替换该节点
D用该节点的父节点替换
5判断题

二叉排序树查找操作的时间复杂度在平均情况下为O(log n)，在最坏情况下为O(n)。