二叉排序树：查找、插入与删除

二叉排序树，也叫二叉搜索树，是数据结构里一个非常经典的结构。说白了，它就是一棵二叉树，但每个节点都守着一个规矩：左子树所有节点的值都比根小，右子树所有节点的值都比根大。这个规矩，让查找、插入、删除都变得特别高效。

我个人习惯把二叉排序树想象成一个“有序的档案柜”。你想想看，如果你要在一堆乱序的纸堆里找一份文件，那得翻到什么时候？但如果你把所有文件按字母顺序排好，找起来就快多了。二叉排序树干的就是这个事。

1. 二叉排序树的查找

查找是二叉排序树最基础的操作。过程很简单：从根节点开始，如果目标值比当前节点小，就往左走；比当前节点大，就往右走；相等，就找到了。

我在项目中遇到过一个问题：用递归实现查找，代码虽然简洁，但树很深的时候容易栈溢出。所以我建议，能用循环就别用递归。来看代码：

// 二叉排序树节点定义
typedef struct BSTNode {
    int key;
    struct BSTNode *lchild, *rchild;
} BSTNode, *BSTree;

// 查找 - 非递归实现
BSTNode* BST_Search(BSTree T, int key) {
    while (T != NULL && key != T->key) {
        if (key < T->key)
            T = T->lchild;
        else
            T = T->rchild;
    }
    return T;
}

2. 二叉排序树的插入

插入操作其实就是在查找的基础上，找到合适的位置把新节点挂上去。如果树里已经有相同关键字的节点，我一般选择不插入——这取决于你的业务需求，但大多数场景下，二叉排序树不允许重复键值。

嗯，这里要注意：插入的新节点一定是叶子节点。你想想看，我们一路查找下去，直到某个空指针的位置，那就是新节点的家。

// 插入 - 递归实现（简洁但注意栈深度）
int BST_Insert(BSTree &T, int key) {
    if (T == NULL) {
        T = (BSTNode*)malloc(sizeof(BSTNode));
        T->key = key;
        T->lchild = T->rchild = NULL;
        return 1;  // 插入成功
    }
    else if (key == T->key)
        return 0;  // 已存在，不插入
    else if (key < T->key)
        return BST_Insert(T->lchild, key);
    else
        return BST_Insert(T->rchild, key);
}

3. 二叉排序树的删除

删除是二叉排序树里最麻烦的操作。为什么？因为删掉一个节点后，你还得保证剩下的树依然满足“左小右大”的规矩。根据被删节点的孩子情况，分三种场景：

• 叶子节点：直接删掉，父节点对应的指针置空。
• 只有左孩子或只有右孩子：让孩子顶替自己的位置。
• 既有左孩子又有右孩子：这个最麻烦。我的做法是：找到右子树中最小的节点（或者左子树中最大的节点），用它来替换被删节点，然后删除那个用来替换的节点。

为什么选右子树的最小节点？因为它比被删节点的所有左子树节点都大，又比被删节点的所有右子树节点都小，完美符合规矩。

// 删除 - 核心逻辑
int BST_Delete(BSTree &T, int key) {
    if (T == NULL) return 0;  // 没找到
    
    if (key < T->key)
        return BST_Delete(T->lchild, key);
    else if (key > T->key)
        return BST_Delete(T->rchild, key);
    else {
        // 找到了要删除的节点
        BSTNode *q;
        if (T->lchild == NULL) {
            // 只有右孩子或无孩子
            q = T;
            T = T->rchild;
            free(q);
        } else if (T->rchild == NULL) {
            // 只有左孩子
            q = T;
            T = T->lchild;
            free(q);
        } else {
            // 左右孩子都在：找右子树最小节点
            q = T->rchild;
            while (q->lchild != NULL) q = q->lchild;
            T->key = q->key;  // 替换值
            BST_Delete(T->rchild, q->key);  // 删除那个最小节点
        }
        return 1;
    }
}

4. 知识体系总览

下面这张图，把二叉排序树的核心操作串起来了。我建议你多看几遍，理解每个操作之间的关联。

5. 性能对比与总结

最后，我把二叉排序树的三种操作做个对比。你写代码的时候，心里要有这张表：

操作	平均时间复杂度	最坏时间复杂度	空间复杂度	实现难度
查找	O(log n)	O(n)	O(1) 迭代 / O(log n) 递归	简单
插入	O(log n)	O(n)	O(1) 迭代 / O(log n) 递归	简单
删除	O(log n)	O(n)	O(1) 迭代 / O(log n) 递归	中等

说实话，二叉排序树是很多高级树结构的基础。你把它吃透了，后面学AVL树、红黑树、B树都会轻松很多。我个人建议你多动手写代码，尤其是删除操作，光看是看不明白的，必须亲手调试几遍才能理解那个“替换再删除”的精髓。

---