【UCB CS 61B SP24】Lecture 22 23: Tree and Graph Traversals, DFS, BFS 学习笔记

本文讲解了二叉树的四种遍历方式，以及如何通过前/后序遍历与中序遍历重建出二叉树，接着介绍了新的非线性数据结构：图，详细讲解了图的存储方式与遍历方式，最后使用 Java 基于邻接表的存储方式实现了图与 DFS、BFS 两种遍历方式。

1. 二叉树的遍历与创建

1.1 遍历方式

二叉树的遍历方式有四种：前序遍历（Preorder Traversal）、中序遍历（Inorder Traversal）、后序遍历（Postorder Traversal）以及层序遍历（Levelorder Traversal）。

（1）前序遍历

• 顺序：根节点 → 左子树 → 右子树
• 特点：先访问根节点，再递归遍历左子树和右子树。
• 应用：复制树的结构。

（2）中序遍历

• 顺序：左子树 → 根节点 → 右子树
• 特点：先遍历左子树，再访问根节点，最后遍历右子树。
• 应用：对二叉搜索树（BST）按升序输出节点（在 BST 那节课实现过一次了）。

（3）后序遍历

• 顺序：左子树 → 右子树 → 根节点
• 特点：先递归遍历左右子树，最后访问根节点。
• 应用：删除树或计算表达式树。

（4）层序遍历

• 顺序：按层级从上到下、从左到右逐层访问节点。
• 特点：使用队列辅助实现，非递归。
• 应用：按层级分析树的结构。

只要结合图片理解了这几种遍历逻辑后实现起来就不难，递归很适合用来实现前三种遍历方式，而且代码几乎一样，只是递归子树与输出节点之间的顺序不一样，Java 实现树的遍历代码如下：

