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

= C语言二叉树 =

'''二叉树'''（Binary Tree）是C语言中一种重要的'''非线性数据结构'''，由节点（Node）和边（Edge）组成，每个节点最多有两个子节点（左子节点和右子节点）。它在算法设计、数据库索引、编译器实现等领域有广泛应用。

== 基本概念 ==
二叉树具有以下特性：
* 每个节点包含：数据域、左子节点指针、右子节点指针
* 根节点（Root）是树的起始节点
* 叶子节点（Leaf）是没有子节点的节点
* 深度（Depth）指从根到某节点的最长路径长度
* 高度（Height）是树中节点的最大深度

<mermaid>
graph TD
    A((根节点)) --> B((左子节点))
    A --> C((右子节点))
    B --> D((左子节点))
    B --> E((右子节点))
    C --> F((左子节点))
    D --> G((叶子节点))
    E --> H((叶子节点))
    F --> I((叶子节点))
</mermaid>

== 二叉树节点结构 ==
在C语言中，二叉树节点通常用结构体表示：

<syntaxhighlight lang="c">
struct TreeNode {
    int data;               // 数据域
    struct TreeNode* left;  // 左子节点指针
    struct TreeNode* right; // 右子节点指针
};
</syntaxhighlight>

== 二叉树操作 ==

=== 创建节点 ===
<syntaxhighlight lang="c">
struct TreeNode* createNode(int value) {
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    if (newNode != NULL) {
        newNode->data = value;
        newNode->left = NULL;
        newNode->right = NULL;
    }
    return newNode;
}
</syntaxhighlight>

=== 插入节点 ===
以下是一个简单的二叉搜索树插入示例：
<syntaxhighlight lang="c">
void insertNode(struct TreeNode** root, int value) {
    if (*root == NULL) {
        *root = createNode(value);
        return;
    }
    
    if (value < (*root)->data) {
        insertNode(&(*root)->left, value);
    } else {
        insertNode(&(*root)->right, value);
    }
}
</syntaxhighlight>

=== 遍历二叉树 ===
二叉树有三种基本遍历方式：

{| class="wikitable"
|+ 遍历方式比较
|-
! 遍历类型 !! 顺序 !! 应用场景
|-
| 前序遍历 || 根→左→右 || 复制树结构
|-
| 中序遍历 || 左→根→右 || 获取有序序列
|-
| 后序遍历 || 左→右→根 || 删除树结构
|}

'''前序遍历'''示例：
<syntaxhighlight lang="c">
void preOrderTraversal(struct TreeNode* root) {
    if (root != NULL) {
        printf("%d ", root->data);  // 访问根节点
        preOrderTraversal(root->left);
        preOrderTraversal(root->right);
    }
}
</syntaxhighlight>

== 特殊二叉树类型 ==

=== 完全二叉树 ===
除最后一层外，其他层节点都达到最大值，且最后一层节点从左向右填充。

数学性质：对于深度为<math>k</math>的完全二叉树：
* 节点总数范围：<math>2^{k-1} \leq n \leq 2^k - 1</math>
* 第<math>i</math>个节点的子节点位置：左子节点=<math>2i+1</math>，右子节点=<math>2i+2</math>

=== 二叉搜索树（BST） ===
满足以下条件：
* 左子树所有节点值 < 根节点值
* 右子树所有节点值 > 根节点值
* 左右子树也都是BST

查找时间复杂度：平均<math>O(\log n)</math>，最坏<math>O(n)</math>（退化为链表时）

== 实际应用案例 ==

'''案例1：文件系统目录结构'''
操作系统常用二叉树组织文件目录，每个节点代表一个目录或文件：
* 数据域：文件名/目录名
* 左指针：第一个子目录/文件
* 右指针：同级下一个目录/文件

'''案例2：表达式树'''
编译器将算术表达式转换为二叉树：
* 叶子节点：操作数
* 内部节点：运算符
* 中序遍历得到中缀表达式
* 后序遍历可用于计算表达式值

<mermaid>
graph TD
    *((*)) --> +((+))
    * --> /((/))
    + --> a((a))
    + --> b((b))
    / --> c((c))
    / --> d((d))
</mermaid>
对应表达式：<math>(a + b) * (c / d)</math>

== 常见问题与解决方案 ==

'''问题1：内存泄漏'''
忘记释放二叉树节点会导致内存泄漏。解决方案：
<syntaxhighlight lang="c">
void freeTree(struct TreeNode* root) {
    if (root == NULL) return;
    freeTree(root->left);
    freeTree(root->right);
    free(root);
}
</syntaxhighlight>

'''问题2：平衡性问题'''
二叉搜索树可能退化为链表。解决方案：使用AVL树或红黑树等自平衡二叉树。

== 进阶练习 ==
1. 实现计算二叉树高度的函数
2. 编写检查二叉树是否为BST的函数
3. 实现二叉树的层序遍历（使用队列）

通过系统学习二叉树，您将掌握处理层次化数据的重要技能，为学习更复杂的树结构（如B树、堆等）奠定基础。

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