CC++ & Algorithm

二叉排序树：一本会自动排序的字典

较难9
语言版本：C++Python
概述：二叉排序树是一种特殊的二叉树，左子树所有节点值小于根节点，右子树所有节点值大于根节点，可以快速查找数据。

二叉排序树：一本会自动排序的字典

想象你有一本没有页码的字典，里面每个单词都按照字母顺序放好：左半边全是字母A开头的，右半边全是字母Z开头的，而根目录是中间的一个单词。这样你要找一个单词，先比较根，如果比根小就往左翻，比根大就往右翻，每次都能排除一半——这就是二叉排序树的思想。

二叉排序树（也叫二叉搜索树）是一种特殊的二叉树，它能让我们像查字典一样快速地找到数据。无论是插入新数据、查找已存在的数据，还是删除数据，它都能高效完成——只要树长得比较“平衡”。

二叉排序树的规则

二叉排序树必须满足以下四条规则，就像一本书的索引必须按顺序排列一样：

  1. 每个节点有一个关键值（比如整数、字母等）。
  2. 左子树的所有节点值都小于根节点值。
  3. 右子树的所有节点值都大于根节点值。
  4. 左子树和右子树自身也必须是二叉排序树（递归要求）。

举个例子：假设根节点是50，左子树上所有节点（比如20、30、40）都小于50，右子树上所有节点（60、70、80）都大于50。而左子树的根节点30，它的左边（20）更小，右边（40）更大，同样满足规则。

生活中的例子：班主任老师按身高给全班同学排座位。最高的同学站在中间（根），比他矮的站在左边，比他高的站在右边。然后左边那一列的同学再按同样规则分左右两边……这样老师想找一个特定身高的同学，每次只要比较一下当前同学的身高，就知道往左边还是右边找，非常快！这就像二叉排序树的过程。

插入操作：把新词放进正确的位置

插入新节点时，我们从根节点开始比较。规则是：

  • 如果新值小于当前节点，就往左走；
  • 如果新值大于当前节点，就往右走；
  • 如果遇到空位置（nullptr），就把新节点放进去。

这个过程就像在字典里插入一个新单词：先找到它应该在哪个字母分区，再在里面按顺序找到空位放好。

// 插入节点函数，返回新的树根（因为可能插入空树）
BSTNode* insert(BSTNode* root, int val) {
    if (root == nullptr) {                     // 如果树为空，创建新节点
        return new BSTNode(val);
    }
    if (val < root->data) {                    // 比根小，去左子树
        root->left = insert(root->left, val);
    } else if (val > root->data) {             // 比根大，去右子树
        root->right = insert(root->right, val);
    }
    // 如果相等，什么也不做（本代码不允许重复值）
    return root;
}

注意：如果插入重复值，有的实现会忽略，有的会放在左边或右边。通常二叉排序树不包含重复元素，否则查找时可能找到任意一个，影响正确性。

查找操作：像二分查找一样快

查找一个值的过程和插入非常类似：从根开始，比较目标值与当前节点值，如果相等就找到了；如果目标值小，去左子树；如果大，去右子树；如果走到空节点还没找到，说明不存在。

// 查找函数，找到返回true，否则false
bool search(BSTNode* root, int val) {
    if (root == nullptr) return false;        // 空树或走到空节点，没找到
    if (root->data == val) return true;       // 找到了
    if (val < root->data)                     // 比根小，去左子树找
        return search(root->left, val);
    else                                      // 比根大，去右子树找
        return search(root->right, val);
}

这个查找过程每次都能排除一半的节点（如果树是平衡的），所以查找速度非常快——就像二分查找一样。例如在100万个有序数字中找某个数，最多只需要比较 log⁡21000000≈20\log_2 1000000 \approx 20 次。

删除操作（进阶了解）

删除节点稍微复杂一点，但在六级知识中可以作为扩展了解。删除有三种情况：

  1. 要删除的是叶子节点（没有子节点）：直接删除，把父节点指向它的指针设为nullptr。
  2. 要删除的节点只有一个孩子：用这个孩子代替它（让父节点直接指向它的孩子）。
  3. 要删除的节点有两个孩子：通常用左子树中最大的节点，或者右子树中最小的节点替换它，然后删除那个被替换的节点。

中序遍历：让树变成排序列表

二叉排序树有一个特别有用的性质：对它进行中序遍历（左-根-右），就能得到从小到大的有序序列。因为左子树都小于根，根小于右子树，中序遍历先访问左子树，再根，最后右子树，自然就是升序。

// 中序遍历，输出节点值
void inorder(BSTNode* root) {
    if (root == nullptr) return;
    inorder(root->left);                // 先左
    cout << root->data << " ";          // 再根
    inorder(root->right);               // 最后右
}

如果把上面的示例树中序遍历，会输出：20 30 40 50 60 70 80，正好是升序排列。

