♻️ 数据结构：树与图

树结构

I. 二叉树基础

1. 二叉树遍历方式

前序遍历（根-左-右）：先访问根节点，然后左子树，最后右子树
中序遍历（左-根-右）：先左子树，然后根节点，最后右子树
后序遍历（左-右-根）：先左子树，然后右子树，最后根节点
层序遍历（BFS）：按层次从上到下，从左到右访问

2. 二叉树性质

第 i 层最多有 2^(i-1) 个节点
深度为 k 的二叉树最多有 2^k - 1 个节点
对于完全二叉树，数组索引关系：左孩子 2i+1，右孩子 2i+2，父节点 (i-1)/2

II. 二叉搜索树（BST）

1. 定义

左子树所有节点值 < 根节点值
右子树所有节点值 > 根节点值
左右子树也分别是 BST

2. 时间复杂度

平均情况：查找、插入、删除 O(logn)
最坏情况（退化为链表）：O(n)

3. Java 实现

java

// TreeMap、TreeSet 底层使用红黑树（BST 的平衡版本）
// 特点：有序存储，支持范围查询

III. 平衡二叉树

1. AVL 树

定义：左右子树高度差绝对值不超过 1
平衡因子：左子树高度 - 右子树高度
旋转操作：
- 左旋（RR 型）
- 右旋（LL 型）
- 左右旋（LR 型）
- 右左旋（RL 型）
特点：查找效率高，但插入/删除频繁旋转，适合读多写少

2. 红黑树

性质：
- 节点红色或黑色
- 根节点黑色
- 叶子节点（NIL）黑色
- 红色节点的两个子节点都是黑色（不能有连续红节点）
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点
对比 AVL：
- 查找性能略逊于 AVL（最多 2 倍差距）
- 插入/删除只需最多 3 次旋转，性能更优
- 应用：HashMap 1.8、TreeMap、TreeSet

IV. 堆（Heap）

1. 定义

完全二叉树结构
大顶堆：每个节点 >= 子节点（根最大）
小顶堆：每个节点 <= 子节点（根最小）

2. Java 实现

java

// PriorityQueue 优先队列（默认小顶堆）
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);

3. 时间复杂度

插入：O(logn)
删除堆顶：O(logn)
查看堆顶：O(1)
建堆：O(n)

4. 应用场景

Top K 问题
堆排序
合并 K 个有序链表
中位数查找

V. 并查集

1. 定义

用于处理不相交集合的合并与查询问题
核心操作：find（查找根节点）、union（合并两个集合）

2. 优化策略

路径压缩：find 时将节点直接指向根节点
按秩合并：将矮树挂到高树下

3. Java 实现

java

int[] parent;
int[] rank;

public int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]); // 路径压缩
    }
    return parent[x];
}

public void union(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX != rootY) {
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }
}

4. 应用

连通性问题（朋友圈数量、岛屿数量）
Kruskal 最小生成树算法
动态连通性

图结构

I. 图的存储方式

1. 邻接矩阵

结构：二维数组 matrix[n][n]
优点：O(1) 判断两点是否相连，适合稠密图
缺点：空间 O(V²)，稀疏图浪费空间

2. 邻接表

结构：数组 + 链表/Map<节点, List<邻居>>
优点：空间 O(V + E)，适合稀疏图
缺点：判断两点是否相连 O(V)
Java 实现：Map<Integer, List<Integer>> graph

II. 图的遍历

1. 深度优先搜索（DFS）

思路：一条路走到黑，撞墙回溯
实现：递归或栈
应用：路径查找、拓扑排序、连通分量

java

void dfs(int node, boolean[] visited, Map<Integer, List<Integer>> graph) {
    visited[node] = true;
    for (int neighbor : graph.get(node)) {
        if (!visited[neighbor]) {
            dfs(neighbor, visited, graph);
        }
    }
}

2. 广度优先搜索（BFS）

思路：层层向外扩展
实现：队列
应用：最短路径（无权图）、层级遍历

java