package CS61B.Lecture22;import java.util.LinkedList;
import java.util.Queue;class TreeNode<T> {T val;TreeNode<T> left;TreeNode<T> right;public TreeNode(T val) {this.val = val;this.left = null;this.right = null;}
}public class BinaryTreeTraversal {/** 前序遍历 */public static void preOrderTraversal(TreeNode root) {if (root == null) return;System.out.print(root.val + " ");preOrderTraversal(root.left);preOrderTraversal(root.right);}/** 中序遍历 */public static void inOrderTraversal(TreeNode root) {if (root == null) return;inOrderTraversal(root.left);System.out.print(root.val + " ");inOrderTraversal(root.right);}/** 后序遍历 */public static void postOrderTraversal(TreeNode root) {if (root == null) return;postOrderTraversal(root.left);postOrderTraversal(root.right);System.out.print(root.val + " ");}/** 层序遍历 */public static void levelOrderTraversal(TreeNode root) {Queue<TreeNode> Q = new LinkedList<>();Q.offer(root);while (Q.peek() != null) {TreeNode node = Q.poll();System.out.print(node.val + " ");if (node.left != null) Q.offer(node.left);if (node.right != null) Q.offer(node.right);}}/** 测试 */public static void main(String[] args) {// 构建示例二叉树//       D//   B       F// A   C   E   GTreeNode<Character> root = new TreeNode<>('D');root.left = new TreeNode<>('B');root.right = new TreeNode<>('F');root.left.left = new TreeNode<>('A');root.left.right = new TreeNode<>('C');root.right.left = new TreeNode<>('E');root.right.right = new TreeNode<>('G');preOrderTraversal(root);  // D B A C F E GSystem.out.println();inOrderTraversal(root);  // A B C D E F GSystem.out.println();postOrderTraversal(root);  // A C B E G F DSystem.out.println();levelOrderTraversal(root);  // D B F A C E GSystem.out.println();}
}

1.2 递归建树

在已知前/后序遍历与中序遍历的结果时，我们可以根据遍历结果把二叉树重建出来，其原理如下：

• 必须包含中序遍历：中序的“左根右”结构是分割左右子树的关键。
• 前序/后序提供根节点：前序首元素或后序末元素为根节点。
• 唯一性条件：仅当已知树是满二叉树时，前序 + 后序可唯一确定二叉树。

前序 + 中序构建二叉树的核心思想为：

• 找出根节点：前序数组的第一个元素即为根节点。
• 分割中序数组：根据根节点将中序数组分为左子树和右子树。
• 分割前序数组：根据左子树的节点数量，确定前序数组中左子树和右子树的范围（左子树的节点在前序数组中一定是在根节点之后连续分布，左子树后剩余的其他节点即为右子树节点）。
• 递归构建：递归处理左子树和右子树。

根据前序遍历与中序遍历创建二叉树的过程如下图所示，其中红色表示当前正在处理的根节点，紫色表示已经创建好节点，绿色表示要递归处理的左子树，蓝色表示要递归处理的右子树：

• 步骤一：前序数组的第一个元素 D 为根节点，在中序数组中找到 D 并建立根节点，然后将 D 的两侧分为左右子树，首先递归在左子树 [B, A, C] 中处理；
• 步骤二：左子树 [B, A, C] 的第一个元素 B 为根节点，在中序数组中找到 B 并建立根节点，然后将 B 的两侧分为左右子树，首先递归在左子树 [A] 中处理；
• 步骤三：左子树 [A] 的第一个元素 A 为根节点，在中序数组中找到 A 并建立根节点，A 的两侧要么为空要么为已经建好的节点，说明 A 已经是叶子节点了，回溯到 B，递归在右子树 [C] 中处理；
• 步骤四：右子树 [C] 的第一个元素 C 为根节点，在中序数组中找到 C 并建立根节点，C 的两侧均为已经建好的节点，说明 C 已经是叶子节点了，回溯到 B，B 的左右子树已经递归建好树了，回溯到 D，递归在右子树 [F, E, G] 中处理；
• 后续步骤原理与之前一样，就不继续讲解了。

后序 + 中序构建二叉树的核心思想为：

• 找出根节点：后序数组的最后一个元素即为根节点。
• 分割中序数组：根据根节点分割中序数组。
• 分割后序数组：根据左子树的节点数量，确定后序数组中左子树和右子树的范围。
• 递归构建：递归处理左子树和右子树。

Java 实现递归建树代码如下，用到的节点 TreeNode 与遍历方法为上一小节中实现的：

package CS61B.Lecture22;public class BuildBinaryTree {/** 根据前序 + 中序遍历构建二叉树 */public static TreeNode buildTreeFromPreIn(Comparable[] pre, Comparable[] in) {return buildTreeFromPreIn(pre, 0, pre.length - 1, in, 0, in.length - 1);}/** 递归建树 */private static TreeNode buildTreeFromPreIn(Comparable[] pre, int preStart, int preEnd,Comparable[] in, int inStart, int inEnd) {if (preStart > preEnd) return null;  // 终止条件：前序数组为空TreeNode root = new TreeNode(pre[preStart]);  // 前序数组的第一个元素是当前子树的根节点int k = inStart;while (in[k].compareTo(pre[preStart]) != 0) k++;  // 在中序数组中找到根节点的位置int leftChildNums = k - inStart;  // 计算左子树的节点数量// 递归构建左子树和右子树root.left = buildTreeFromPreIn(pre, preStart + 1, preStart + leftChildNums, in, inStart, k - 1);root.right = buildTreeFromPreIn(pre, preStart + leftChildNums + 1, preEnd, in, k + 1, inEnd);return root;}/** 根据后序 + 中序遍历构建二叉树 */public static TreeNode buildTreeFromPostIn(Comparable[] post, Comparable[] in) {return buildTreeFromPostIn(post, 0, post.length - 1, in, 0, in.length - 1);}/** 递归建树 */private static TreeNode buildTreeFromPostIn(Comparable[] post, int postStart, int postEnd,Comparable[] in, int inStart, int inEnd) {if (postStart > postEnd) return null;  // 终止条件：后序数组为空TreeNode root = new TreeNode(post[postEnd]);  // 后序数组的最后一个元素是当前子树的根节点int k = inStart;while (in[k].compareTo(post[postEnd]) != 0) k++;  // 在中序数组中找到根节点的位置int leftChildNums = k - inStart;  // 计算左子树的节点数量// 递归构建左子树和右子树root.left = buildTreeFromPostIn(post, postStart, postStart + leftChildNums - 1, in, inStart, k - 1);root.right = buildTreeFromPostIn(post, postStart + leftChildNums, postEnd - 1, in, k + 1, inEnd);return root;}/** 测试 */public static void main(String[] args) {Character[] preorder = {'D', 'B', 'A', 'C', 'F', 'E', 'G'};Character[] inorder = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};Character[] postorder = {'A', 'C', 'B', 'E', 'G', 'F', 'D'};// 根据前序 + 中序遍历构建二叉树TreeNode rootFromPreIn = buildTreeFromPreIn(preorder, inorder);BinaryTreeTraversal.preOrderTraversal(rootFromPreIn);  // D B A C F E GSystem.out.println();BinaryTreeTraversal.inOrderTraversal(rootFromPreIn);  // A B C D E F GSystem.out.println();// 根据后序 + 中序遍历构建二叉树TreeNode rootFromPostIn = buildTreeFromPostIn(postorder, inorder);BinaryTreeTraversal.postOrderTraversal(rootFromPostIn);  // A C B E G F DSystem.out.println();BinaryTreeTraversal.inOrderTraversal(rootFromPostIn);  // A B C D E F GSystem.out.println();}
}

2. 图的概念及其遍历方式

2.1 介绍

与树类似，图（Graph）也是一种非线性数据结构，由顶点（Vertex/Node）和边（Edge）组成。

• 顶点：图的基本元素，表示实体，可以存储数据（如用户 ID、城市名称等）。
• 边：表示顶点之间的关系（如社交关系、道路、超链接等），其中又分为简单边（连接两个顶点）、带权边（附加数值信息如距离、成本）以及自环边（顶点与自身相连的边）。
• 数学表示：通常表示为 $G=(V,E)$，其中 $V$ 是顶点集合，$E$ 是边集合。
• 路径（Path）：由顶点序列 $v_1,v_2,\dots ,v_n$ 组成，其中每对相邻顶点由边连接，路径分为简单路径（路径中不重复经过顶点）与环（起点和终点相同的路径）。

图有多种类型，分为有向图、无向图、有环图、无环图、且图的边是可以带权重的。其中无向图的边没有方向，若顶点 $u$ 与 $v$ 之间有边，则 $(u,v)$ 与 $(v,u)$ 表示同一概念；有向图的边表示为 $<u,v>$，表示从 $u$ 指向 $v$。

其他特殊图：

• 完全图：每对顶点之间都有边；
• 稀疏图与稠密图：边数远少于 $V^2$ 的图为稀疏图，反之为稠密图；
• 连通图：任意两个顶点之间都有路径；
• 树：无环的连通图（树是图的特例）。

图的相关术语：

• 度（Degree）：与顶点相连的边数。在有向图中又分为入度（In-degree）和出度（Out-degree）。
• 子图（Subgraph）：由原图的部分顶点和边组成。
• 连通分量（Connected Component）：无向图中的极大连通子图。
• 强连通图（Strongly Connected Graph）：有向图中任意两顶点互相可达。

2.2 图的存储与遍历方式

图有以下几种存储方式：

(1) 邻接矩阵（Adjacency Matrix）

• 实现方法：使用二维数组 $G$ 表示，其中 $G[i][j]=true$ 表示顶点 $i$ 与 $j$ 之间有边，否则表示无边。无向图的邻接矩阵一定是对称的
• 优点：能够快速判断两顶点是否邻接，时间复杂度为 $O(1)$。
• 缺点：数组的宽高取决于顶点数，空间复杂度为 $O(V^2)$，不适合稀疏图。

(2) 邻接表（Adjacency List）

• 实现方法：每个顶点维护一个链表，存储其邻接的顶点。
• 优点：空间复杂度为 $O(V+E)$，适合稀疏图。
• 缺点：判断两顶点是否邻接需要遍历链表，时间复杂度为 $O(V)$。

(3) 其他存储方式

• 边列表（Edge List）：直接存储所有边的集合。
• 邻接多重表（Adjacency Multilist）：适用于无向图，优化边存储。

图的遍历方式最常用的有两种，分别是深度优先搜索（Depth-First Search，DFS）与广度优先搜索（Breadth-First Search，BFS）。

DFS 的核心思想是从起点出发，尽可能深地探索分支，直到无法继续，再回溯到上一个分叉点搜索其他分支，一般使用递归或栈实现，优先访问未探索的邻接顶点。DFS 适用于拓扑排序、连通性检测、寻找路径、解决迷宫问题。

BFS 的核心思想是从起点出发，逐层向外扩展，先访问完最近的所有邻接顶点，再访问下一层，一般使用队列实现，保证按层遍历。BFS 适用于最短路径（无权图）、社交网络中的层级关系、广播消息。

我们通过下图来简单说明一下 DFS 与 BFS 的区别，假设我们想从起点 S 开始遍历，走到终点 T 的位置结束，那么这两种搜索方式的过程可能是下面这样：

• DFS：假如第一步先搜到了 1，那么遵循一条分支走到底的原则，DFS 会先搜索完 1 -> 2 -> 5 -> 6 这条分支，发现没见到终点，因此开始回溯，而一路上的节点都没有分支，因此回溯到起点后才选另一条分支 3，在这条分支上继续往下搜索：3 -> 8，找到终点结束搜索。如果我们不结束继续搜索那么 DFS 就会从 8 继续往下搜到 4，因为只要当前有路可以走 DFS 就会一直走完，而不会回到起点走 0 -> 4 这条路。
• BFS：在起点时 BFS 就会将与其相邻的所有节点加入队列：Q = [1, 3, 4, 7]，然后开始遍历第一个节点 1，遍历的时候继续将当前节点相邻的点加入队列，此时 Q = [3, 4, 7, 2]，然后我们下一个遍历的队头节点是 3，遍历的时候发现与其相连的节点 8，加入队列：Q = [4, 7, 2, 8]。因此 BFS 是从起点开始，先遍历完与之相连接的最近的节点：1 -> 3 -> 4 -> 7，然后才会向外扩展到第二近的那层：2 -> 8，以此类推。

我们用 Java 实现一下这两种搜索方式，图采用邻接表的形式存储，测试时构建的图与上图一致，代码不难理解：

package CS61B.Lecture22;import java.util.LinkedList;
import java.util.List;
import java.util.Queue;public class Graph {private final int V;  // 节点数量private final LinkedList<Integer>[] adj;  // 邻接表public Graph(int v) {V = v;adj = new LinkedList[v];for (int i = 0; i < v; i++)adj[i] = new LinkedList<>();  // 每个节点都用一个列表存放其能到达的其他节点序号}/** 添加边 */public void addEdge(int u, int v) {adj[u].add(v);  // 将 v 添加到 u 的邻接表，表示 u 有一条边能走到 vadj[v].add(u);  // 无向图还需要反向添加，表示 v 也能走到 u}/** 深度优先搜索 */public void DFS(int s) {boolean[] vis = new boolean[V];  // 标记某个节点是否已经访问过System.out.print("DFS Result: ");DFS(s, vis);System.out.println();}/** DFS 递归实现 */private void DFS(int u, boolean[] vis) {vis[u] = true;  // 标记当前节点已访问System.out.print(u + " ");for (int v : adj[u])  // 遍历当前节点 u 的邻接表if (!vis[v]) DFS(v, vis);  // 如果 u 能走到 v 且 v 还未访问则递归搜索 v}/** 广度优先搜索 */public void BFS(int s) {System.out.print("BFS Result: ");boolean[] vis = new boolean[V];Queue<Integer> q = new LinkedList<>(List.of(s));vis[s] = true;while (!q.isEmpty()) {int u = q.poll();System.out.print(u + " ");for (int v : adj[u])if (!vis[v]) {  // 将所有未访问的邻接顶点加入队列q.add(v);vis[v] = true;}}System.out.println();}/** 测试 */public static void main(String[] args) {Graph g = new Graph(10);for (int i : List.of(1, 3, 4, 7)) g.addEdge(0, i);g.addEdge(1, 2);g.addEdge(2, 5);g.addEdge(5, 6);g.addEdge(3, 8);g.addEdge(4, 8);g.DFS(0);  // DFS Result: 0 1 2 5 6 3 8 4 7g.BFS(0);  // BFS Result: 0 1 3 4 7 2 8 5 6}
}