CC++ & Algorithm

二叉搜索树的概念与查找

困难2
语言版本：通用
概述：用图书馆找书的例子引入二叉搜索树，讲解其“左小右大”的特点和快速查找的原理，并给出C++和Python的完整实现。

二叉搜索树的概念与查找

从一个谜题开始

假设你和小明玩猜数字游戏：小明心里想了一个1到100之间的整数，你每次猜一个数，小明会告诉你“大了”还是“小了”。如果你第一次猜50，小明说“小了”，那么你马上知道答案在51到100之间；第二次猜75，小明说“大了”，范围变成51到74……这样最多猜7次就能确定答案。但如果小明不按大小提示，只回答“不对”，那你就要一个一个猜，最坏可能要100次。

这个“每次将范围减半”的聪明方法，在计算机里有一个好朋友——二叉搜索树（Binary Search Tree，简称BST）。它就像一本自动分类的“查号簿”，帮我们在一堆数据里快速找到想要的值。

1 图书馆找书的启示

想象你走进一间图书馆，里面所有书都随意堆在桌子上，想找一本《小王子》可能要翻遍整间屋子。但如果图书馆管理员按规则摆放：所有书名拼音比“小”小的书放在左边书架，比“小”大的放在右边书架，每个书架里面再继续这样分……那么你只需根据书名拼音，每次决定向左走还是向右走，很快就能找到目标。这种“分区存放、逐层缩小范围”的思想，正是二叉搜索树的灵魂。

在计算机里，二叉搜索树把数据组织成一棵树，每个节点最多有两个孩子，并且遵守一条简单规则：

  • 对于树中任意一个节点，它的左子树中所有节点的值都小于该节点的值；
  • 它的右子树中所有节点的值都大于该节点的值。

满足这个规则的二叉树就叫二叉搜索树。这里我们暂时假设所有节点的值互不相同（实际中也可以处理相等的情况，但先忽略）。

2 数据结构原理和核心思想

2.1 什么是二叉树？

回忆一下“二叉树”：它是一种每个节点最多有两个子节点的树形结构。这两个子节点分别叫左孩子和右孩子。最上面的节点叫根节点，没有子节点的节点叫叶子节点。

二叉搜索树就是在普通二叉树上加了大小顺序规则。

2.2 二叉搜索树的“搜索”原理

查找过程特别像刚才的猜数字游戏：
从根节点开始

  1. 如果目标值等于当前节点值 → 找到啦！
  2. 如果目标值小于当前节点值 → 往左子树走（因为左子树所有值都更小）
  3. 如果目标值大于当前节点值 → 往右子树走

一直重复，直到找到或者遇到空节点（说明没找到）。

每比较一次，就排除掉一半的可能区域（理想情况下）。所以查找速度非常快，平均需要比较的次数约为树的高度。如果树很平衡，高度大约是log₂(n)（n是节点个数）。比如100万个节点，最多比较20次左右，比顺序查找快几万倍！

2.3 生活中的类比

  • 查成绩：老师把全班成绩按从低到高排好，你想知道自己分数在第几？先用二分法猜中间，问“我的分数比这个高还是低？”——这就是二叉搜索树。
  • 零食价格：你有一堆零食价格标签（3元、5元、8元、12元……），想快速找到某个价格是否存在，可以按大小顺序排列，每次取中间比较。

2.4 ASCII示意图

下面是一棵二叉搜索树：

          50
         /  \
        30   70
       /  \   \
      20  40   80
     /
    10
  • 根节点50：左子树所有节点（30,20,40,10）都小于50；右子树所有节点（70,80）都大于50。
  • 节点30：左子树（20,10）都小于30；右子树（40）大于30。
  • 查找40：从50开始，40<50 → 往左到30；40>30 → 往右到40，找到！
  • 查找25：50→左到30→左到20→右？20没有右孩子，查找失败。

查找路径的长度就是树的深度。当树平衡时，深度≈log₂(n)，所以很快。

2.5 最好情况和最坏情况

  • 最好情况：树是完美平衡的，比如根节点是中间值，左右子树大小差不多。此时查找一个元素需要O(log n)次比较。
  • 最坏情况：如果插入的数据本来就是有序的（从小到大或从大到小），BST会退化成一条“链表”。比如依次插入1,2,3,4,5，树就变成：
1
 \
  2
   \
    3
     \
      4
       \
        5

