CC++ & Algorithm

二叉搜索树

困难2
语言版本：C++
概述：二叉搜索树是一种特殊二叉树，所有左子树节点小于根，所有右子树节点大于根，查找和插入都很快。

二叉搜索树：像查字典一样快速查找数据

什么是二叉搜索树？

你有没有玩过“猜数字”游戏？朋友心里想一个1到100之间的数，你每次猜一个数，他会告诉你“大了”或“小了”。按照这个策略，你最多只需要猜7次就能找到答案（因为每次猜中间的数）。二叉搜索树（Binary Search Tree，简称BST）就是按照这种思想设计的一种二叉树：每个节点都满足：左子树中所有节点的值 < 根节点的值 < 右子树中所有节点的值。这样一来，查找、插入数据时，每次都能根据大小关系排除掉一半的节点，效率非常高。

想象你有一本无序的字典，要找单词“hello”，你只能一页一页翻；但如果字典是按字母顺序排列的，你就可以先翻到中间，根据字母大小决定往左翻还是往右翻——这就是二叉搜索树的核心思路。

二叉搜索树的关键概念

1. 节点结构

每个节点包含三个部分：一个数据值（比如整数）、一个指向左子树的指针、一个指向右子树的指针。在C++中，我们通常用结构体或类来表示：

struct TreeNode {
    int val;                 // 节点的值
    TreeNode* left;          // 左子树指针
    TreeNode* right;         // 右子树指针
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} // 构造函数
};

2. 左小右大的规则

这是BST的“铁律”：

  • 对于任意节点，其左子树中所有节点的值都小于该节点的值。
  • 右子树中所有节点的值都大于该节点的值。
  • 左右子树自身也是BST。

例如，插入数字序列 {50, 30, 80, 20, 40, 70, 90, 10, 35} 后，得到的树结构如下（你可以用手画一画）：

        50
       /  \
     30    80
    /  \   / \
   20  40 70  90
  /     /
10    35

注意：35比40小，所以放在40的左子树上；比30大，所以又放在30的右子树里。每次比较都遵循规则。

3. 查找操作（Search）

查找一个值的过程就像是玩“猜数字”的缩小范围版：

  1. 从根节点开始。
  2. 如果当前节点为空，说明没找到，结束。
  3. 如果目标值等于当前节点的值，找到！返回。
  4. 如果目标值小于当前节点的值，则继续在左子树中查找。
  5. 如果目标值大于当前节点的值，则继续在右子树中查找。

生活例子：班级里有全班同学的《学生信息表》（姓名和学号），表格按学号从小到大排列。你想找学号为325的同学，你会先翻到中间某页，如果看到学号400，因为325<400，你往前面（左侧）翻；如果看到学号300，因为325>300，你往后面（右侧）翻，直到找到为止。

代码实现（递归方式）：

// 在二叉搜索树中查找目标值，返回是否找到
bool search(TreeNode* root, int target) {
    if (root == nullptr) return false;      // 空树或走到了空位置，没找到
    if (target == root->val) return true;   // 找到了
    if (target < root->val)                 // 小于当前节点，往左找
        return search(root->left, target);
    else                                    // 大于当前节点，往右找
        return search(root->right, target);
}

也可以改成非递归（循环）方式，更省空间：

bool search(TreeNode* root, int target) {
    TreeNode* cur = root;   // 当前节点指针
    while (cur != nullptr) {
        if (target == cur->val) return true;
        if (target < cur->val) cur = cur->left;
        else cur = cur->right;
    }
    return false;
}

4. 插入操作（Insert）

插入一个值，本质就是沿着树“往下走”，直到找到一个空位（左子树或右子树为nullptr），然后把新节点挂上去。注意：如果树中已经有相同值的节点，一般选择不插入（去重），或者插入到另一侧（由需求决定）。本篇文章沿用“去重”做法。

步骤：

  1. 如果树为空，直接创建新节点作为根。
  2. 否则，从根开始比较：
    • 如果插入值小于当前节点值，往左子树走。
    • 如果插入值大于当前节点值，往右子树走。
    • 如果相等，不插入（或根据需求处理）。
  3. 走到空位置时，创建新节点并连接。

生活例子：还是那个《学生信息表》，现在转来一位新同学，学号是310。你需要在表格中找到合适的位置插入他的信息。你会从中间开始比较：如果当前页学号是350，310<350，所以往前翻；如果当前页是300，310>300，就往后翻……直到找到一页空位（或者插在合适的两页之间）。

递归实现：

