15、递归与树：二叉搜索树的查找、插入、删除（递归实现）

树结构，尤其是二叉搜索树，是我个人在C语言项目中用得最多的数据结构之一。为什么？因为它把递归的优雅展现得淋漓尽致。你想想看，一棵树的每个节点，本身又是一棵子树的根——这种自相似性，天然就是递归的舞台。

今天我们就来聊聊，怎么用递归搞定二叉搜索树的三个核心操作：查找、插入、删除。我会结合自己踩过的坑，给你讲明白。

二叉搜索树长什么样？

先简单回顾一下。二叉搜索树（BST）有个关键性质：

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

说白了，就是中序遍历能得到一个递增序列。这个性质，让查找变得极其高效。

下面我用一张图帮你理清递归操作的整体脉络：

先定义节点结构

写代码之前，先把数据结构定下来。我习惯这样定义：

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

嗯，这里要注意，左右指针必须初始化成 NULL。我在项目中见过有人忘了初始化，结果递归时访问野指针，程序直接崩了。

递归查找：最直观的操作

查找的逻辑其实很简单。给定一个值，从根开始比较：

• 相等？找到了，返回节点指针。
• 小于当前节点？去左子树找。
• 大于当前节点？去右子树找。
• 走到 NULL？说明不存在，返回 NULL。

代码写出来是这样的：

TreeNode* search(TreeNode *root, int target) {
    if (root == NULL) {
        return NULL;  // 没找到
    }
    
    if (target == root->data) {
        return root;  // 找到了
    } else if (target < root->data) {
        return search(root->left, target);  // 去左边找
    } else {
        return search(root->right, target); // 去右边找
    }
}

你看，整个函数只有 10 行左右。递归的威力就在这里——逻辑清晰，代码简洁。

递归插入：在正确的位置种下新节点

插入操作和查找很像。区别在于：查找是「找到了就返回」，插入是「找到了空位就放进去」。

具体思路：

1. 如果当前节点是 NULL，说明找到空位了，创建新节点返回。
2. 如果要插入的值小于当前节点，递归插入到左子树。
3. 如果要插入的值大于当前节点，递归插入到右子树。
4. 如果相等？嗯，这取决于你的设计。我一般不允许重复值，直接返回原节点。

TreeNode* insert(TreeNode *root, int value) {
    if (root == NULL) {
        TreeNode *newNode = (TreeNode*)malloc(sizeof(TreeNode));
        newNode->data = value;
        newNode->left = NULL;
        newNode->right = NULL;
        return newNode;
    }
    
    if (value < root->data) {
        root->left = insert(root->left, value);
    } else if (value > root->data) {
        root->right = insert(root->right, value);
    }
    // 相等时什么都不做，或者你可以选择覆盖
    
    return root;
}

这里有个关键点：递归调用的返回值要赋值给对应的子指针。为什么？因为当子树根节点发生变化时（比如子树为空时创建了新节点），父节点需要更新它的指向。

我曾经犯过一个错误：写了 insert(root->left, value); 却忘了接收返回值。结果插了半天，树一点没变。排查了好久才发现这个低级错误。

递归删除：最复杂的操作

删除操作是二叉搜索树里最麻烦的。为什么？因为删除一个节点后，你还得保持二叉搜索树的性质。

删除分三种情况：

情况	描述	处理方法
情况一	被删除节点是叶子节点（没有子节点）	直接删除，返回 NULL
情况二	被删除节点只有一个子节点	用子节点替换它
情况三	被删除节点有两个子节点	找右子树的最小节点（或左子树的最大节点）替换它

代码实现：

TreeNode* deleteNode(TreeNode *root, int target) {
    if (root == NULL) {
        return NULL;
    }
    
    // 先找到要删除的节点
    if (target < root->data) {
        root->left = deleteNode(root->left, target);
    } else if (target > root->data) {
        root->right = deleteNode(root->right, target);
    } else {
        // 找到了！处理三种情况
        
        // 情况一：叶子节点
        if (root->left == NULL && root->right == NULL) {
            free(root);
            return NULL;
        }
        
        // 情况二：只有一个子节点
        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 *minNode = root->right;
        while (minNode->left != NULL) {
            minNode = minNode->left;
        }
        // 用最小节点的值替换当前节点
        root->data = minNode->data;
        // 删除右子树中的那个最小节点
        root->right = deleteNode(root->right, minNode->data);
    }
    
    return root;
}

一个完整的例子

光说不练假把式。我们来跑一个完整的例子：

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

// ... 上面定义的 TreeNode 结构体和三个函数 ...

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

int main() {
    TreeNode *root = NULL;
    int values[] = {50, 30, 70, 20, 40, 60, 80};
    
    // 插入
    for (int i = 0; i < 7; i++) {
        root = insert(root, values[i]);
    }
    
    printf("中序遍历: ");
    inorder(root);  // 输出: 20 30 40 50 60 70 80
    printf("\n");
    
    // 查找
    TreeNode *found = search(root, 40);
    if (found) {
        printf("找到了: %d\n", found->data);
    }
    
    // 删除
    root = deleteNode(root, 50);
    printf("删除50后: ");
    inorder(root);  // 输出: 20 30 40 60 70 80
    printf("\n");
    
    return 0;
}

运行结果：

中序遍历: 20 30 40 50 60 70 80
找到了: 40
删除50后: 20 30 40 60 70 80

递归的代价与取舍

递归虽然优雅，但也不是没有代价的。每次递归调用都会消耗栈空间。如果树的高度很大（比如退化成链表），递归深度可能达到 n，导致栈溢出。

我个人在实际项目中的经验是：

• 如果树是平衡的（高度约 log n），递归完全没问题。
• 如果树可能退化成链表（比如插入有序数据），我会考虑用迭代实现，或者引入平衡机制（如 AVL 树、红黑树）。

不过话说回来，作为学习阶段，递归实现能帮你更好地理解树的结构。等你把递归思想吃透了，再去看迭代实现，会发现其实都是相通的。

好了，这一章的内容就到这里。代码你可以直接拿去跑，有问题欢迎交流。

---

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