void bfs(int start, Map<Integer, List<Integer>> graph) {
    Queue<Integer> queue = new LinkedList<>();
    boolean[] visited = new boolean[graph.size()];
    queue.offer(start);
    visited[start] = true;

    while (!queue.isEmpty()) {
        int node = queue.poll();
        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                queue.offer(neighbor);
            }
        }
    }
}

III. 最短路径算法

1. Dijkstra 算法（单源正权边）

适用：非负权图
思路：贪心 + 优先队列，每次选距离最小的未访问节点
时间复杂度：O((V + E)logV)
缺点：无法处理负权边

java

int[] dijkstra(int start, int n, Map<Integer, List<int[]>> graph) {
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[start] = 0;

    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
    pq.offer(new int[]{start, 0});

    while (!pq.isEmpty()) {
        int[] curr = pq.poll();
        int node = curr[0], distance = curr[1];

        if (distance > dist[node]) continue;

        for (int[] edge : graph.get(node)) {
            int neighbor = edge[0], weight = edge[1];
            if (dist[node] + weight < dist[neighbor]) {
                dist[neighbor] = dist[node] + weight;
                pq.offer(new int[]{neighbor, dist[neighbor]});
            }
        }
    }
    return dist;
}

2. Bellman-Ford 算法（单源可负权）

适用：可处理负权边，检测负权环
时间复杂度：O(VE)
思路：松弛所有边 V-1 次

3. Floyd-Warshall 算法（多源最短路径）

适用：任意两点间最短路径
时间复杂度：O(V³)
思路：动态规划，dp[i][j][k] = min(dp[i][j][k-1], dp[i][k][k-1] + dp[k][j][k-1])

java

void floydWarshall(int[][] graph) {
    int n = graph.length;
    int[][] dist = new int[n][n];

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dist[i][j] = graph[i][j];
        }
    }

    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][k] != Integer.MAX_VALUE && dist[k][j] != Integer.MAX_VALUE) {
                    dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
}

IV. 最小生成树（MST）

1. Prim 算法（加点法）

思路：从任意点开始，每次选距离已选集合最近的未选点
时间复杂度：O((V + E)logV)（优先队列优化）
适用：稠密图

2. Kruskal 算法（加边法）

思路：按边权排序，从小到大加边，用并查集判断是否成环
时间复杂度：O(ElogE)
适用：稀疏图

java

int kruskal(int n, int[][] edges) {
    Arrays.sort(edges, (a, b) -> a[2] - b[2]); // 按权排序
    UnionFind uf = new UnionFind(n);
    int mstWeight = 0;

    for (int[] edge : edges) {
        int u = edge[0], v = edge[1], weight = edge[2];
        if (uf.find(u) != uf.find(v)) {
            uf.union(u, v);
            mstWeight += weight;
        }
    }
    return mstWeight;
}

V. 拓扑排序

1. 定义

对有向无环图（DAG） 的顶点排序，使得每条边 uv 在排序中 u 出现在 v 之前

2. 实现方式

Kahn 算法（BFS）：
1. 统计入度
2. 入度为 0 的节点入队列
3. 弹出节点，更新邻居入度，重复

java

List<Integer> topologicalSort(int numCourses, int[][] prerequisites) {
    List<Integer> result = new ArrayList<>();
    int[] inDegree = new int[numCourses];
    Map<Integer, List<Integer>> graph = new HashMap<>();

    // 建图 + 统计入度
    for (int[] edge : prerequisites) {
        int from = edge[1], to = edge[0];
        graph.computeIfAbsent(from, k -> new ArrayList<>()).add(to);
        inDegree[to]++;
    }

    // 入度为 0 的节点入队列
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < numCourses; i++) {
        if (inDegree[i] == 0) {
            queue.offer(i);
        }
    }

    // BFS
    while (!queue.isEmpty()) {
        int node = queue.poll();
        result.add(node);
        for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
            if (--inDegree[neighbor] == 0) {
                queue.offer(neighbor);
            }
        }
    }

    return result.size() == numCourses ? result : new ArrayList<>(); // 判断是否有环
}

3. 应用

课程选修顺序
任务调度
编译依赖解析

VI. 图的其他重要概念

1. 有向图与无向图