// 向二叉搜索树中插入一个值，返回新的根节点（可能不变）
TreeNode* insert(TreeNode* root, int value) {
    if (root == nullptr) {                        // 空位置，创建新节点
        return new TreeNode(value);
    }
    if (value < root->val) {                      // 小于当前节点，插入左子树
        root->left = insert(root->left, value);
    } else if (value > root->val) {               // 大于当前节点，插入右子树
        root->right = insert(root->right, value);
    }
    // 等于时不插入（去重）
    return root;
}

注意：递归时一定要将返回值赋给对应的子树指针（如 root->left = insert(...)），否则新节点不会真正连接到树上。

5. 删除操作（更复杂，了解即可）

删除节点时，需要考虑被删除节点的子节点情况：

  • 叶子节点（没有孩子）：直接删除，父节点对应指针设为nullptr。
  • 只有一个孩子：用孩子节点替换掉被删除节点。
  • 有两个孩子：通常用右子树中最小的节点（或左子树中最大的节点）替换被删除节点，然后删除那个用来替换的节点。

因为删除逻辑较复杂，在CSP-J考试中很少直接考实现，但理解原理有助于深入认识BST。

生活中的更多例子

  • 图书管理：图书馆的书按索书号（字母+数字）排列。你要找“TP312.8C”，先找到T类区域，再找TP31，再找TP312……每一步缩小范围。
  • 手机通讯录：联系人按名字拼音排序。你要找“张三”，会先翻到Z开头，再找“zhang”，再找“张三”。
  • 电脑文件系统：文件夹的层次结构也是一种树，但并不是BST，因为文件排序不依靠大小关系。

中序遍历：把树变成有序序列

BST有一个非常棒的属性：中序遍历（左-根-右）会得到一个升序序列。这是因为遍历时先访问左子树（所有较小值），然后访问根，最后访问右子树（所有较大值）。

例如上面构建的BST，中序遍历输出：

10 20 30 35 40 50 70 80 90

这正好是插入数字从小到大排列的结果。利用这个特点，BST可以用来对一组数进行排序（插入后中序遍历）。

// 中序遍历，打印节点的值
void inorder(TreeNode* root) {
    if (root == nullptr) return;        // 空节点直接返回
    inorder(root->left);                // 递归遍历左子树
    cout << root->val << " ";           // 访问当前节点
    inorder(root->right);               // 递归遍历右子树
}

常见错误提醒（新手必看！）

❌ 错误1：递归时忘记连接新节点

// 错误写法
void insert(TreeNode* root, int value) {
    if (root == nullptr) {
        root = new TreeNode(value);    // 只改变了局部指针，没有影响到调用者
        return;
    }
    if (value < root->val) insert(root->left, value);
    else insert(root->right, value);
}

正确做法：函数返回新根节点，并赋值给父节点的左/右指针，如前面的代码所示。

❌ 错误2：没有处理重复值

插入时如果遇到相等值，要明确处理方法。大多数情况下我们直接忽略（不插入），否则会导致树中出现相等的值，破坏BST的定义（“大于”和“小于”的严格性丢失）。

❌ 错误3：查找时没有判断空指针

在递归中，如果当前节点为空，必须返回 false，否则访问 root->val 会引发程序崩溃。

❌ 错误4：混淆“左子树中所有节点”与“左孩子”

错误理解：认为只要左孩子的值小于根节点，右孩子的值大于根节点就行。实际上，左子树中所有节点（包括左孩子的右子树等）都必须小于根节点。比如下图就不是BST：

    5
   / \
  2   8
 / \
1   7   ← 7大于5，但7在左子树中，违反规则！

❌ 错误5：忘记释放内存（动态分配）

代码中用 new 创建的节点，在程序结束前最好用 delete 释放，否则会造成内存泄漏。但在竞赛题中，通常题目只要求实现功能，内存泄漏一般不计入扣分，但作为良好的编程习惯，应该注意。

完整可运行代码示例（含注释）

下面是一个完整的程序，包含插入、查找、中序遍历，并且对每个变量定义都写了中文注释：

#include <iostream>
using namespace std;