这时候查找5需要5次比较，时间复杂度退化到O(n)。这就像图书馆的书虽然按大小分了，但每个书架只放一本书，反而没有效率。后面我们会学平衡树（如AVL树）来避免这种情况。

3 新手容易犯的错误

❌ 错误1：忘记递归的终止条件

// 错误示例：没有判断node为空
bool search(TreeNode* node, int x) {
    if (x == node->val) return true;   // 如果node是nullptr，这里会崩溃！
    // ...
}

改正：先判断node == nullptr，返回false。

❌ 错误2：插入时没有正确连接父节点

def insert(self, x):
    if self.root is None:
        self.root = TreeNode(x)
        return
    # 直接调用一个函数，但没有保持递归返回的节点连接
    self._insert(self.root, x)   # 错误：_insert可能改变了子树，但root没更新

改正：必须用递归返回值更新父节点的左/右指针。

❌ 错误3：认为查找一定能成功，没有处理不存在的情况

有些同学直接写return search(node->left, x);，但忘记如果node为空的情况。正确做法：如果最终node为空，返回false。

❌ 错误4：构造树时重复插入相同的值

题目中我们约定值不重复，但如果重复插入，有些实现会忽略，有些会放在左或右。最好明确约定：相等时不插入（或插入到一边）。

4 C++完整代码实现

下面用C++实现一个二叉搜索树，包含插入（为了构造树）和查找功能。

#include <iostream>
using namespace std;

// 定义树节点
struct TreeNode {
    int val;            // 节点值
    TreeNode* left;     // 左孩子指针
    TreeNode* right;    // 右孩子指针
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 二叉搜索树类
class BST {
private:
    TreeNode* root;     // 根节点指针

    // 辅助函数：向以node为根的树中插入值x，返回新的根
    TreeNode* insert(TreeNode* node, int x) {
        if (node == nullptr) {               // 如果当前节点空，创建新节点
            return new TreeNode(x);
        }
        if (x < node->val) {                 // x比当前值小，向左插入
            node->left = insert(node->left, x);
        } else if (x > node->val) {          // x比当前值大，向右插入
            node->right = insert(node->right, x);
        }
        // 如果相等，按约定不插入（避免重复）
        return node;
    }

    // 辅助函数：在以node为根的树中查找值x，返回是否找到
    bool search(TreeNode* node, int x) {
        if (node == nullptr) {               // 遇到空节点，没找到
            return false;
        }
        if (x == node->val) {                // 找到目标值
            return true;
        } else if (x < node->val) {          // 目标小于当前，向左找
            return search(node->left, x);
        } else {                             // 目标大于当前，向右找
            return search(node->right, x);
        }
    }

    // 辅助函数：销毁整棵树（释放内存）
    void destroy(TreeNode* node) {
        if (node != nullptr) {
            destroy(node->left);             // 递归销毁左子树
            destroy(node->right);            // 递归销毁右子树
            delete node;                     // 删除当前节点
        }
    }

public:
    // 构造函数，初始化空树
    BST() : root(nullptr) {}

    // 析构函数，释放所有节点
    ~BST() {
        destroy(root);
    }

    // 对外接口：插入一个值
    void insert(int x) {
        root = insert(root, x);
    }

    // 对外接口：查找一个值，返回bool
    bool search(int x) {
        return search(root, x);
    }
};

int main() {
    BST tree;
    // 构造例子中的树：50,30,70,20,40,80,10
    tree.insert(50);
    tree.insert(30);
    tree.insert(70);
    tree.insert(20);
    tree.insert(40);
    tree.insert(80);
    tree.insert(10);

    // 测试查找
    cout << "查找40: " << (tree.search(40) ? "找到" : "未找到") << endl;
    cout << "查找25: " << (tree.search(25) ? "找到" : "未找到") << endl;
    // 输出：
    // 查找40: 找到
    // 查找25: 未找到
    return 0;
}

代码说明：

  • TreeNode结构体包含val（节点值）、left（左孩子指针）、right（右孩子指针），构造函数初始化值并置空指针。
  • BST类封装根节点root，私有辅助函数用递归实现插入和查找，公有的insert和search接口供外部使用。
  • 插入时递归直到空节点，创建新节点并返回，上一层用返回的指针更新当前节点的孩子。
  • 查找时递归比较，若节点为空返回false，相等则true，否则根据大小转向。
  • 析构函数中递归删除所有节点，避免内存泄漏。

5 Python完整代码实现

Python实现更加简洁，逻辑与C++完全一致。

class TreeNode:
    """树节点"""
    def __init__(self, val):
        self.val = val          # 节点值
        self.left = None        # 左孩子
        self.right = None       # 右孩子

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