常见错误（新手容易踩的坑）

  1. 左子树和右子树的比较方向搞反：有些人记成左大右小，结果查找永远找不到正确的值。记住左小右大（或者按题目要求，也可能是左大右小，但必须一致）。
  2. 忘记处理空树（root == nullptr）：在插入或查找时，如果不先判断空情况直接访问 root->data，程序会崩溃。
  3. 插入重复值没有处理：如果允许重复，查找时可能找到的是哪个？通常用 <= 或 >= 决定方向，但这样树会变得不平衡。更常见的做法是直接忽略重复值（如本示例代码）。
  4. 递归时没有正确更新左右子节点：比如写 insert(root->left, val); 但没把返回值赋给 root->left，这样新节点插入了但跟原树没连上。
  5. 忘记释放内存：在C++中，手动new出来的节点最后需要用delete释放，否则会造成内存泄漏。当然在简单示例中不释放问题不大，但在实际项目里一定要记得。

完整可运行示例

下面是一个完整的程序，包含插入、查找、中序遍历，并且展示了查找一个不存在的值的情况。

#include <iostream>
using namespace std;

// 二叉树节点结构体
struct BSTNode {
    int data;             // 节点存储的数值
    BSTNode* left;        // 左子节点指针
    BSTNode* right;       // 右子节点指针
    BSTNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

// 插入节点函数
BSTNode* insert(BSTNode* root, int val) {
    if (root == nullptr) {
        return new BSTNode(val);        // 空位置，插入新节点
    }
    if (val < root->data) {
        root->left = insert(root->left, val);   // 往左子树插
    } else if (val > root->data) {
        root->right = insert(root->right, val); // 往右子树插
    }
    // val == root->data 时不做任何事（不重复插入）
    return root;
}

// 查找函数
bool search(BSTNode* root, int val) {
    if (root == nullptr) return false;         // 没找到
    if (root->data == val) return true;        // 找到了
    if (val < root->data)
        return search(root->left, val);        // 去左边找
    else
        return search(root->right, val);       // 去右边找
}

// 中序遍历（输出升序结果）
void inorder(BSTNode* root) {
    if (root == nullptr) return;
    inorder(root->left);               // 先左子树
    cout << root->data << " ";         // 输出当前节点
    inorder(root->right);              // 再右子树
}

int main() {
    BSTNode* root = nullptr;           // 初始化空树

    // 插入一系列数值
    root = insert(root, 50);
    root = insert(root, 30);
    root = insert(root, 70);
    root = insert(root, 20);
    root = insert(root, 40);
    root = insert(root, 60);
    root = insert(root, 80);

    // 中序遍历看看是否有序
    cout << "中序遍历结果：";
    inorder(root);
    cout << endl;

    // 查找存在的值
    int x = 60;
    if (search(root, x))
        cout << x << " 找到了" << endl;
    else
        cout << x << " 没找到" << endl;

    // 查找不存在的值
    int y = 55;
    if (search(root, y))
        cout << y << " 找到了" << endl;
    else
        cout << y << " 没找到" << endl;

    return 0;
}

运行结果：

中序遍历结果：20 30 40 50 60 70 80
60 找到了
55 没找到

相关知识点指引

如果你已经掌握了二叉排序树，还可以继续学习这些相关内容：

  • 二叉树遍历：前序、中序、后序、层序遍历，都能用递归或非递归实现。
  • 平衡二叉树（AVL树、红黑树）：普通的二叉排序树在极端情况（比如插入有序数据）下会退化成链表，查找速度变慢。平衡树能自动调整形状，保持查找效率。
  • 二叉排序树的应用：C++ STL中的 std::set 和 std::map 通常用红黑树实现，就是二叉排序树的升级版。
  • 堆排序与二叉堆：另一种特殊树结构，用于优先队列和排序。

最后，不妨自己动手试试：把上述代码中的插入顺序改为“20, 30, 40, 50, 60, 70, 80”（完全升序），然后中序遍历看看结果，但你会发现这棵树长得像一根棍子（只有右孩子），查找效率就变成了O(n)！这就是为什么需要平衡树的原因。

例题精讲

1单选题

在二叉排序树中查找一个元素时，其平均查找长度主要取决于什么？

A树的结点数
B树的形状
C树的高度
D树的叶结点数
2判断题

对一棵二叉排序树进行中序遍历，可以得到一个递增有序的序列。

3填空题
以下函数实现在二叉排序树中插入一个结点。请补充代码：\nstruct TreeNode { int val; TreeNode *left, *right; };\nvoid insert(TreeNode* &root, int x) {\n    if (root == nullptr) {\n        root = new TreeNode;\n        root->val = x;\n        root->left = root->right = nullptr;\n        return;\n    }\n    if (x < root->val) ___;\n    else if (x > root->val) ___;\n}