这是西南交通大大学学生zhy提交的数据结构课程的第四次作业，内容涵盖了数据结构相关的理论应用和编程实践。文档包含了对各种数据结构的理解以及算法实现的具体代码。
西南交大；西南交通大学；数据结构；赵宏宇
一、二叉树（二）
1. 编写算法：
(1) 二叉树的直径定义为从根结点至叶子的最大路径长度。编写求解该值的算法。
(2) 已知二叉树(用二叉链表表示)根节点指针bt，以及两个节点p和q。请设计一个算法找出这两个节点最近公共祖先，并返回其地址。
(3) 给定一棵以二叉链表形式存储的二叉树及其根结点指针bt，请编写程序利用叶子结点的rchild字段将所有叶子连接成单向链表，最后输出该链表头结点地址。
2. 编程题：
(1) 输入一个不含重复字符的字符串。假设此串中的每个字符代表完全二叉树的一个节点值，建立对应的完全二叉树（使用二叉链表存储），然后分别进行前序、中序和后序遍历输出结果。
(2) 根据输入的先序序列(其中##表示空节点)，构建一个以char类型为数据域的二叉链表，完成该树的中序线索化，并用非递归方式实现其正逆两种顺序的中序遍历。
二、图
1. 已知某无向图如下。请画出它的多重邻接表示意图并给出从顶点v0出发进行深度和广度优先搜索时访问节点序列。
2. 设计一个算法来检测给定无向图是否存在环路，提示：在执行DFS过程中，若当前结点的某个相邻结点已被标记为已访问且该相邻结点不是上一递归步骤中的父节点，则表明存在回边即形成了环。
3. 编写程序建立某无向图的邻接表结构，并输出深度和广度优先搜索时顶点被访问顺序。
4. 设计一个算法构建AOE网络并计算所有事件ve[]及vl[]值，最后按要求格式展示结果。
5. 选做题*：
给定AOE网的邻接表存储以及其所有的ve[], vl[]数据，请编写程序输出该图的所有关键路径。每条路径应以源点至汇点顶点序列的形式给出（即需保持拓扑顺序）。
5星