    def insert(self, x):
        """插入值x"""
        def _insert(node, x):
            if node is None:                     # 空位置，创建新节点
                return TreeNode(x)
            if x < node.val:                     # 向左走
                node.left = _insert(node.left, x)
            elif x > node.val:                   # 向右走
                node.right = _insert(node.right, x)
            # x == node.val 不做处理
            return node
        self.root = _insert(self.root, x)

    def search(self, x):
        """查找值x，返回布尔值"""
        def _search(node, x):
            if node is None:                     # 走到空节点，没找到
                return False
            if x == node.val:                    # 找到了
                return True
            elif x < node.val:                   # 小于，向左找
                return _search(node.left, x)
            else:                                # 大于，向右找
                return _search(node.right, x)
        return _search(self.root, x)

# 测试
if __name__ == "__main__":
    tree = BST()
    # 构造例子中的树：50,30,70,20,40,80,10
    for v in [50, 30, 70, 20, 40, 80, 10]:
        tree.insert(v)

    print("查找40:", "找到" if tree.search(40) else "未找到")
    print("查找25:", "找到" if tree.search(25) else "未找到")
    # 输出：
    # 查找40: 找到
    # 查找25: 未找到

Python说明：

  • 使用嵌套函数_insert和_search实现递归，避免了在类中定义额外方法。
  • 注意if __name__ == "__main__":是Python的标准测试写法。
  • 递归函数内部直接return调用自身，返回值由外层处理。

6 与二分查找的对比

二叉搜索树的查找与数组上的二分查找很相似，但有一个重要区别：

特性二分查找（数组）二叉搜索树（BST）
数据存储有序数组，连续内存树形结构，不连续内存
插入/删除需要移动大量元素，O(n)只需要修改指针，O(log n)平均
查找速度O(log n)O(log n)平均
空间需求少（只需数组）多（每个节点额外存指针）

所以，如果数据经常动态增加或删除，二叉搜索树比有序数组更灵活；如果数据基本不变，只做查找，有序数组+二分查找可能更简单高效。

7 总结要点

  • 二叉搜索树（BST） 是一种节点间有大小顺序的二叉树：左子树节点值都小于根，右子树节点值都大于根。
  • 查找 从根开始，每次比较后转向左或右，类似二分查找，平均时间复杂度O(log n)。
  • 插入 也是通过比较找到合适的空位置，创建新节点并连接。
  • 性能依赖树的形状：平衡时快，退化成链表时慢。后续学习的平衡树（AVL、红黑树）能解决这个问题。
  • 多种应用：数据库索引、集合实现、平衡树基础、表达式求值等。

8 相关指引

  • 要更深入地理解二叉搜索树，可以学习树的遍历（前序、中序、后序），中序遍历BST会得到有序序列。
  • 如果树经常倾斜，可以研究AVL树（自平衡二叉搜索树）和红黑树，它们保证查找、插入、删除都是O(log n)。
  • 对于更高级的应用，伸展树（Splay Tree） 和 Treap（树堆） 也很有趣。
  • 如果想用BST实现集合（Set）或映射（Map），可以看看C++的std::set/std::map或Python的bisect模块，底层通常用平衡树。

现在你已经掌握了二叉搜索树的核心思想——“左小右大，二分查找”。试着用它来解决一些实际问题吧，比如建立一个“同学姓名拼音查询系统”或者“零食价格检索表”。

例题精讲

1单选题

二叉搜索树的中序遍历结果具有什么特征？

A递增有序
B递减有序
C先递增后递减
D无序
2判断题

在二叉搜索树中查找一个元素的时间复杂度总是O(log n)。

3单选题

给定二叉搜索树，根节点为50，左子树包含30、20、40，右子树包含70、60、80。查找元素60时，依次比较的节点是？

A50,70,60
B50,30,40,60
C50,70,80,60
D50,30,20,60
4判断题

二叉搜索树中，左子树上所有节点的值都小于根节点的值，右子树上所有节点的值都大于根节点的值，此定义对树中任意节点都成立。

5填空题
补全二叉搜索树查找函数：
Node* search(Node* root, int key) {
    if (root == NULL || root->val == key) return root;
    if (key < root->val) return search(___ , key);
    else return search(root->right, key);
}