数据结构作业：二叉树直径与图遍历算法

"西南交通大学数据结构作业" 本次作业涵盖了数据结构中的关键概念，主要涉及二叉树和图的处理。以下是各个部分的知识点详解： 一、二叉树 1. **二叉树的直径**：二叉树的直径是树中任意两个节点之间的最长路径，这条路径至少包含一个根节点。求解二叉树直径通常需要两次深度优先搜索（DFS）或者一次深度优先搜索配合一次广度优先搜索（BFS）。首先找到两个距离最远的叶子节点，然后计算它们与根节点的距离。 算法思路： - DFS1：从根节点出发，找到最远的叶子节点，记录路径长度。 - DFS2：从另一个根节点出发，再次找到最远的叶子节点，记录路径长度。 - 最大值即为直径。 2. **叶子节点链接**：给定二叉树的根节点，可以通过遍历二叉树，将所有叶子节点的`rchild`指针域指向下一个叶子节点，形成一个单向链表。这个过程可以采用后序遍历，当遇到叶子节点时进行链接。 算法思路： - 后序遍历二叉树，遇到叶子节点时，将其`rchild`指针设置为其右兄弟或NULL（如果它是最后一个叶子节点）。 3. **先序建立二叉链表**：通过先序遍历输入的字符序列，可以构建二叉树的二叉链表表示。输入的字符'#'表示空节点。接着对构建的二叉树进行中序线索化，便于非递归中序遍历。 算法思路： - 先序遍历序列，遇到字符创建新节点，遇到'#'创建空节点，按照先序规则连接节点。 - 线索化中序遍历，标记每个节点的前驱和后继。 二、图 1. **邻接表存储结构**：无向图的邻接表是每个顶点关联一个列表，列表中包含所有与其相邻的顶点。根据图构建邻接表，并进行深度优先搜索（DFS）和广度优先搜索（BFS），输出访问顺序。 2. **判断无向图有环**：深度优先遍历过程中，如果在访问某个顶点后发现其邻接点中有已访问过且不是直接父节点的顶点，说明存在回边，即图中存在环。 算法思路： - 使用DFS，为每个访问过的节点标记状态。 - 当访问新节点时，检查其邻居中是否有已标记的节点，且该节点不是直接的父节点。 3. **无向图的遍历**：编程实现邻接表存储结构的无向图，并输出深度优先和宽度优先遍历的顶点访问顺序。DFS通常使用栈，BFS使用队列。 4. **AOE网络**：AOE（Activity On Edge）网络是一种特殊的有向无环图，用于表示项目的进度计划。需要计算每条边的最早开始时间（ve[]）和最晚开始时间（vl[]）。 计算思路： - 从源点开始，使用拓扑排序确定事件的执行顺序。 - 根据事件的依赖关系和完成时间，自底向上计算ve[]和vl[]。 这些题目旨在检验学生对二叉树的基本操作、图的存储结构以及遍历方法的理解和应用能力，同时涉及到图的环检测以及项目进度管理中的关键路径计算。通过这些练习，学生可以深化对数据结构核心概念的掌握。