有向图：边有方向（a→b 不等于 b→a）
无向图：边无方向（可视为双向的有向图）

2. 度

无向图：度 = 与节点相连的边数
有向图：
- 入度：指向该节点的边数
- 出度：从该节点指出的边数

3. 连通性

连通图：任意两点可达
强连通：有向图中任意两点互相可达
连通分量：极大连通子图

4. 图的类型

DAG（有向无环图）：无环的有向图，拓扑排序的前提
完全图：任意两点都有边
二分图：顶点可分为两组，同组内无边相连

典型面试题

树相关

二叉树的最大深度：DFS 或 BFS
翻转二叉树：递归交换左右子树
验证二叉搜索树：中序遍历是否递增
二叉树的最近公共祖先（LCA）：后序遍历
从前序与中序遍历序列构造二叉树：递归建树
二叉树展开为链表：前序遍历 + 右指针修改

图相关

岛屿数量：DFS/BFS 遍历网格
课程表（课程排序）：拓扑排序
网络延迟时间：Dijkstra 最短路径
克隆图：BFS/DFS 深拷贝
最小生成树：Prim 或 Kruskal
单词接龙（Word Ladder）：BFS + 图建模

参考资料

Java TreeMap 源码（红黑树实现）
Java PriorityQueue 源码（堆实现）
《算法（第 4 版）》- 树与图章节
LeetCode 题号：94/104/98/236/200/207/743

♻️ 数据结构：树与图 ​

树结构 ​

I. 二叉树基础 ​

1. 二叉树遍历方式 ​

2. 二叉树性质 ​

II. 二叉搜索树（BST） ​

1. 定义 ​

2. 时间复杂度 ​

3. Java 实现 ​

III. 平衡二叉树 ​

1. AVL 树 ​

2. 红黑树 ​

IV. 堆（Heap） ​

1. 定义 ​

2. Java 实现 ​

3. 时间复杂度 ​

4. 应用场景 ​

V. 并查集 ​

1. 定义 ​

2. 优化策略 ​

3. Java 实现 ​

4. 应用 ​

图结构 ​

I. 图的存储方式 ​

1. 邻接矩阵 ​

2. 邻接表 ​

II. 图的遍历 ​

1. 深度优先搜索（DFS） ​

2. 广度优先搜索（BFS） ​

III. 最短路径算法 ​

1. Dijkstra 算法（单源正权边） ​

2. Bellman-Ford 算法（单源可负权） ​

3. Floyd-Warshall 算法（多源最短路径） ​

IV. 最小生成树（MST） ​

1. Prim 算法（加点法） ​

2. Kruskal 算法（加边法） ​

V. 拓扑排序 ​

1. 定义 ​

2. 实现方式 ​

3. 应用 ​

VI. 图的其他重要概念 ​

1. 有向图与无向图 ​

2. 度 ​

3. 连通性 ​

4. 图的类型 ​

典型面试题 ​

树相关 ​

图相关 ​

参考资料 ​

♻️ 数据结构：树与图

树结构

I. 二叉树基础

1. 二叉树遍历方式

2. 二叉树性质

II. 二叉搜索树（BST）

1. 定义

2. 时间复杂度

3. Java 实现

III. 平衡二叉树

1. AVL 树

2. 红黑树

IV. 堆（Heap）

1. 定义

2. Java 实现

3. 时间复杂度

4. 应用场景

V. 并查集

1. 定义

2. 优化策略

3. Java 实现

4. 应用

图结构

I. 图的存储方式

1. 邻接矩阵

2. 邻接表

II. 图的遍历

1. 深度优先搜索（DFS）

2. 广度优先搜索（BFS）

III. 最短路径算法

1. Dijkstra 算法（单源正权边）

2. Bellman-Ford 算法（单源可负权）

3. Floyd-Warshall 算法（多源最短路径）

IV. 最小生成树（MST）

1. Prim 算法（加点法）

2. Kruskal 算法（加边法）

V. 拓扑排序

1. 定义

2. 实现方式

3. 应用

VI. 图的其他重要概念

1. 有向图与无向图

2. 度

3. 连通性

4. 图的类型

典型面试题

树相关

图相关

参考资料