编辑“︁C 语言二叉搜索树”︁

{{DISPLAYTITLE:C语言二叉搜索树}}

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

== 基本概念 ==
二叉搜索树是一种[[二叉树]]，其中每个节点最多有两个子节点（左子节点和右子节点），并满足以下性质：
* 对于任意节点，其'''左子树'''中的所有节点的值都'''小于'''该节点的值。
* 其'''右子树'''中的所有节点的值都'''大于'''该节点的值。
* 左右子树也必须是二叉搜索树。

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

=== 示例结构 ===
<mermaid>
graph TD
    8((8)) --> 3((3))
    8 --> 10((10))
    3 --> 1((1))
    3 --> 6((6))
    6 --> 4((4))
    6 --> 7((7))
    10 --> 14((14))
    14 --> 13((13))
</mermaid>
上图展示了一个典型的BST，其中根节点为8，左子树的所有节点值均小于8，右子树的所有节点值均大于8。

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

=== 节点结构定义 ===
<syntaxhighlight lang="c">
typedef struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;
</syntaxhighlight>

=== 插入操作 ===
插入操作需遵循BST的排序规则：
<syntaxhighlight lang="c">
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;
}
</syntaxhighlight>

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

=== 查找操作 ===
查找操作利用BST的排序特性进行高效搜索：
<syntaxhighlight lang="c">
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);
}
</syntaxhighlight>

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

<syntaxhighlight lang="c">
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;
}
</syntaxhighlight>

== 遍历方法 ==
BST支持三种主要遍历方式：
* '''中序遍历'''（In-order）：按升序输出节点。
* '''前序遍历'''（Pre-order）：根节点优先。
* '''后序遍历'''（Post-order）：根节点最后。

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

'''输出示例'''（对前述树结构中序遍历）：
<pre>1 3 4 6 7 8 10 13 14</pre>

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

=== 案例：单词频率统计 ===
以下程序使用BST统计文本中单词的出现频率：
<syntaxhighlight lang="c">
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;
}
</syntaxhighlight>

== 性能分析 ==
* '''最佳情况'''：树完全平衡，高度为<math>\lfloor \log_2 n \rfloor</math>，操作时间复杂度为<math>O(\log n)</math>。
* '''最坏情况'''：树退化为链表（如插入已排序数据），时间复杂度为<math>O(n)</math>。

解决方案：使用[[AVL树]]或[[红黑树]]等自平衡二叉搜索树。

== 练习题目 ==
1. 实现BST的非递归插入算法。
2. 编写函数计算BST的高度。
3. 扩展BST结构，使其支持重复值存储。

== 总结 ==
二叉搜索树是C语言中高效组织动态数据的重要工具。通过本章学习，您应掌握其核心操作及实际应用场景。进阶学习可转向更复杂的平衡树结构或[[哈希表]]实现。

[[Category:编程语言]]
[[Category:C]]
[[Category:C 语言高级数据结构]]