数据结构作业：二叉树与图的算法解析

"西南交通大学的数据结构第4次作业，涵盖了二叉树和图的相关知识，包括算法设计与编程题目。" 本次作业主要涉及了数据结构中的核心概念——二叉树和图，具体知识点如下： 一、二叉树部分： 1. **二叉树的直径**：直径是从根节点到叶子节点的最大路径长度。可以使用递归的方法，分别计算左子树和右子树的直径，取较大者加上根节点到叶子节点的距离。 ```cpp int diameter(BiTNode* bt) { if (!bt) return 0; int d_left = diameter(bt->lchild); int d_right = diameter(bt->rchild); return d_left > d_right ? d_left : d_right + 1; } ``` 2. **最近公共祖先**：通过后序遍历，找到同时出现在左右子树的最近公共祖先。需要维护两个数组记录祖先节点。 3. **叶子节点链接**：遍历二叉树，利用叶子节点的`rchild`指针将它们连接成单链表，从最左边的叶子节点开始。 二、图部分： 1. **邻接表表示**：对于给定的无向图，可以构建多重邻接表来存储，并根据此结构进行深度优先遍历（DFS）和广度优先遍历（BFS）。 2. **环检测**：深度优先遍历时，若发现已访问的邻接点不是当前节点的直接前驱，说明存在环。 3. **图遍历**：编程实现邻接表存储结构，输出DFS和BFS的顶点访问顺序。 4. **AOE网**：建立活动-on-edge (AOE) 网络的邻接表存储，计算关键路径的ve[]和vl[]值。 5. **关键路径**：已知ve[]和vl[]，找出所有关键路径，用拓扑有序的顶点序列表示。 这些题目旨在检验学生对二叉树的基本操作、图的存储和遍历、环检测、以及AOE网的关键路径等概念的理解和应用能力。在解决这些问题时，需要熟悉二叉树和图的遍历算法，理解链式存储结构，并能运用递归或迭代方法解决问题。