树和图的实现与应用：C语言实践详解

树和图的实现与应用：C语言实践详解

树和图是两种重要的非线性数据结构，在计算机科学中有着广泛的应用。从基本的二叉树到复杂的图算法（如最短路径和最小生成树），这些结构能够帮助我们高效解决实际问题。本文将从基础出发，逐步深入，讲解如何用C语言实现树和图，并探讨其典型的应用场景。

一、树的数据结构

1. 什么是树？

树是一种层次化的数据结构，它由节点和边组成，满足以下特点：

• 每个节点有零个或多个子节点。
• 除了根节点外，每个节点只有一个父节点。
• 树是一个无环图。

常见的树结构包括：

• 二叉树：每个节点最多有两个子节点。
• 二叉搜索树：二叉树的一种，满足左子树的节点值小于根节点值，右子树的节点值大于根节点值。
• 平衡二叉树：在二叉搜索树的基础上，保证树的高度平衡（如AVL树）。
• 完全二叉树：除了最后一层外，所有层的节点都是满的，且最后一层的节点都靠左对齐。
• 满二叉树：所有节点都有两个子节点，或为叶子节点。
• 红黑树：一种自平衡二叉搜索树，通过节点着色和重新调整树结构，确保插入和删除的时间复杂度为O(log n)。
• B树和B+树：多路平衡查找树，常用于数据库和文件系统中。

2. 二叉树的实现

（1）定义节点结构

在C语言中，树通常通过链式存储实现。我们使用指针来表示父子节点关系。

#include <stdio.h>
#include <stdlib.h>

// 定义二叉树节点结构
typedef struct TreeNode {
   
    int value;                // 节点值
    struct TreeNode* left;    // 左子节点
    struct TreeNode* right;   // 右子节点
} TreeNode;

// 创建新节点
TreeNode* createNode(int value) {
   
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    newNode->value = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

（2）二叉树的遍历

二叉树的遍历方式主要包括：

• 前序遍历（Preorder Traversal）：根节点 -> 左子树 -> 右子树
• 中序遍历（Inorder Traversal）：左子树 -> 根节点 -> 右子树
• 后序遍历（Postorder Traversal）：左子树 -> 右子树 -> 根节点

以下是递归实现三种遍历方式的代码：

// 前序遍历
void preorderTraversal(TreeNode* root) {
   
    if (root == NULL) return;
    printf("%d ", root->value);
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}

// 中序遍历
void inorderTraversal(TreeNode* root) {