第十章 二叉搜索树：从理论到实战

二叉搜索树，简称 BST。说实话，这是我在工作中用得最多的数据结构之一。无论是做嵌入式系统的快速查找，还是做算法题的底层优化，BST 都是绕不开的基础。

今天我就带你彻底搞懂它。从定义到操作，从代码到性能，咱们一步步来。

什么是二叉搜索树？

先看定义。二叉搜索树是一棵二叉树，每个节点最多有两个孩子。但它有个特殊性质：

  • 左子树上所有节点的值，都小于根节点的值
  • 右子树上所有节点的值，都大于根节点的值
  • 左右子树也分别是二叉搜索树

说白了，就是中序遍历的结果是一个递增序列。这个性质非常有用。

核心要点：BST 的每个节点都满足「左小右大」。这是所有操作的基础。

BST 的知识体系

下面这张图，是我自己总结的 BST 知识框架。你一看就明白。

二叉搜索树 BST 定义 左小右大，递归结构 查找 二分思想，O(log n) 插入 找到空位，挂上去 删除 三种情况，最复杂 性能分析 平均 O(log n)，最坏 O(n) C语言实现 结构体定义 + 递归/迭代实现 ⚠ 常见坑：递归栈溢出、指针丢失、内存泄漏

查找操作

查找是 BST 最基础的操作。思路很简单：从根开始，比当前节点小就往左走，大就往右走，相等就找到了。

我个人习惯用递归实现，代码更清晰。但如果你对栈深度有要求，迭代版本更安全。

// 递归查找
TreeNode* bst_search(TreeNode* root, int key) {
    if (root == NULL || root->val == key) {
        return root;
    }
    if (key < root->val) {
        return bst_search(root->left, key);
    } else {
        return bst_search(root->right, key);
    }
}

// 迭代查找（推荐在嵌入式场景使用）
TreeNode* bst_search_iter(TreeNode* root, int key) {
    while (root != NULL && root->val != key) {
        if (key < root->val) {
            root = root->left;
        } else {
            root = root->right;
        }
    }
    return root;
}

我的经验：在嵌入式项目中，我一般用迭代版本。因为递归会消耗栈空间，而嵌入式系统的栈通常很小。有一次我在一个 STM32 项目里用递归，结果深度超过 100 层就栈溢出了。从那以后，我养成了「能用迭代就不用递归」的习惯。

插入操作

插入其实就是在查找的基础上，找到合适的位置挂上去。如果树是空的，直接新建节点。否则，比大小决定往左还是往右。

TreeNode* bst_insert(TreeNode* root, int key) {
    if (root == NULL) {
        TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
        node->val = key;
        node->left = node->right = NULL;
        return node;
    }
    
    if (key < root->val) {
        root->left = bst_insert(root->left, key);
    } else if (key > root->val) {
        root->right = bst_insert(root->right, key);
    }
    // 如果相等，什么也不做（或者根据需求覆盖）
    return root;
}

你想想看，插入操作的时间复杂度是多少？其实就是查找的时间复杂度。平均 O(log n)，最坏 O(n)。

注意：插入时如果 key 已经存在，不同场景处理方式不同。有的要求去重，有的要求计数。我在做数据库索引时，一般选择计数方式，保留重复值。

删除操作

删除是 BST 里最复杂的操作。为什么？因为删除一个节点后，还要保持 BST 的性质不变。

删除分三种情况：

  • 情况一：删除叶子节点。直接删掉就行，父节点指向 NULL。
  • 情况二：删除只有一个孩子的节点。让孩子顶替它的位置。
  • 情况三：删除有两个孩子的节点。这个最麻烦，需要找前驱或后继来替换。

前驱就是左子树中最大的节点，后继就是右子树中最小的节点。我一般用后继，因为代码写起来顺手。

// 找最小值节点（用于删除操作）
TreeNode* find_min(TreeNode* root) {
    while (root->left != NULL) {
        root = root->left;
    }
    return root;
}

