第五章 数据结构与算法
第二节 树形与图状数据结构
概述
本节重点讲解树形与图状两类重要的数据结构，它们在计算机科学中具有广泛的应用。通过本节学习，考生将系统掌握树和图的基本概念、结构特性、存储方式、常用操作及典型算法。掌握这些内容不仅能帮助理解复杂数据关系，还为后续算法设计与实现打下坚实基础。
学习目标如下：
- 理解树和图的定义与分类
- 掌握树的遍历方法及其实现
- 理解图的存储结构及遍历算法
- 学会典型案例分析与应用
- 避免常见误区，提高算法设计能力
核心概念
树（Tree）
树是一种层次型数据结构，由节点和边组成，具有以下特性：
- 具有一个根节点
- 除根节点外，每个节点只有一个父节点
- 节点可以有零个或多个子节点
- 没有环路，即不存在从某节点回到自身的路径
常见树的类型：
- 二叉树：每个节点最多有两个子节点，分别称为左子节点和右子节点
- 二叉搜索树（BST）：一种特殊的二叉树，左子树节点值小于根节点，右子树节点值大于根节点
- 平衡树（如AVL树）：保持树的高度平衡，保证操作效率
图（Graph）
图是由顶点（节点）和边组成的非线性数据结构，边连接两个顶点，边可以是有向或无向，图的特点：
- 允许有环路
- 边可以携带权值（加权图）
- 分为有向图和无向图
- 可以是连通图或非连通图
图的基本术语：
- 顶点（Vertex）
- 边（Edge）
- 度（Degree）：顶点的连接数，有向图中分为入度和出度
- 路径：顶点之间的连接序列
- 环：路径的起点和终点相同
原理分析
树的原理
树的结构体现了层次关系，适合表达分层信息。树的遍历是操作的核心，主要有三种方式：
- 前序遍历（Preorder）：根节点 → 左子树 → 右子树
- 中序遍历（Inorder）：左子树 → 根节点 → 右子树
- 后序遍历（Postorder）：左子树 → 右子树 → 根节点
这些遍历方法可以用递归和非递归（栈）方式实现。中序遍历特别适用于二叉搜索树的排序功能。
树的操作复杂度通常依赖于树的高度，平衡树通过旋转等操作控制高度，提高操作效率。
图的原理
图的存储和遍历是图结构的核心：
存储方式：
- 邻接矩阵：二维数组，适合稠密图，空间复杂度高
- 邻接表：链表或数组，适合稀疏图，节省空间
遍历算法：
- 深度优先搜索（DFS）：沿着一条路径深度遍历，遇到死胡同回溯
- 广度优先搜索（BFS）：逐层遍历，使用队列实现
图的遍历用于路径查找、连通性检测等，结合权重信息可实现最短路径算法（如Dijkstra算法）。
详细内容
1. 树的结构与表示
树由节点组成，节点包含数据域和指向子节点的指针。二叉树节点通常包含三个部分：数据域、左子节点指针、右子节点指针。
树的存储方式主要有：
- 链式存储：节点包含指针，灵活，适合动态结构
- 顺序存储：通常用于完全二叉树，利用数组下标计算父子关系
完全二叉树的性质：
- 除最后一层外，每层节点数达到最大
- 最后一层节点集中在左侧
利用数组存储完全二叉树时，给定节点下标 i：
- 左子节点下标为 2i + 1
- 右子节点下标为 2i + 2
- 父节点下标为 (i - 1) / 2
这使得树结构在内存中紧凑且易于访问。
2. 树的遍历及应用
树的遍历是访问所有节点的过程，三种遍历方式适用于不同场景。
- 前序遍历常用于复制树结构或表达式树的前缀表达式生成。
- 中序遍历生成排序序列，应用于二叉搜索树。
- 后序遍历用于释放树资源或生成后缀表达式。
遍历可用递归实现，简单直观；也可用栈模拟递归，避免函数调用开销。
3. 图的存储结构
图的存储方式直接影响算法效率：
邻接矩阵
- 用二维数组表示，
matrix[i][j]表示顶点 i 到顶点 j 是否有边 - 适合边数多的图，查询边存在性O(1)
- 缺点是空间复杂度高，O(V^2)
- 用二维数组表示，
邻接表
- 每个顶点维护一个链表，链表中包含该顶点所有邻接顶点
- 适合边数少的图，节省空间
- 查询边存在性最坏O(V)
4. 图的遍历算法
深度优先搜索（DFS）：
- 采用递归或栈实现
- 从一个顶点出发，尽可能深地探索分支
- 用于检测连通性、拓扑排序、寻找路径
广度优先搜索（BFS）：
- 使用队列实现
- 逐层访问邻近节点
- 可用于求最短路径（无权图）、层次遍历
这两种算法是图的基础，许多复杂算法的基础构件。
5. 特殊树与图结构
二叉搜索树（BST）
- 中序遍历结果为有序序列
- 插入、删除、查找平均时间复杂度为O(log n)
平衡树（AVL树、红黑树）
- 通过旋转维持高度平衡，保证最坏情况下操作效率
有向无环图（DAG）
- 无环有向图，用于表达依赖关系
- 拓扑排序是DAG的重要算法
实例分析
案例1：二叉搜索树插入与中序遍历
背景：设计一个系统，需要动态插入数据并保持数据有序。
分析：利用二叉搜索树插入新节点，保证左子树节点小于根，右子树节点大于根。中序遍历可输出排序序列。
步骤：
- 初始化空树
- 插入节点，比较大小决定左或右子树插入
- 中序遍历输出结果
结论：二叉搜索树有效支持动态排序数据的插入和查询。
案例2：图的DFS与BFS遍历
背景：社交网络分析，查找用户间的连接路径。
分析：用图表示用户及关系，应用DFS寻找深度连接，BFS用于查找最短连接路径。
步骤：
- 构建邻接表表示用户关系
- 选择起始用户，执行DFS或BFS
- 记录访问顺序和路径
结论：DFS适合深度连接探索，BFS适合最短路径查找。
案例3：拓扑排序应用于任务调度
背景：项目管理中任务有先后顺序，需合理安排执行顺序。
分析：用有向无环图表示任务依赖关系，拓扑排序给出可行执行序列。
步骤：
- 构建任务依赖图（DAG）
- 应用拓扑排序算法
- 输出任务执行顺序
结论：拓扑排序保证任务先后依赖正确，避免死锁。
常见误区
混淆树与图的概念
- 树是无环的层次结构，图允许环路。
- 正确做法：明确判断数据结构特性，选择合适模型。
遍历方法混用不当
- 如用中序遍历处理非二叉树结构，导致错误结果。
- 正确做法：针对不同树结构选择正确遍历方式。
图的存储结构选择错误
- 对稀疏图使用邻接矩阵，浪费空间。
- 正确做法：根据图的稠密度选择邻接表或邻接矩阵。
忽略图的连通性问题
- 遍历时不考虑非连通分量，导致访问不完全。
- 正确做法：多次遍历或标记所有顶点。
忽略树的平衡性导致效率降低
- 使用非平衡二叉搜索树，最坏情况下退化为链表。
- 正确做法：学习并应用平衡树技术。
应用场景
- 文件系统目录结构：操作系统使用树形结构组织文件和目录，便于层级管理。
- 数据库索引：采用B树、B+树实现高效数据检索。
- 社交网络关系分析：使用图结构表示用户关系和社交网络。
- 任务调度和依赖管理：利用有向无环图实现任务间依赖关系排序。
- 地图导航与路径规划：图的最短路径算法应用于GPS导航系统。
知识拓展
- 平衡树深入：了解AVL树、红黑树的旋转和调整机制
- 图算法进阶：学习最短路径算法（Dijkstra、Floyd）、最小生成树（Kruskal、Prim）
- 树形结构优化：线段树、树状数组用于高效区间查询
- 图的拓扑排序及应用：在编译器、项目管理中的应用
总结回顾
本节围绕树形与图状数据结构展开，系统讲解了二者的定义、特性、存储结构及遍历算法。重点掌握了树的三种遍历方式及其应用，图的邻接矩阵与邻接表存储，DFS和BFS遍历技术。通过典型案例，理解实际应用中树和图结构的设计与操作。并列举了常见误区，帮助考生避免错误理解。最后结合实际应用场景，展示树和图在计算机领域的广泛用途。
全面掌握本节内容，为后续算法学习和程序设计提供坚实基础。