C 语言二叉搜索树

二叉搜索树（Binary Search Tree，BST）是C语言中一种重要的高级数据结构，它结合了链表的动态性和数组的快速查找特性。本章节将详细介绍BST的原理、实现方法、操作及应用场景，适合从初学者到进阶开发者学习。

基本概念[编辑 | 编辑源代码]

二叉搜索树是一种二叉树，其中每个节点最多有两个子节点（左子节点和右子节点），并满足以下性质：

对于任意节点，其左子树中的所有节点的值都小于该节点的值。
其右子树中的所有节点的值都大于该节点的值。
左右子树也必须是二叉搜索树。

这一特性使得BST在查找、插入和删除操作中具有较高的效率（平均时间复杂度为 $O (\log n)$ ，最坏情况下为 $O (n)$ ）。

示例结构[编辑 | 编辑源代码]

上图展示了一个典型的BST，其中根节点为8，左子树的所有节点值均小于8，右子树的所有节点值均大于8。

C语言实现[编辑 | 编辑源代码]

以下是BST的基本结构定义及核心操作的C语言实现。

节点结构定义[编辑 | 编辑源代码]

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

插入操作[编辑 | 编辑源代码]

插入操作需遵循BST的排序规则：

TreeNode* insert(TreeNode *root, int value) {
    if (root == NULL) {
        TreeNode *newNode = (TreeNode*)malloc(sizeof(TreeNode));
        newNode->data = value;
        newNode->left = 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;
}

输入/输出示例：

插入序列：8, 3, 10, 1, 6, 14, 4, 7, 13
生成的树结构与上述Mermaid图表一致。

查找操作[编辑 | 编辑源代码]

查找操作利用BST的排序特性进行高效搜索：

TreeNode* search(TreeNode *root, int value) {
    if (root == NULL || root->data == value) {
        return root;
    }
    if (value < root->data) {
        return search(root->left, value);
    }
    return search(root->right, value);
}

删除操作[编辑 | 编辑源代码]

删除操作需处理三种情况： 1. 节点无子节点：直接删除。 2. 节点有一个子节点：用子节点替代。 3. 节点有两个子节点：用右子树的最小节点替代当前节点。

TreeNode* delete(TreeNode *root, int value) {
    if (root == NULL) return root;
    if (value < root->data) {
        root->left = delete(root->left, value);
    } else if (value > root->data) {
        root->right = delete(root->right, value);
    } else {
        // 情况1或2
        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;
        }
        // 情况3
        TreeNode *temp = root->right;
        while (temp->left != NULL) temp = temp->left;
        root->data = temp->data;
        root->right = delete(root->right, temp->data);
    }
    return root;
}

遍历方法[编辑 | 编辑源代码]

BST支持三种主要遍历方式：

中序遍历（In-order）：按升序输出节点。
前序遍历（Pre-order）：根节点优先。
后序遍历（Post-order）：根节点最后。

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

输出示例（对前述树结构中序遍历）：

1 3 4 6 7 8 10 13 14

实际应用案例[编辑 | 编辑源代码]

1. 数据库索引：BST用于加速数据检索（如B树的变种）。 2. 字典实现：存储键值对并支持快速查询。 3. 游戏引擎：管理场景中的对象层级。

案例：单词频率统计[编辑 | 编辑源代码]

以下程序使用BST统计文本中单词的出现频率：

typedef struct WordNode {
    char word[50];
    int count;
    struct WordNode *left, *right;
} WordNode;

WordNode* insertWord(WordNode *root, const char *word) {
    if (root == NULL) {
        WordNode *newNode = (WordNode*)malloc(sizeof(WordNode));
        strcpy(newNode->word, word);
        newNode->count = 1;
        newNode->left = newNode->right = NULL;
        return newNode;
    }
    int cmp = strcmp(word, root->word);
    if (cmp < 0) {
        root->left = insertWord(root->left, word);
    } else if (cmp > 0) {
        root->right = insertWord(root->right, word);
    } else {
        root->count++;
    }
    return root;
}