数据结构与算法复习
最近期末周准备考试，停更一段时间，结束之后继续更新
图
图连通问题
** 问题描述：**ConnectedComponents 给定无向图，计算无线图的连通分量
java">public class ConnectedComponents {private static Map<Vertex,Integer> cc; // the resulting mapprivate static UnDiGraph G; // the undirected graph/*** Returns the map of the connected components of 'G'* If cc is the returned map, then, for all verticies u and v,* cc.get(u) = cc.get(v) if and only if u and v are in the same* connected component*/public static Map<Vertex,Integer> find(UnDiGraph G) {cc = new HashMap<Vertex,Integer>();ConnectedComponents.G = G;int number = 1;for ( Vertex u : G.vertices() ) {if ( notNumbered(u) )setComponent(u,number++);}return cc;}/*** Set the component number to 'number' for 'u' and* all the vertices reachable from u*/private static void setComponent(Vertex u, int number) {setNumber(u, number);for ( Vertex a : G.adjacents(u) )if ( notNumbered(a) )setComponent(a,number);}private static boolean notNumbered(Vertex u) {return ! cc.containsKey(u);}private static void setNumber(Vertex u, int number) {cc.put(u, number);}public static void main(String[] s) {Map<Vertex,Integer> cc = find(GraphReader.U1);System.out.println(cc);cc = find(GraphReader.U2);System.out.println(cc);}
}环路检测
**问题描述：**检测有向图和无向图是否带环
java">public class Cycles {private static Graph G; // 当前图private static Set<Vertex> visited; // 已访问顶点集合/// 无向图的环检测/*** 检测无向图是否存在环* @param G 无向图* @return 如果存在环返回 true，否则返回 false*/public static boolean hasCycle(UnDiGraph G) {visited = new HashSet<>();Cycles.G = G;// 遍历所有顶点，启动深度优先搜索for (Vertex u : G.vertices()) {if (!visited.contains(u) && hasCycle(u, null)) {return true; // 如果发现环则直接返回}}return false; // 图中无环}/*** 深度优先搜索辅助方法* @param u 当前顶点* @param from 来自哪个顶点* @return 如果从顶点 u 开始发现环返回 true，否则返回 false*/private static boolean hasCycle(Vertex u, Vertex from) {visited.add(u); // 标记当前顶点为已访问for (Vertex neighbor : G.adjacents(u)) {if (!visited.contains(neighbor)) {if (hasCycle(neighbor, u)) return true; // 递归检测} else if (!neighbor.equals(from)) {return true; // 如果邻居已访问且不是来源顶点，则发现环}}return false;}/// 有向图的环检测private enum Status { UnDiscovered, InProgress, Completed } // 顶点状态枚举private static Map<Vertex, Status> vertexStatus; // 顶点状态映射/*** 检测有向图是否存在环* @param G 有向图* @return 如果存在环返回 true，否则返回 false*/public static boolean hasCycle(DiGraph G) {vertexStatus = new HashMap<>();Cycles.G = G;// 遍历所有顶点，启动深度优先搜索for (Vertex u : G.vertices()) {if (status(u) == Status.UnDiscovered && hasCycleDirected(u)) {return true; // 如果发现环则直接返回}}return false; // 图中无环}/*** 深度优先搜索辅助方法（有向图）* @param u 当前顶点* @return 如果从顶点 u 开始发现环返回 true，否则返回 false*/private static boolean hasCycleDirected(Vertex u) {setStatus(u, Status.InProgress); // 设置当前顶点为处理中for (Vertex neighbor : G.adjacents(u)) {if (status(neighbor) == Status.UnDiscovered) {if (hasCycleDirected(neighbor)) return true; // 递归检测} else if (status(neighbor) == Status.InProgress) {return true; // 如果邻居在处理中，发现环}}setStatus(u, Status.Completed); // 设置当前顶点为已完成return false;}/*** 获取顶点状态* @param u 顶点* @return 顶点的当前状态*/private static Status status(Vertex u) {return vertexStatus.getOrDefault(u, Status.UnDiscovered);}/*** 设置顶点状态* @param u 顶点* @param s 新状态*/private static void setStatus(Vertex u, Status s) {vertexStatus.put(u, s);}
}寻找路径
**问题描述：**寻找顶点 u 到 v 的路径
java">public class PathFinder {private static Graph G; // 当前图private static Set<Vertex> visited; // 已访问顶点集合/*** 查找从顶点 u 到顶点 v 的路径* @param G 图* @param u 起始顶点* @param v 目标顶点* @return 如果存在路径，返回路径上的顶点列表；否则返回空列表*/public static List<Vertex> findPath(Graph G, Vertex u, Vertex v) {PathFinder.G = G;visited = new HashSet<>();List<Vertex> path = new LinkedList<>();// 尝试找到从 u 到 v 的路径if (findPathHelper(u, v, path)) {return path; // 成功找到路径}return Collections.emptyList(); // 未找到路径}/*** 深度优先搜索辅助方法* @param u 当前顶点* @param v 目标顶点* @param path 路径列表* @return 如果存在路径返回 true，并将路径存储在 path 中；否则返回 false*/private static boolean findPathHelper(Vertex u, Vertex v, List<Vertex> path) {visited.add(u); // 标记当前顶点为已访问if (u.equals(v)) { // 如果到达目标顶点path.add(u); // 将目标顶点加入路径return true;}// 遍历当前顶点的所有相邻顶点for (Vertex neighbor : G.adjacents(u)) {if (!visited.contains(neighbor)) { // 如果相邻顶点未访问if (findPathHelper(neighbor, v, path)) { // 递归尝试找到路径path.add(0, u); // 将当前顶点加入路径前部return true;}}}return false; // 未找到路径}
}寻找源节点
**问题描述：**寻找有向图中可以到达图中所有顶点的 Root 顶点
java">public class RootFinder {private static DiGraph G; // 当前有向图private static Set<Vertex> visited; // 已访问顶点集合/*** 查找图 G 的根节点* @param G 有向图* @return 如果存在根节点，返回根节点；否则返回 null*/public static Vertex findRoot(DiGraph G) {RootFinder.G = G;visited = new HashSet<>();Vertex candidate = findCandidate(); // 获取根节点候选项visited.clear(); // 清除访问记录// 检查候选节点是否可以访问图中所有顶点if (visit(candidate) == G.nbVertices()) {return candidate;}return null; // 不存在根节点}/*** 寻找根节点的候选节点* @return 最后访问的顶点作为候选节点*/private static Vertex findCandidate() {Vertex lastVisited = null;for (Vertex u : G.vertices()) {if (!visited.contains(u)) {lastVisited = u; // 更新最后访问的顶点visit(u); // 深度优先访问该顶点}}return lastVisited; // 返回候选节点}/*** 访问从顶点 u 可达的所有顶点* @param u 起始顶点* @return 可访问的顶点数量*/private static int visit(Vertex u) {visited.add(u); // 标记当前顶点为已访问int count = 1; // 记录当前顶点// 遍历相邻顶点for (Vertex neighbor : G.adjacents(u)) {if (!visited.contains(neighbor)) {count += visit(neighbor); // 递归访问未访问的相邻顶点}}return count; // 返回总访问顶点数}
}图广度搜索遍历
java">private DiGraph G;
/*** 广度优先搜索（BFS），返回从起始顶点开始按访问顺序的顶点列表。* 通过一个队列逐层遍历图中的顶点，并确保每个顶点只访问一次。* * @param start 起始顶点* @return 从起始顶点出发的按访问顺序排列的顶点列表*/
public List<Vertex> bfs(Vertex start) {Queue<Vertex> queue = new LinkedList<>();List<Vertex> result = new LinkedList<>();Set<Vertex> marked = new HashSet<>();marked.add(start); // 标记起始顶点已访问queue.offer(start); // 将起始顶点加入队列while (!queue.isEmpty()) {Vertex v = queue.poll(); // 从队列中取出一个顶点result.add(v); // 将顶点加入结果列表for (Vertex a : G.adjacents(v)) { // 遍历当前顶点的所有邻接顶点if (!marked.contains(a)) { // 如果邻接顶点未被访问marked.add(a); // 标记邻接顶点已访问queue.offer(a); // 将邻接顶点加入队列}}}return result; // 返回按访问顺序的顶点列表
}/*** 使用广度优先搜索（BFS）计算从起始顶点到所有其他顶点的最短路径距离。* 记录每个顶点的距离并确保每个顶点只计算一次。* * @param start 起始顶点* @return 从起始顶点到其他顶点的最短路径距离映射*/
public Map<Vertex, Integer> distance(Vertex start) {Queue<Vertex> queue = new LinkedList<>();Map<Vertex, Integer> distance = new HashMap<>();distance.put(start, 0); // 起始顶点的距离初始化为 0queue.offer(start); // 将起始顶点加入队列while (!queue.isEmpty()) {Vertex v = queue.poll(); // 从队列中取出一个顶点for (Vertex a : G.adjacents(v)) { // 遍历当前顶点的所有邻接顶点if (!distance.containsKey(a)) { // 如果邻接顶点的距离尚未计算distance.put(a, distance.get(v) + 1); // 计算邻接顶点的距离queue.offer(a); // 将邻接顶点加入队列}}}return distance; // 返回从起始顶点到其他顶点的距离映射
}拓扑排序
1. Kahn算法（基于入度）
这个算法使用了入度的概念：图中一个顶点的入度是指指向该顶点的边的数量。
- 步骤：
- 计算图中每个顶点的入度。
- 将所有入度为0的顶点加入一个队列。
- 从队列中依次取出顶点，将其加入排序结果中。
- 对于每个被访问的顶点，减少它所有邻接顶点的入度。如果某个邻接顶点的入度变为0，加入队列。
- 如果所有顶点都被访问完且入度为0的顶点都处理过，输出排序结果。如果有顶点的入度仍不为0，说明图中存在环，无法进行拓扑排序。
- 时间复杂度：
O(V + E)，其中V是顶点数，E是边数。
java">/*** 使用拓扑排序算法返回有向图 G 的顶点列表，其中顶点按照拓扑顺序排列。* 拓扑排序适用于有向无环图（DAG），表示一种顶点的线性排列，使得对于每条有向边 (u, v)，顶点 u 在 v 之前出现。* 算法采用 Kahn 算法的实现，通过记录每个顶点的入度并逐步处理入度为 0 的顶点。* * @param G 输入的有向图* @return 按拓扑顺序排列的顶点列表。如果图中存在环，则返回的列表可能不完整。*/
public static List<Vertex> sort1(DiGraph G) {Map<Vertex, Integer> inDegree = new HashMap<>(); // 记录每个顶点的入度Queue<Vertex> queue = new LinkedList<>(); // 用于存储当前入度为 0 的顶点List<Vertex> sorted = new LinkedList<>(); // 存储排序后的顶点列表// 初始化入度并将入度为 0 的顶点加入队列for (Vertex vertex : G.vertices()) {inDegree.put(vertex, G.inDegree(vertex)); // 获取每个顶点的入度if (G.inDegree(vertex) == 0) { // 如果顶点的入度为 0，则加入队列queue.offer(vertex);}}// 处理队列中的顶点，执行拓扑排序while (!queue.isEmpty()) {Vertex v = queue.poll(); // 从队列中取出一个入度为 0 的顶点sorted.add(v); // 将该顶点加入排序结果for (Vertex a : G.adjacents(v)) { // 遍历该顶点的所有邻接顶点inDegree.put(a, inDegree.get(a) - 1); // 减少邻接顶点的入度if (inDegree.get(a) == 0) { // 如果邻接顶点的入度变为 0，则加入队列queue.offer(a);}}}return sorted; // 返回拓扑排序结果
}
2. 深度优先搜索（DFS）
DFS方法是通过递归或栈的方式实现的，利用递归栈的特点来帮助找到拓扑排序。
- 步骤：
- 对图中的每个顶点进行深度优先搜索。
- 在递归过程中，标记顶点为已访问。当所有相邻的顶点都被访问后，将当前顶点加入栈中。
- 最终，栈中的顶点顺序即为拓扑排序的结果（栈底的元素是最后访问的节点）。
- 如果在DFS过程中发现存在回边（即发现一个节点已经在递归栈中），则图中有环，无法进行拓扑排序。
- 时间复杂度：
O(V + E)，与Kahn算法相同。
java">/*** 使用深度优先搜索 (DFS) 返回有向图 G 的顶点列表，其中顶点按照拓扑顺序排列。* 拓扑排序适用于有向无环图（DAG），表示一种顶点的线性排列，使得对于每条有向边 (u, v)，顶点 u 在 v 之前出现。* 此方法通过递归实现拓扑排序，从未访问的顶点开始深度优先遍历，并将顶点按逆后序插入排序结果。** @param G 输入的有向图* @return 按拓扑顺序排列的顶点列表*/
public static List<Vertex> sort2(DiGraph G) {Set<Vertex> visited = new HashSet<>(); // 记录已访问的顶点List<Vertex> sorted = new LinkedList<>(); // 存储排序后的顶点列表// 对图中的每个顶点进行遍历，如果顶点尚未访问，则从该顶点开始执行 DFSfor (Vertex v : G.vertices()) {if (!visited.contains(v)) {visit(G, v, visited, sorted);}}return sorted; // 返回拓扑排序结果
}/*** 从顶点 u 开始对有向图 G 进行深度优先搜索 (DFS)，并按照拓扑顺序将顶点添加到列表 sorted 中。* 在递归过程中，所有访问过的顶点会被标记，避免重复访问。** @param G 输入的有向图* @param u 当前访问的顶点* @param visited 记录已访问顶点的集合* @param sorted 存储排序结果的列表，按逆后序插入顶点*/
private static void visit(DiGraph G, Vertex u, Set<Vertex> visited, List<Vertex> sorted) {visited.add(u); // 标记当前顶点为已访问for (Vertex a : G.adjacents(u)) { // 遍历当前顶点的所有邻接顶点if (!visited.contains(a)) { // 如果邻接顶点尚未访问，递归访问visit(G, a, visited, sorted);}}sorted.add(0, u); // 当前顶点的所有邻接顶点处理完毕后，将该顶点插入结果列表开头
}
哈密尔顿回路
拓扑排序法
java">/*** 测试有向图 G 是否存在哈密顿路径。* 哈密顿路径是图中一种路径，它访问每个顶点恰好一次（不需要回到起点）。* 此方法首先对图进行拓扑排序，然后验证拓扑排序中的每对相邻顶点是否在原图中直接相连。** @param G 输入的有向图* @return 如果存在哈密顿路径则返回 true，否则返回 false*/
public static boolean hasHamiltonianPath(DiGraph G) {// 对有向图 G 进行拓扑排序，获取按拓扑顺序排列的顶点列表List<Vertex> topo = sort1(G);// 获取拓扑排序列表中的第一个顶点Vertex previous = topo.remove(0);// 遍历拓扑排序列表中的剩余顶点for (Vertex v : topo) {// 如果当前顶点和前一个顶点之间不存在有向边，则图中不存在哈密顿路径if (!G.adjacents(previous, v)) {return false;}// 更新前一个顶点为当前顶点previous = v;}// 如果所有相邻顶点都满足条件，返回 truereturn true;
}
回溯法
java">/*** 检查图 G 是否存在哈密顿回路* @param G 输入的有向图* @return 如果存在哈密顿回路则返回 true，否则返回 false*/
public static boolean hasHamiltonianCycle(DiGraph G) {// 图中顶点数量int V = G.nbVertices();// 用来记录访问过的顶点boolean[] visited = new boolean[V];// 假设起始顶点是第一个顶点Vertex start = G.vertices().get(0);// 通过回溯法检测哈密顿回路return hasHamiltonianCycleUtil(G, start, visited, start, 1);
}/*** 使用回溯法从当前顶点 u 开始，检查是否能找到哈密顿回路* @param G 输入的有向图* @param u 当前顶点* @param visited 记录访问过的顶点* @param start 起始顶点，用于回路检测* @param count 已访问顶点的数量* @return 如果存在哈密顿回路，则返回 true，否则返回 false*/
private static boolean hasHamiltonianCycleUtil(DiGraph G, Vertex u, boolean[] visited, Vertex start, int count) {// 如果已访问的顶点数量等于图中的顶点数量，且当前顶点与起始顶点相连，则存在回路if (count == G.nbVertices() && G.adjacents(u, start)) {return true;}// 遍历所有相邻顶点for (Vertex v : G.adjacents(u)) {// 如果 v 尚未访问if (!visited[v.getIndex()]) {// 标记为已访问visited[v.getIndex()] = true;// 递归调用，继续访问相邻的顶点if (hasHamiltonianCycleUtil(G, v, visited, start, count + 1)) {return true;}// 回溯：撤销对 v 的访问visited[v.getIndex()] = false;}}// 如果无法找到回路，返回 falsereturn false;
}
最小生成树
并查集
java">
/*** 使用 up-tree 实现的并查集（Disjoint Set）*/
public class Partition<AnyType> {private int nbTrees; // 当前树的数量private Map<AnyType, InnerTree> map; // 存储元素与其所在树的映射/*** 构造一个空的并查集*/public Partition() {nbTrees = 0;map = new HashMap<>();}/*** 返回当前并查集中的树的数量*/public int nbTrees() {return nbTrees;}/*** 向并查集中添加一个新的单元素树*/public void newTree(AnyType e) {map.put(e, new InnerTree());nbTrees++;}/*** 查找元素 e 所在的树*/public InnerTree find(AnyType e) {return find(map.get(e));}/*** 合并两个树，要求两个树不相同*/public void union(InnerTree x, InnerTree y) {if (x.size <= y.size) {x.parent = y; // 将小树挂到大树下面y.size += x.size; // 更新大小} else {y.parent = x; // 将小树挂到大树下面x.size += y.size; // 更新大小}nbTrees--; // 合并后树的数量减少}/*** 查找某个树的根，使用路径压缩*/private InnerTree find(InnerTree n) {if (n != n.parent) {n.parent = find(n.parent); // 递归查找并压缩路径}return n.parent; // 返回树的根}/*** 代表树的接口，外部只能通过引用来比较树*/public interface Tree {}/*** 内部类 InnerTree，表示树的节点*/private class InnerTree implements Tree {InnerTree parent; // 父节点int size; // 当前树的元素数量InnerTree() {this.parent = this; // 初始化时自己是根this.size = 1; // 初始大小为 1}}
}Prim 最小生成树
java">/*** 使用 Prim 算法返回加权无向图 G 的最小生成树（MST）边的列表* 前提：图 G 是连通的*/
public static List<Edge> prim(UnDiGraph G) throws FullHeapException, EmptyHeapException {// 存储最小生成树的边List<Edge> mst = new LinkedList<Edge>();// 定义最小堆的比较器，按权重升序排列Comparator<Edge> c = new Comparator<Edge>() {public int compare(Edge e1, Edge e2) {return e1.compareTo(e2); // 使用边的比较方法进行比较}};// 创建最小堆BinaryHeap<Edge> minHeap = new BinaryHeap<Edge>(G.nbEdges(), c);// 用一个集合记录已知的顶点Set<Vertex> known = new HashSet<Vertex>();// 随机选择一个起始顶点 uVertex u = G.getRandomVertex();known.add(u);// 将与 u 相邻的边加入堆中for (Edge e : G.incidents(u))minHeap.add(e);// 当尚未连接所有顶点时，继续循环while (known.size() < G.nbVertices()) {Edge min = minHeap.deleteExtreme(); // 取出权重最小的边Vertex x = notKnown(min, known); // 找到该边的未知道顶点if (x != null) {mst.add(min); // 将该边加入最小生成树known.add(x); // 将该顶点加入已知集合// 将与 x 相邻的所有边加入堆中for (Edge e : G.incidents(x)) {Vertex y = notKnown(e, known); // 找到该边的未知道顶点if (y != null)minHeap.add(e); // 将边加入堆}}}return mst;
}/*** 判断边 e 的两个端点中哪个不在 known 集合中* 前提：至少有一个端点在 known 集合中*/
private static Vertex notKnown(Edge e, Set<Vertex> known) {if (!known.contains(e.origin())) {return e.origin();} else if (!known.contains(e.destination())) {return e.destination();}return null;
}
Prim 最小生成林
java">/*** 使用 Prim 算法返回加权无向图 G 的最小生成森林（MSF）边的列表* 适用于图是非连通的情况*/
public static List<Edge> prim(UnDiGraph G) throws FullHeapException, EmptyHeapException {// 存储最小生成森林的边List<Edge> mst = new LinkedList<Edge>();// 定义最小堆的比较器，按权重升序排列Comparator<Edge> c = new Comparator<Edge>() {public int compare(Edge e1, Edge e2) {return e1.compareTo(e2); // 使用边的比较方法进行比较}};// 创建最小堆BinaryHeap<Edge> minHeap = new BinaryHeap<Edge>(G.nbEdges(), c);// 用一个集合记录已知的顶点Set<Vertex> known = new HashSet<Vertex>();// 遍历所有顶点，处理每一个连通分量for (Vertex u : G.vertices()) {if (!known.contains(u)) {known.add(u); // 标记当前顶点为已知// 将与顶点 u 相邻的边加入堆中for (Edge e : G.incidents(u)) {minHeap.add(e);}// 当堆中还有边且存在未连接的顶点时，继续循环while (!minHeap.isEmpty()) {Edge min = minHeap.deleteExtreme(); // 取出权重最小的边Vertex x = notKnown(min, known); // 找到该边的未知道顶点if (x != null) {mst.add(min); // 将该边加入最小生成森林known.add(x); // 将该顶点加入已知集合// 将与顶点 x 相邻的所有边加入堆中for (Edge e : G.incidents(x)) {Vertex y = notKnown(e, known); // 找到该边的未知道顶点if (y != null) {minHeap.add(e); // 将边加入堆}}}}}}return mst;
}/*** 判断边 e 的两个端点中哪个不在 known 集合中* 前提：至少有一个端点在 known 集合中*/
private static Vertex notKnown(Edge e, Set<Vertex> known) {if (!known.contains(e.origin())) {return e.origin();} else if (!known.contains(e.destination())) {return e.destination();}return null;
}Kruskal 最小生成树
java">/*** 使用 Kruskal 算法返回加权无向图 G 的最小生成树（MST）边的列表* 前提：图 G 是连通的*/
public static List<Edge> kruskal(UnDiGraph G) throws FullHeapException, EmptyHeapException {// 存储最小生成树的边List<Edge> mst = new LinkedList<Edge>();// 定义最小堆的比较器，按权重升序排列Comparator<Edge> c = new Comparator<Edge>() {public int compare(Edge e1, Edge e2) {return e1.compareTo(e2); // 使用边的比较方法进行比较}};// 创建最小堆BinaryHeap<Edge> minHeap = new BinaryHeap<Edge>(G.nbEdges(), c);// 将所有边加入堆中for (Edge e : G.edges())minHeap.add(e);// 初始化并查集（用来判断是否形成环）Partition<Vertex> P = new Partition<Vertex>();// 将每个顶点加入并查集中作为独立的树for (Vertex v : G.vertices())P.newTree(v);// 当所有顶点还未连接成一个连通分量时，继续循环while (P.nbTrees() > 1) {Edge min = minHeap.deleteExtreme(); // 取出权重最小的边Vertex u = min.origin();Vertex v = min.destination();// 判断 u 和 v 是否属于同一树（即是否会形成环）Partition.Tree ru = P.find(u);Partition.Tree rv = P.find(v);if (ru != rv) { // 如果不在同一树中，则合并它们mst.add(min); // 将该边加入最小生成树P.union(ru, rv); // 合并这两棵树}}return mst;
}
最短路径
Dijkstra
ps : 无法处理负权图
**问题描述：**给定有向图或者无向图，计算开始顶点到其他各个顶点的最短路
edgeTo：记录每个顶点到达的前驱顶点，从而形成一棵最短路径树。利用 edgeTo 可以回溯并重建从起点到任意目标点的最短路径。
known：存储已确定最短路径的顶点，避免重复访问。
heap：用于维护当前所有未处理顶点的权重，使得可以快速找到权重最小的顶点（优先级队列的核心作用）。
顶点权重：最短路径的权重值
java">protected Graph G; // 图的表示，可以是有向图或无向图
protected Map<Vertex, Vertex> edgeTo; // 用于记录每个顶点的最短路径的前驱顶点
protected Vertex start; // 起点顶点/*** 实现 Dijkstra 算法计算从起点到所有其他顶点的最短路径。* 前置条件：图 G 的顶点和边已正确定义，起点 start 已指定。*/
public void Dijkstra() {// 已知集合：存储所有已确定最短路径的顶点Set<Vertex> known = new HashSet<>();// 初始化每个顶点的权重为正无穷大，起点权重为 0for (Vertex v : G.vertices()) {v.setWeight(Double.POSITIVE_INFINITY);}start.setWeight(0.0);// 创建一个最小堆，用于动态维护未处理顶点的权重顺序DijkstraHeap heap = new DijkstraHeap(G.nbVertices());// 将所有顶点加入堆中for (Vertex v : G.vertices()) {heap.add(v);}// 主循环：每次处理权重最小的顶点，直到所有顶点都已知while (known.size() != G.nbVertices()) {// 从堆中取出当前权重最小的顶点Vertex min = heap.deleteMin();// 将该顶点加入已知集合known.add(min);// 遍历当前顶点的所有相邻边for (Edge e : G.incidents(min)) {Vertex v = e.otherEnd(min); // 找到相邻的顶点if (!known.contains(v)) { // 如果该顶点尚未确定最短路径double newDist = min.getWeight() + e.weight(); // 计算从起点到该顶点的新路径权重if (newDist < v.getWeight()) { // 如果新路径权重更小v.setWeight(newDist); // 更新顶点的权重edgeTo.put(v, min); // 更新前驱顶点为当前顶点heap.percolateUp(v); // 调整堆中的位置，确保堆的正确性}}}}
}**问题描述：**起始顶点到目标顶点存在多条最短路径，记录所有最短路径
增加一个 nosp 记录最短路径的数量
java">protected Graph G; // 图的表示，可以是有向图或无向图
protected Map<Vertex, Vertex> edgeTo; // 用于记录每个顶点的最短路径的前驱顶点
protected Vertex start; // 起点顶点// 记录每个顶点到达源点的最短路径数
Map<Vertex, Integer> nosp = new HashMap<>();; // Number of Shortest Paths// 计算从起点到每个顶点的最短路径长度及路径数
public void DijkstraWithPath() {Set<Vertex> known = new HashSet<>(); // 存储已经处理过的顶点// 初始化所有顶点的最短路径为正无穷大，并设置起点的路径长度为 0for (Vertex v : G.vertices()) {v.setWeight(Double.POSITIVE_INFINITY); // 将所有顶点的权重设置为无穷大nosp.put(v, 0); // 设置每个顶点的最短路径数为 0}start.setWeight(0.0); // 设置起点的权重为 0nosp.put(start, 1); // 起点的最短路径数为 1// 创建一个堆来管理所有顶点，并按最短路径权重排序DijkstraHeap heap = new DijkstraHeap(G.nbVertices());for (Vertex v : G.vertices())heap.add(v); // 将所有顶点添加到堆中// Dijkstra算法的主循环：直到所有顶点都被处理while (known.size() != G.nbVertices()) {// 从堆中取出当前最短路径的顶点Vertex min = heap.deleteMin();known.add(min); // 将当前顶点加入已处理顶点集合// 遍历当前顶点的所有相邻顶点for (Edge e : G.incidents(min)) {Vertex v = e.otherEnd(min); // 获取边的另一个顶点double newDist = min.getWeight() + e.weight(); // 计算通过当前边到达 v 的新路径长度if (known.contains(v)) { // 如果 v 已经处理过// 如果新路径长度等于原路径长度，累加最短路径数if (newDist == v.getWeight()) {nosp.put(v, nosp.get(v) + nosp.get(min)); // 累加路径数}} else if (newDist <= v.getWeight()) { // 如果新路径更短或相等v.setWeight(newDist); // 更新 v 的最短路径edgeTo.put(v, min); // 记录 v 的前驱节点nosp.put(v, nosp.get(min)); // 更新 v 的路径数heap.percolateUp(v); // 调整堆，保持顺序}}}
}// 返回从源点到每个顶点的最短路径数
public Map<Vertex, Integer> nbPaths() {return nosp; // 返回路径数的映射
}BellmanFord
可处理负权值，检测负权回路
java">protected Graph G; // 图的表示，可以是有向图或无向图
protected Map<Vertex, Vertex> edgeTo; // 用于记录每个顶点的最短路径的前驱顶点
protected Vertex start; // 起点顶点
/*** 使用 Bellman-Ford 算法计算从起点到图中所有其他顶点的最短路径。* 该算法能够处理带负权边的图，但如果存在负权回路，则无法保证正确性。*/
public void BellmanFord() {// 初始化所有顶点的权重为正无穷大for (Vertex v : G.vertices()) {v.setWeight(Double.POSITIVE_INFINITY);}// 设置起点的权重为 0start.setWeight(0.0);// 标志变量，用于判断在一次松弛操作中是否更新了权重boolean update = true;// 进行 |V| - 1 次松弛操作（其中 |V| 为顶点数量）// 如果在某一轮没有任何更新，算法提前终止for (int i = 0; update && i < G.nbVertices() - 1; i++) {update = false; // 假设本轮没有权重更新// 遍历图中所有的边for (Edge e : G.edges()) {Vertex u = e.origin(); // 边的起点Vertex v = e.destination(); // 边的终点double newDist = u.getWeight() + e.weight(); // 计算从起点到 v 的新权重// 如果通过边 e 可以找到更短路径，则更新权重和路径if (newDist < v.getWeight()) {update = true; // 本轮发生了权重更新v.setWeight(newDist); // 更新顶点 v 的权重edgeTo.put(v, u); // 更新 v 的前驱顶点为 u}}}
}排序 Sorting
selection sort
java">public static <AnyType extends Comparable<AnyType>> void selection(AnyType[] array) {for ( int i = 0; i < array.length - 1; i++ ) {int k = i;for ( int j = i + 1; j < array.length; j++ )if ( array[j].compareTo(array[k]) < 0 )k = j;swap(array, i, k);}}
insertion sort
java">public static <AnyType extends Comparable<AnyType>> void insertion(AnyType[] array) {for ( int i = 1; i < array.length; i++ ) {AnyType x = array[i];int j = i; while ( j > 0 && array[j - 1].compareTo(x) > 0 ) {array[j] = array[j - 1];j = j - 1;}array[j] = x;}}
heap sort
java">public static <AnyType extends Comparable<AnyType>> void sort(AnyType[] array) {BinaryHeap<AnyType> heap = new BinaryHeap<AnyType>(array);for ( int i = array.length - 1; i > 0; i-- )try {array[i] = heap.deleteExtreme();}catch ( Exception e ) {}}
merge sort
java">/*** 使用辅助数组 tmp 中 [lo, hi] 的部分对数组 array 中 [lo, hi] 的部分进行排序* 时间复杂度：THETA(n.log(n))，其中 n = hi - lo + 1*/
private static <AnyType extends Comparable<AnyType>> void sort(AnyType[] array, AnyType[] tmp, int lo, int hi) {// 如果区间内至少有两个元素，则继续划分if (lo < hi) {// 计算中点位置int mid = (lo + hi) / 2;// 递归对左半部分排序sort(array, tmp, lo, mid);// 递归对右半部分排序sort(array, tmp, mid + 1, hi);// 合并左右部分merge(array, tmp, lo, mid, hi);// 将辅助数组的结果拷贝回原数组transfer(tmp, array, lo, hi);}
}/*** 合并 array[lo, mid] 和 array[mid+1, hi] 到 tmp[lo, hi]，* 然后将结果拷贝回 array[lo, hi]* 前提条件：array[lo, mid] 和 array[mid+1, hi] 已经排序* 时间复杂度：THETA(n)，其中 n = hi - lo + 1*/
private static <AnyType extends Comparable<AnyType>> void merge(AnyType[] array, AnyType[] tmp, int lo, int mid, int hi) {// 定义左指针 l、右指针 r 和目标位置指针 mint l = lo; // 左半部分的起始位置int r = mid + 1; // 右半部分的起始位置int m = lo; // 辅助数组中当前写入的位置// 交替从左右两部分中选择较小的元素，写入 tmpwhile (l <= mid && r <= hi) {if (array[l].compareTo(array[r]) < 0) {tmp[m++] = array[l++];} else {tmp[m++] = array[r++];}}// 如果左半部分还有剩余元素，则全部写入 tmpwhile (l <= mid) {tmp[m++] = array[l++];}// 如果右半部分还有剩余元素，则全部写入 tmpwhile (r <= hi) {tmp[m++] = array[r++];}
}
java">/*** 使用辅助数组 tmp 的 [lo, hi] 部分对 array 的 [lo, hi] 部分进行原地排序* 时间复杂度：THETA(n.log(n))，其中 n = hi - lo + 1*/
private static <AnyType extends Comparable<AnyType>> void sortInplace(AnyType[] array, AnyType[] tmp, int lo, int hi) {// 如果区间内至少有两个元素，继续分割if (lo < hi) {// 计算中间位置int mid = (lo + hi) / 2;// 递归对左半部分进行排序sortTo(array, tmp, lo, mid);// 递归对右半部分进行排序sortTo(array, tmp, mid + 1, hi);// 合并左右部分到原数组中mergeTo(tmp, array, lo, mid, hi);}
}/*** 将 array 中 [lo, hi] 部分排序后存入 tmp 的 [lo, hi] 部分* 时间复杂度：THETA(n.log(n))，其中 n = hi - lo + 1*/
private static <AnyType extends Comparable<AnyType>> void sortTo(AnyType[] array, AnyType[] tmp, int lo, int hi) {// 如果区间内至少有两个元素，继续分割if (lo < hi) {// 计算中间位置int mid = (lo + hi) / 2;// 递归对左半部分排序并存入 arraysortInplace(array, tmp, lo, mid);// 递归对右半部分排序并存入 arraysortInplace(array, tmp, mid + 1, hi);// 合并左右部分到辅助数组中mergeTo(array, tmp, lo, mid, hi);} // 如果区间只有一个元素，直接将其复制到辅助数组else if (lo == hi) {tmp[lo] = array[lo];}
}/*** 将 from 数组的 [lo, mid] 和 [mid+1, hi] 两部分合并到 to 数组的 [lo, hi] 部分* 前置条件：from[lo, mid] 和 from[mid+1, hi] 均已排序* 时间复杂度：THETA(n)，其中 n = hi - lo + 1*/
private static <AnyType extends Comparable<AnyType>> void mergeTo(AnyType[] from, AnyType[] to, int lo, int mid, int hi) {// 定义左指针 l、右指针 r 和目标位置指针 mint l = lo; // 左半部分的起始位置int r = mid + 1; // 右半部分的起始位置int m = lo; // 目标数组的写入位置// 合并左右两部分，选择较小的元素放入目标数组while (l <= mid && r <= hi) {if (from[l].compareTo(from[r]) < 0) {to[m++] = from[l++];} else {to[m++] = from[r++];}}// 如果左半部分还有剩余元素，全部写入目标数组while (l <= mid) {to[m++] = from[l++];}// 如果右半部分还有剩余元素，全部写入目标数组while (r <= hi) {to[m++] = from[r++];}
}
quick sort
java">/*** 快速排序主方法* @param array 待排序数组* @param lo 当前排序范围的左边界* @param hi 当前排序范围的右边界*/
private static <AnyType extends Comparable<AnyType>> void sort(AnyType[] array, int lo, int hi) {if (lo < hi) {// 对当前范围进行分区操作，并获取基准值的索引int pivot = partition(array, lo, hi);// 递归排序左半部分sort(array, lo, pivot - 1);// 递归排序右半部分sort(array, pivot + 1, hi);}
}/*** 对数组的部分区间 array[lo, hi] 进行分区操作* 并返回基准值（pivot）的最终索引* @param array 待分区数组* @param lo 分区范围的左边界* @param hi 分区范围的右边界* @return 基准值的最终索引*/
private static <AnyType extends Comparable<AnyType>> int partition(AnyType[] array, int lo, int hi) {// 选择最左边的元素作为基准值AnyType pivot = array[lo];int p = lo; // p 用于记录小于 pivot 的区域的末尾索引// 遍历数组的其余部分for (int i = lo + 1; i <= hi; i++) {// 如果当前元素小于基准值，将其与小于区域的下一个元素交换if (array[i].compareTo(pivot) < 0) {swap(array, i, ++p);}}// 将基准值放到正确位置，即小于区域的末尾swap(array, lo, p);return p; // 返回基准值的最终位置
}/*** 交换数组中的两个元素* @param array 数组* @param i 第一个元素的索引* @param j 第二个元素的索引*/
private static <AnyType> void swap(AnyType[] array, int i, int j) {AnyType temp = array[i];array[i] = array[j];array[j] = temp;
}rank
java">/*** 返回数组中指定元素 'item' 的秩（排名）。秩是指该元素在已排序数组中的位置（从 1 开始）。* 前提条件：如果 'item' 存在于数组中，它位于切片 array[lo, hi] 范围内。* * @param item 要查找的元素* @param array 待排序的数组* @param lo 当前查找范围的起始索引* @param hi 当前查找范围的结束索引* @return 如果 'item' 存在，返回其秩（1-based index），否则返回 -1*/
private static <AnyType extends Comparable<AnyType>> int rank(AnyType item, AnyType[] array, int lo, int hi) {// 如果当前查找范围无效（hi < lo），返回 -1if (hi < lo)return -1;// 对当前范围进行分区操作，返回基准元素的索引int pivot = partition(array, lo, hi);// 比较 'item' 和基准元素的大小int cmp = item.compareTo(array[pivot]);// 如果 'item' 小于基准元素，递归查找左半部分if (cmp < 0)return rank(item, array, lo, pivot - 1);// 如果 'item' 大于基准元素，递归查找右半部分if (cmp > 0)return rank(item, array, pivot + 1, hi);// 如果相等，返回该基准元素的秩（索引 + 1）return pivot + 1;
}/*** 对数组的部分区间 array[lo, hi] 进行分区操作* 并返回基准元素（pivot）的最终索引* * @param array 待分区数组* @param lo 分区范围的起始索引* @param hi 分区范围的结束索引* @return 基准元素的最终索引*/
private static <AnyType extends Comparable<AnyType>> int partition(AnyType[] array, int lo, int hi) {// 选择最左边的元素作为基准元素AnyType pivot = array[lo];int p = lo; // p 用于记录小于基准元素的区域的末尾索引// 遍历数组的其余部分for (int i = lo + 1; i <= hi; i++) {// 如果当前元素小于基准元素，则将其与小于区域的下一个元素交换if (array[i].compareTo(pivot) < 0) {swap(array, i, ++p);}}// 将基准元素放到正确的位置，即小于区域的末尾swap(array, lo, p);return p; // 返回基准元素的最终位置
}/*** 交换数组中的两个元素* * @param array 数组* @param i 第一个元素的索引* @param j 第二个元素的索引*/
private static <AnyType> void swap(AnyType[] array, int i, int j) {AnyType temp = array[i];array[i] = array[j];array[j] = temp;
}二叉堆 Heap
Binary heap
java">/*** 使数组 A 中的元素满足堆的性质（大顶堆）。* 时间复杂度: O(size)，其中 size 是堆的大小。*/
private void buildHeap() {// 从最后一个非叶子节点开始向上调整堆，使得整个数组满足堆的性质for (int i = parent(size - 1); i >= 0; i--)percolateDown(i);
}
/*** 对堆中指定节点 n 执行下沉操作，调整堆使其仍然保持堆的性质。* 时间复杂度: O(log(size))，其中 size 是堆的大小。*/
private void percolateDown(int n) {// 获取当前节点的左右子节点索引int g = left(n); // 左子节点int d = right(n); // 右子节点int k = n; // 假设当前节点是最大的节点// 如果左子节点存在且左子节点大于当前节点，则更新 k 为左子节点的索引if (g < size && c.compare(A[g], A[n]) > 0)k = g;// 如果右子节点存在且右子节点大于当前的最大节点，则更新 k 为右子节点的索引if (d < size && c.compare(A[d], A[k]) > 0)k = d;// 如果 k 不等于 n，说明当前节点不是最大节点，需要交换并继续下沉if (k != n) {swap(k, n); // 交换当前节点和最大子节点percolateDown(k); // 递归调用下沉操作，继续调整堆}
}/*** 对堆中指定节点 n 执行上浮操作，调整堆使其仍然保持堆的性质。* 时间复杂度: O(log(size))，其中 size 是堆的大小。*/
private void percolateUp(int n) {// 记录当前节点的值AnyType e = A[n];// 上浮元素，使其不违反堆的性质while (n > 0 && c.compare(e, A[parent(n)]) > 0) {// 如果当前节点比父节点大，则将父节点下沉到当前节点的位置A[n] = A[parent(n)];n = parent(n); // 更新 n 为父节点的索引}// 将上浮的元素放到正确的位置A[n] = e;
}
/*** 返回并删除堆中的极端元素（根节点元素）。* 时间复杂度: O(log(size))，其中 size 是堆的大小。*/
public AnyType deleteExtreme() throws EmptyHeapException {// 如果堆为空，则抛出异常if (size == 0)throw new EmptyHeapException();// 记录极端元素（堆顶元素）AnyType extreme = A[0];// 将堆的最后一个元素放到堆顶A[0] = A[--size];// 如果堆不为空，执行下沉操作调整堆if (size > 0)percolateDown(0);return extreme; // 返回删除的极端元素
}/*** 向堆中添加一个新元素。* 时间复杂度: O(log(size))，其中 size 是堆的大小。*/
public void add(AnyType e) throws FullHeapException {// 如果堆满，则抛出异常if (size == A.length)throw new FullHeapException();// 将新元素添加到堆的末尾A[size++] = e;// 上浮新元素，使得堆保持堆的性质percolateUp(size - 1);
}D-heaps
java">private void percolateDown(int n) {int k = n;// 遍历当前节点的所有子节点，子节点的范围是 [d*k+1, d*(k+1)] for (int i = d * k + 1; i < size && i <= d * (k + 1); i++) {// 如果当前子节点比当前节点大，则更新 k 为子节点的索引if (c.compare(A[i], A[k]) > 0)k = i;}// 如果 k 被更新了，说明子节点中有比当前节点更大的元素，交换并继续下沉操作if (k != n) {swap(k, n);percolateDown(k); // 递归继续下沉}
}
private void percolateUp(int n) {AnyType e = A[n];// 上浮元素，直到堆的性质满足，或者到达根节点while (n > 0 && c.compare(e, A[parent(n)]) > 0) {// 如果当前节点比父节点大，则交换当前节点与父节点A[n] = A[parent(n)];n = parent(n); // 更新 n 为父节点的索引}A[n] = e; // 将上浮后的元素放置到正确的位置
}
树 Trees
java">// 计算二叉树的高度
// 高度定义为从根节点到最远叶子节点的路径长度（不包括根节点）
private int height(BinaryNode<AnyType> t) {// 如果节点为空，则返回 -1（空树的高度）if ( t == null )return -1;// 否则，递归计算左子树和右子树的高度，返回它们的最大值加一return 1 + Math.max(height(t.left), height(t.right));
}// 计算二叉树的 lowness，定义为从根节点到最接近的叶子节点的路径长度
public int lowness(BinaryNode<AnyType> t) {// 如果是叶子节点（没有左右子树），返回 0if ( t.left == null && t.right == null )return 0;// 如果只有左子树，递归计算左子树的 lowness，加 1if ( t.left == null )return 1 + lowness(t.right);// 如果只有右子树，递归计算右子树的 lowness，加 1if ( t.right == null )return 1 + lowness(t.left);// 如果左右子树都存在，递归计算左右子树的 lowness，返回其中较小值加 1return 1 + Math.min(lowness(t.left), lowness(t.right));
}// 计算二叉树的大小，即节点的总数
private int size(BinaryNode<AnyType> t) {// 如果节点为空，返回 0（树的大小）if ( t == null )return 0;// 否则，递归计算左右子树的大小，并加上当前节点return 1 + size(t.left) + size(t.right);
}// 计算二叉树的叶子节点数量
private int leaves(BinaryNode<AnyType> t) {// 如果节点为空，返回 0if ( t == null )return 0;// 如果是叶子节点（没有左右子树），返回 1if ( t.left == null && t.right == null )return 1;// 否则，递归计算左右子树中的叶子节点数量return leaves(t.left) + leaves(t.right);
}// 检查两个二叉树是否同构
private boolean isomorphic(BinaryNode<AnyType> t1, BinaryNode<AnyType> t2) {// 如果两个树都为空，则是同构的if ( t1 == null )return t2 == null;// 如果一个树为空而另一个非空，则不是同构的if ( t2 == null )return false;// 递归检查左子树和右子树是否相同return isomorphic(t1.left, t2.left) && isomorphic(t1.right, t2.right);
}// 检查二叉树是否平衡（左右子树的高度差不超过 1）
private boolean balanced1(BinaryNode<AnyType> t) {// 如果节点为空，认为是平衡的if ( t == null )return true;// 递归检查左右子树是否平衡，并且左右子树的高度差不超过 1return balanced1(t.left) && balanced1(t.right) &&Math.abs(height(t.left) - height(t.right)) <= 1;
}private static final int NOT_BALANCED = -2;
// 检查二叉树是否平衡，并计算树的高度
private int balanced2(BinaryNode<AnyType> t) {// 如果节点为空，返回 -1 表示空树平衡if ( t == null )return -1;// 递归计算左子树的平衡状态和高度int l = balanced2(t.left);if ( l == NOT_BALANCED ) return NOT_BALANCED; // 如果左子树不平衡，返回标志// 递归计算右子树的平衡状态和高度int r = balanced2(t.right);if ( r == NOT_BALANCED ) return NOT_BALANCED; // 如果右子树不平衡，返回标志// 如果左右子树的高度差大于 1，表示不平衡if ( Math.abs(l - r) > 1 ) return NOT_BALANCED;// 返回当前树的高度return 1 + Math.max(l, r);
}// 使用 Optional 返回树是否平衡以及树的高度
private Optional<Integer> balanced22(BinaryNode<AnyType> t) {// 如果节点为空，返回 Optional.of(-1) 表示平衡的空树if ( t == null )return Optional.of(-1);// 递归检查左子树的平衡状态Optional<Integer> l = balanced22(t.left);if ( l.isEmpty() ) return Optional.empty(); // 如果左子树不平衡，返回空 Optional// 递归检查右子树的平衡状态Optional<Integer> r = balanced22(t.right);if ( r.isEmpty() ) return Optional.empty(); // 如果右子树不平衡，返回空 Optional// 如果左右子树的高度差大于 1，表示不平衡，返回空 Optionalif ( Math.abs(l.get() - r.get()) > 1 ) return Optional.empty();// 返回树的高度return Optional.of(1 + Math.max(l.get(), r.get()));
}// 检查二叉树是否 shapely (符合一定的形状约束)
// 高度不应大于 lowness 的两倍
private boolean shapely1(BinaryNode<AnyType> t) {// 如果节点为空，认为是 shapelyif ( t == null )return true;// 计算当前节点的高度和 lownessint height = height(t);int lowness = lowness(t);// 递归检查左右子树是否符合 shapely 约束return shapely1(t.left) && shapely1(t.right) && height <= 2 * lowness;
}// 记录树的高度和 lowness 的类
private record Pair(int height, int lowness) {}// 默认叶子节点的高度和 lowness
private final Pair leafPair = new Pair(-1, -1);// 检查树是否 shapely2 (符合形状约束)
public boolean shapely2() {// 调用 shapely2 方法检查根节点Pair p = shapely2(this);return p != null; // 如果返回非空值，表示树是 shapely 的
}// 递归检查树的形状是否符合约束
private Pair shapely2(BinaryNode<AnyType> t) {// 如果是叶子节点，返回默认的叶子节点高度和 lownessif ( t.left == null && t.right == null )return leafPair;int lowness, height;// 如果没有右子树，递归检查左子树if ( t.right == null ) {Pair l = shapely2(t.left);if ( l == null ) return null; // 如果左子树不符合要求，返回 nulllowness = 1 + l.lowness;height = 1 + l.height;}// 如果没有左子树，递归检查右子树else if ( t.left == null ) {Pair r = shapely2(t.right);if ( r == null ) return null; // 如果右子树不符合要求，返回 nulllowness = 1 + r.lowness;height = 1 + r.height;}// 如果左右子树都存在，递归检查左右子树else {Pair l = shapely2(t.left);if ( l == null ) return null; // 如果左子树不符合要求，返回 nullPair r = shapely2(t.right);if ( r == null ) return null; // 如果右子树不符合要求，返回 nullheight = 1 + Math.max(l.height, r.height); // 当前树的高度是左右子树高度的最大值加 1lowness = 1 + Math.min(l.lowness, r.lowness); // 当前树的 lowness 是左右子树 lowness 的最小值加 1}// 如果高度不大于 lowness 的两倍，则返回当前的 Pair，否则返回 nullif ( height <= 2 * lowness )return new Pair(height, lowness);return null;
}Binary Search Trees
java">private BinaryNode add(AnyType x, BinaryNode t) {if (t == null)return new BinaryNode(x); // 如果树为空，创建一个新的节点返回int compareResult = x.compareTo(t.element); // 比较 x 和当前节点 t.element 的大小if (compareResult < 0) // 如果 x 比当前节点小，插入到左子树t.left = add(x, t.left);else if (compareResult > 0) // 如果 x 比当前节点大，插入到右子树t.right = add(x, t.right);return t; // 返回当前节点 t（树的结构可能发生变化，但节点本身不变）
}
private BinaryNode remove(AnyType x, BinaryNode t) {if (t == null)return t; // 如果树为空，返回 null，表示没有找到该元素int compareResult = x.compareTo(t.element); // 比较 x 和当前节点 t.element 的大小if (compareResult < 0) // 如果 x 比当前节点小，从左子树删除t.left = remove(x, t.left);else if (compareResult > 0) // 如果 x 比当前节点大，从右子树删除t.right = remove(x, t.right);else if (t.left != null && t.right != null) { // 当前节点有两个子节点t.element = findMax(t.left).element; // 找到左子树中的最大元素t.left = remove(t.element, t.left); // 删除最大元素}elset = (t.left != null) ? t.left : t.right; // 当前节点只有一个子节点或没有子节点return t; // 返回当前节点
}