TreeNode* bst_delete(TreeNode* root, int key) {
    if (root == NULL) return NULL;
    
    if (key < root->val) {
        root->left = bst_delete(root->left, key);
    } else if (key > root->val) {
        root->right = bst_delete(root->right, key);
    } else {
        // 找到了要删除的节点
        // 情况一：叶子节点
        if (root->left == NULL && root->right == NULL) {
            free(root);
            return NULL;
        }
        // 情况二：只有一个孩子
        else if (root->left == NULL) {
            TreeNode* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            TreeNode* temp = root->left;
            free(root);
            return temp;
        }
        // 情况三：有两个孩子
        else {
            TreeNode* successor = find_min(root->right);
            root->val = successor->val;
            root->right = bst_delete(root->right, successor->val);
        }
    }
    return root;
}

避坑指南：我曾经在删除操作中忘记释放内存，导致内存泄漏。在嵌入式系统中，内存泄漏是致命问题。每次 free 之后，最好把指针置为 NULL，防止野指针。

性能分析

BST 的性能取决于树的高度。理想情况下，树是平衡的，高度为 O(log n)。最坏情况下，树退化成链表，高度为 O(n)。

操作 平均时间复杂度 最坏时间复杂度
查找 O(log n) O(n)
插入 O(log n) O(n)
删除 O(log n) O(n)
中序遍历 O(n) O(n)

为什么会退化？如果你按递增顺序插入数据，BST 就变成了一条右斜链。比如插入 1, 2, 3, 4, 5，树就长成了只有右孩子的链表。

为了解决这个问题，就有了平衡二叉树，比如 AVL 树和红黑树。这些是 BST 的进阶版本，后面章节会讲。

我的建议：如果你确定数据是随机分布的，普通 BST 完全够用。但如果数据有序或接近有序，一定要用平衡树。我在做日志系统时，时间戳是递增的，用普通 BST 直接崩了，换成 AVL 树才解决问题。

完整代码示例

下面是一个完整的 BST 实现，包含创建、插入、查找、删除和中序遍历。

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

TreeNode* create_node(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = node->right = NULL;
    return node;
}

TreeNode* insert(TreeNode* root, int val) {
    if (root == NULL) return create_node(val);
    if (val < root->val)
        root->left = insert(root->left, val);
    else if (val > root->val)
        root->right = insert(root->right, val);
    return root;
}

TreeNode* search(TreeNode* root, int val) {
    while (root && root->val != val) {
        if (val < root->val) root = root->left;
        else root = root->right;
    }
    return root;
}

TreeNode* find_min(TreeNode* root) {
    while (root->left) root = root->left;
    return root;
}

TreeNode* delete_node(TreeNode* root, int val) {
    if (root == NULL) return NULL;
    
    if (val < root->val)
        root->left = delete_node(root->left, val);
    else if (val > root->val)
        root->right = delete_node(root->right, val);
    else {
        if (root->left == NULL) {
            TreeNode* temp = root->right;
            free(root);
            return temp;
        }
        if (root->right == NULL) {
            TreeNode* temp = root->left;
            free(root);
            return temp;
        }
        TreeNode* temp = find_min(root->right);
        root->val = temp->val;
        root->right = delete_node(root->right, temp->val);
    }
    return root;
}

void inorder(TreeNode* root) {
    if (root == NULL) return;
    inorder(root->left);
    printf("%d ", root->val);
    inorder(root->right);
}

int main() {
    TreeNode* root = NULL;
    int arr[] = {5, 3, 7, 2, 4, 6, 8};
    for (int i = 0; i < 7; i++)
        root = insert(root, arr[i]);
    
    printf("中序遍历: ");
    inorder(root);
    printf("\n");
    
    root = delete_node(root, 5);
    printf("删除5后: ");
    inorder(root);
    printf("\n");
    
    return 0;
}

运行结果：

中序遍历: 2 3 4 5 6 7 8 
删除5后: 2 3 4 6 7 8

嗯，到这里 BST 的核心内容就讲完了。记住三个关键点：左小右大的定义、递归的思维方式、以及删除操作的三种情况。把这些搞明白，后面的平衡树学起来就轻松多了。

公众号:蓝海资料掘金营，微信deep3321

← 上一章 📖 返回目录 下一章 →