C 语言树基础

C语言树基础

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

树的基本概念

树是由节点（Node）组成的层次结构，具有以下特点：

• 每个树有一个根节点（Root Node），它是树的起点。
• 除根节点外，每个节点有且仅有一个父节点（Parent Node）。
• 节点可以有零个或多个子节点（Child Node）。
• 没有子节点的节点称为叶节点（Leaf Node）。
• 节点之间的连接称为边（Edge）。

树的常见术语：

• 深度（Depth）：从根节点到该节点的边数。
• 高度（Height）：从该节点到最远叶节点的边数。
• 度（Degree）：节点的子节点数量。

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

上图展示了一棵树，其中：

• A是根节点
• D、E、G、H、F是叶节点
• B的度是2（D和E）
• G的深度是3（A→B→D→G）
• A的高度是3（最长路径到G或H）

树的C语言实现

在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;
}

树的遍历方法

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

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

对于上面的示例树，不同遍历的结果为：

• 前序：1 2 4 5 3
• 中序：4 2 5 1 3
• 后序：4 5 2 3 1

树的应用案例

文件系统

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

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

表达式解析

算术表达式可以用表达式树表示，其中：

• 叶节点是操作数
• 非叶节点是运算符

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

graph TD *((*)) --> +((+)) * --> 2((2)) + --> 3((3)) + --> 5((5))

数据库索引

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

常见树类型

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

树的数学性质

对于一棵有$n$个节点的树：

• 边数：$n-1$
• 对于二叉树，最小高度为$\lfloor {\log }_{2}n\rfloor$
• 第$i$层最多有$2^{i-1}$个节点

进阶话题

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

总结

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