// 二叉搜索树的节点结构体
struct TreeNode {
    int val;                 // 节点存储的值
    TreeNode* left;          // 左子树指针
    TreeNode* right;         // 右子树指针
    // 构造函数：初始化值为x，左右指针置为空
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 插入节点（递归）
// 参数：root - 当前子树的根节点指针，value - 要插入的值
// 返回值：更新后的根节点指针
TreeNode* insert(TreeNode* root, int value) {
    if (root == nullptr) {                      // 如果当前节点为空，创建新节点
        return new TreeNode(value);
    }
    if (value < root->val) {                    // 插入值小于当前节点，往左子树插入
        root->left = insert(root->left, value);
    } else if (value > root->val) {             // 插入值大于当前节点，往右子树插入
        root->right = insert(root->right, value);
    }
    // 如果相等，不插入（去重）
    return root;                                // 返回（可能不变的）根节点
}

// 查找节点，返回是否找到
// 参数：root - 根节点指针，target - 要查找的目标值
bool search(TreeNode* root, int target) {
    if (root == nullptr) return false;          // 空树或跑到了空位置，没找到
    if (target == root->val) return true;       // 找到了
    if (target < root->val)                     // 比当前节点小，往左走
        return search(root->left, target);
    else                                        // 比当前节点大，往右走
        return search(root->right, target);
}

// 中序遍历，输出升序序列
// 参数：root - 当前子树的根节点指针
void inorder(TreeNode* root) {
    if (root == nullptr) return;                // 空节点直接返回
    inorder(root->left);                        // 先遍历左子树
    cout << root->val << " ";                   // 打印当前节点的值
    inorder(root->right);                       // 再遍历右子树
}

// 主函数：演示BST的插入与查找
int main() {
    TreeNode* root = nullptr;                   // 初始化根节点为空（空树）

    // 要插入的数字数组
    int values[] = {50, 30, 80, 20, 40, 70, 90, 10, 35};
    int n = sizeof(values) / sizeof(values[0]); // 数组长度

    // 循环插入每个数字
    for (int i = 0; i < n; i++) {
        root = insert(root, values[i]);         // 插入后更新根节点（根节点可能改变）
    }

    // 输出中序遍历结果
    cout << "中序遍历结果: ";
    inorder(root);
    cout << endl;

    // 测试查找功能
    cout << "查找35: " << (search(root, 35) ? "找到" : "未找到") << endl;
    cout << "查找100: " << (search(root, 100) ? "找到" : "未找到") << endl;

    // 额外测试：查找10、50、0
    cout << "查找10: " << (search(root, 10) ? "找到" : "未找到") << endl;
    cout << "查找50: " << (search(root, 50) ? "找到" : "未找到") << endl;
    cout << "查找0: " << (search(root, 0) ? "找到" : "未找到") << endl;

    return 0;
}

运行输出：

中序遍历结果: 10 20 30 35 40 50 70 80 90
查找35: 找到
查找100: 未找到
查找10: 找到
查找50: 找到
查找0: 未找到

效率分析：为什么BST很快？

  • 平均时间复杂度：对于一棵高度平衡的BST，查找、插入操作的时间复杂度为 O(log n)，其中n是节点个数。因为每次比较都能排除一半的节点，树的高度大约为 log₂(n)。
  • 最坏情况：如果插入的数据已经是单调递增或递减的（比如1,2,3,4,5），BST会退化成一条直线（即链表），此时高度为n，查找时间变成 O(n)。为了避免这种情况，诞生了平衡二叉搜索树（如AVL树、红黑树），它们能在插入时自动调整树的结构，保持高度接近log n。

相关知识点指引

  1. 平衡二叉搜索树（AVL树）：自动保持左右子树高度差不超过1，保证O(log n)性能。
  2. 红黑树：一种近似平衡的二叉搜索树，C++标准库中的 map、set 就是用红黑树实现的。
  3. 堆（Heap）：另一种树形结构，但“左小右大”的规则不同，堆的根节点是最大/最小值。
  4. 二叉树遍历：前序、中序、后序、层序，是理解树的基础。
  5. 递归与分治：BST的很多操作天然适合用递归实现，是学习递归的好素材。

掌握了二叉搜索树，你就打开了一扇通往高效存储和查找世界的大门。试试用代码模拟一遍插入和查找过程，画出树的结构，你会更加理解它的魅力！

例题精讲

1单选题

已知一棵二叉搜索树的先序遍历序列为 {5, 3, 2, 4, 7, 6, 8}，则该树的中序遍历序列是以下哪一项？

A{2, 3, 4, 5, 6, 7, 8}
B{5, 3, 2, 4, 7, 6, 8}
C{2, 4, 3, 6, 8, 7, 5}
D{8, 7, 6, 5, 4, 3, 2}
2单选题

在二叉搜索树中删除一个既有左孩子又有右孩子的节点时，通常采用以下哪种替代策略？

A用左子树的最小节点替换
B用右子树的最大节点替换
C用左子树的最大节点或右子树的最小节点替换
D用父节点替换
3判断题

在二叉搜索树中，值最小的节点一定没有右孩子。

4判断题

在二叉搜索树中插入一个新节点时，新节点总是被添加为叶子节点。

5填空题
以下函数用于在二叉搜索树中查找是否存在值为key的节点。补全代码。

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

bool search(TreeNode* root, int key) {
    if (___①___) {
        return false;
    }
    if (root->val == key) {
        return true;
    } else if (key < root->val) {
        return ___②___;
    } else {
        return ___③___;
    }
}