编辑“︁C 语言树基础”︁

= C语言树基础 =

树（Tree）是计算机科学中一种重要的非线性数据结构，广泛应用于各种算法和系统中。在C语言中，树可以通过指针和结构体来实现。本章将详细介绍树的基本概念、实现方式以及实际应用。

== 树的基本概念 ==

树是由节点（Node）组成的层次结构，具有以下特点：
* 每个树有一个'''根节点'''（Root Node），它是树的起点。
* 除根节点外，每个节点有且仅有一个'''父节点'''（Parent Node）。
* 节点可以有零个或多个'''子节点'''（Child Node）。
* 没有子节点的节点称为'''叶节点'''（Leaf Node）。
* 节点之间的连接称为'''边'''（Edge）。

树的常见术语：
* '''深度'''（Depth）：从根节点到该节点的边数。
* '''高度'''（Height）：从该节点到最远叶节点的边数。
* '''度'''（Degree）：节点的子节点数量。

<mermaid>
graph TD
    A((A)) --> B((B))
    A --> C((C))
    B --> D((D))
    B --> E((E))
    C --> F((F))
    D --> G((G))
    D --> H((H))
</mermaid>

上图展示了一棵树，其中：
* A是根节点
* D、E、G、H、F是叶节点
* B的度是2（D和E）
* G的深度是3（A→B→D→G）
* A的高度是3（最长路径到G或H）

== 树的C语言实现 ==

在C语言中，树通常用结构体和指针实现。以下是二叉树（每个节点最多有两个子节点）的基本实现：

<syntaxhighlight lang="c">
#include <stdio.h>
#include <stdlib.h>

// 定义树节点结构
struct TreeNode {
    int data;               // 节点数据
    struct TreeNode* left;  // 左子节点指针
    struct TreeNode* right; // 右子节点指针
};

// 创建新节点
struct TreeNode* createNode(int value) {
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 前序遍历：根→左→右
void preorderTraversal(struct TreeNode* root) {
    if (root == NULL) return;
    printf("%d ", root->data);
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}

int main() {
    // 构建一个简单的二叉树
    struct TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);

    printf("前序遍历结果: ");
    preorderTraversal(root);  // 输出: 1 2 4 5 3
    printf("\n");

    return 0;
}
</syntaxhighlight>

== 树的遍历方法 ==

树有三种基本的遍历方式，区别在于访问根节点的时机：

1. '''前序遍历'''（Preorder）：根节点→左子树→右子树
2. '''中序遍历'''（Inorder）：左子树→根节点→右子树
3. '''后序遍历'''（Postorder）：左子树→右子树→根节点

对于上面的示例树，不同遍历的结果为：
* 前序：1 2 4 5 3
* 中序：4 2 5 1 3
* 后序：4 5 2 3 1

== 树的应用案例 ==

=== 文件系统 ===
操作系统中的文件系统通常用树结构组织。目录是节点，文件是叶节点。

<mermaid>
graph TD
    /((/)) --> etc((etc))
    / --> home((home))
    / --> usr((usr))
    home --> user1((user1))
    home --> user2((user2))
    user1 --> Documents((Documents))
    user1 --> Downloads((Downloads))
</mermaid>

=== 表达式解析 ===
算术表达式可以用表达式树表示，其中：
* 叶节点是操作数
* 非叶节点是运算符

例如表达式 (3+5)*2 的树表示：

<mermaid>
graph TD
    *((*)) --> +((+))
    * --> 2((2))
    + --> 3((3))
    + --> 5((5))
</mermaid>

=== 数据库索引 ===
许多数据库使用B树或B+树作为索引结构，以高效地存储和检索数据。

== 常见树类型 ==

1. '''二叉树'''：每个节点最多有两个子节点
2. '''二叉搜索树'''（BST）：左子树所有节点值小于根，右子树所有节点值大于根
3. '''平衡二叉树'''（如AVL树）：保持左右子树高度差不超过1
4. '''堆'''：完全二叉树，满足堆性质（最大堆或最小堆）
5. '''Trie'''（前缀树）：用于字符串检索

== 树的数学性质 ==

对于一棵有<math>n</math>个节点的树：
* 边数：<math>n-1</math>
* 对于二叉树，最小高度为<math>\lfloor \log_2 n \rfloor</math>
* 第<math>i</math>层最多有<math>2^{i-1}</math>个节点

== 进阶话题 ==

* 树的旋转操作（用于平衡二叉树）
* 红黑树原理
* B树和B+树在文件系统中的应用
* 树的序列化和反序列化

== 总结 ==

树是C语言中实现复杂数据组织的重要结构。理解树的基本概念和操作是学习更高级数据结构（如图）的基础。通过指针和递归，可以高效地实现各种树操作。在实际编程中，根据具体需求选择合适的树变体（如二叉搜索树用于快速查找，堆用于优先队列等）至关重要。

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