wehub-skill-sync
14 KiB
14 KiB
树与图参考
二叉树
核心概念
二叉树是一种层次化数据结构，每个节点最多有两个子节点（左子节点与右子节点）。
关键属性：
- 每个节点最多有 2 个子节点
- 根节点没有父节点
- 叶节点没有子节点
- 高度：从根节点到叶节点的最长路径
- 深度：从根节点到某节点的距离
二叉树类型：
- 满二叉树：每个节点有 0 或 2 个子节点
- 完全二叉树：除最后一层外，所有层都被填满，且最后一层从左向右填充
- 完美二叉树：所有内部节点都有 2 个子节点，所有叶节点在同一层
- 平衡二叉树：左右子树的高度差 ≤ 1
节点结构
Python：
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
JavaScript：
class TreeNode {
constructor(val = 0, left = null, right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
树的遍历
1. 深度优先搜索（DFS）
中序遍历（左 → 根 → 右）
用途：BST 可得到有序序列
def inorder(root):
result = []
def traverse(node):
if not node:
return
traverse(node.left)
result.append(node.val)
traverse(node.right)
traverse(root)
return result
前序遍历（根 → 左 → 右）
用途：复制树、前缀表达式
def preorder(root):
result = []
def traverse(node):
if not node:
return
result.append(node.val)
traverse(node.left)
traverse(node.right)
traverse(root)
return result
后序遍历（左 → 右 → 根）
用途：删除树、后缀表达式
def postorder(root):
result = []
def traverse(node):
if not node:
return
traverse(node.left)
traverse(node.right)
result.append(node.val)
traverse(root)
return result
2. 广度优先搜索（BFS）
用途：层序遍历、无权重树中的最短路径
from collections import deque
def level_order(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue)
current_level = []
for _ in range(level_size):
node = queue.popleft()
current_level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(current_level)
return result
时间：O(n)，空间：O(w)，其中 w 为最大宽度
二叉搜索树（BST）
属性
- 左子树的值 < 节点值
- 右子树的值 > 节点值
- 左右子树也都是 BST
- 中序遍历得到有序序列
常见操作
查找
def search_bst(root, val):
if not root or root.val == val:
return root
if val < root.val:
return search_bst(root.left, val)
return search_bst(root.right, val)
时间：O(h)，其中 h 为高度（平衡时 O(log n)，最坏 O(n)）
插入
def insert_bst(root, val):
if not root:
return TreeNode(val)
if val < root.val:
root.left = insert_bst(root.left, val)
else:
root.right = insert_bst(root.right, val)
return root
删除
def delete_bst(root, val):
if not root:
return None
if val < root.val:
root.left = delete_bst(root.left, val)
elif val > root.val:
root.right = delete_bst(root.right, val)
else:
# 找到待删除节点
# 情况 1：无子节点
if not root.left and not root.right:
return None
# 情况 2：只有一个子节点
if not root.left:
return root.right
if not root.right:
return root.left
# 情况 3：有两个子节点
# 寻找中序后继（右子树中的最小值）
min_node = find_min(root.right)
root.val = min_node.val
root.right = delete_bst(root.right, min_node.val)
return root
def find_min(node):
while node.left:
node = node.left
return node
常见树算法
1. 树的高度/深度
def max_depth(root):
if not root:
return 0
return 1 + max(max_depth(root.left), max_depth(root.right))
2. 平衡树检查
def is_balanced(root):
def height(node):
if not node:
return 0
left_height = height(node.left)
if left_height == -1:
return -1
right_height = height(node.right)
if right_height == -1:
return -1
if abs(left_height - right_height) > 1:
return -1
return 1 + max(left_height, right_height)
return height(root) != -1
3. 最近公共祖先（BST）
def lowest_common_ancestor_bst(root, p, q):
if p.val < root.val and q.val < root.val:
return lowest_common_ancestor_bst(root.left, p, q)
if p.val > root.val and q.val > root.val:
return lowest_common_ancestor_bst(root.right, p, q)
return root
4. 二叉树的直径
def diameter_of_binary_tree(root):
diameter = 0
def height(node):
nonlocal diameter
if not node:
return 0
left = height(node.left)
right = height(node.right)
diameter = max(diameter, left + right)
return 1 + max(left, right)
height(root)
return diameter
5. 序列化与反序列化
def serialize(root):
"""将树编码为字符串。"""
def helper(node):
if not node:
return 'null,'
return str(node.val) + ',' + helper(node.left) + helper(node.right)
return helper(root)
def deserialize(data):
"""将字符串解码为树。"""
def helper(nodes):
val = next(nodes)
if val == 'null':
return None
node = TreeNode(int(val))
node.left = helper(nodes)
node.right = helper(nodes)
return node
return helper(iter(data.split(',')))
图
核心概念
图是由边连接的节点（顶点）集合。
类型：
- 有向图与无向图：边是否有方向
- 有权图与无权图：边是否带有权重
- 有环图与无环图：是否包含环
- 连通图与非连通图：所有节点之间是否存在路径
表示方法
1. 邻接表（最常用）
# 无向图
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
# 或使用 defaultdict
from collections import defaultdict
graph = defaultdict(list)
graph['A'].append('B')
graph['B'].append('A')
空间：O(V + E)
2. 邻接矩阵
# graph[i][j] = 1 表示存在从 i 到 j 的边
n = 5 # 顶点数
graph = [[0] * n for _ in range(n)]
graph[0][1] = 1 # 从 0 到 1 的边
graph[1][0] = 1 # 从 1 到 0 的边（无向）
空间：O(V²)
图的遍历
1. 深度优先搜索（DFS）
递归：
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(start)
for neighbor in graph[start]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
return visited
迭代（使用栈）：
def dfs_iterative(graph, start):
visited = set()
stack = [start]
while stack:
node = stack.pop()
if node not in visited:
visited.add(node)
print(node)
for neighbor in graph[node]:
if neighbor not in visited:
stack.append(neighbor)
return visited
时间：O(V + E)，空间：O(V)
2. 广度优先搜索（BFS）
from collections import deque
def bfs(graph, start):
visited = set([start])
queue = deque([start])
while queue:
node = queue.popleft()
print(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return visited
时间：O(V + E)，空间：O(V)
常见图算法
1. 环检测（无向图）
def has_cycle(graph):
visited = set()
def dfs(node, parent):
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
if dfs(neighbor, node):
return True
elif neighbor != parent:
return True # 发现环
return False
for node in graph:
if node not in visited:
if dfs(node, None):
return True
return False
2. 环检测（有向图）
def has_cycle_directed(graph):
WHITE, GRAY, BLACK = 0, 1, 2
color = {node: WHITE for node in graph}
def dfs(node):
color[node] = GRAY
for neighbor in graph[node]:
if color[neighbor] == GRAY:
return True # 发现回边
if color[neighbor] == WHITE and dfs(neighbor):
return True
color[node] = BLACK
return False
for node in graph:
if color[node] == WHITE:
if dfs(node):
return True
return False
3. 拓扑排序（DAG）
def topological_sort(graph):
visited = set()
stack = []
def dfs(node):
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs(neighbor)
stack.append(node)
for node in graph:
if node not in visited:
dfs(node)
return stack[::-1] # 反转
时间：O(V + E)
4. 最短路径（无权图 - BFS）
from collections import deque
def shortest_path_bfs(graph, start, end):
queue = deque([(start, [start])])
visited = set([start])
while queue:
node, path = queue.popleft()
if node == end:
return path
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, path + [neighbor]))
return None # 未找到路径
5. Dijkstra 算法（有权图）
import heapq
def dijkstra(graph, start):
"""找到从起点到所有节点的最短路径。"""
distances = {node: float('inf') for node in graph}
distances[start] = 0
pq = [(0, start)] # (距离, 节点)
while pq:
current_dist, current_node = heapq.heappop(pq)
if current_dist > distances[current_node]:
continue
for neighbor, weight in graph[current_node]:
distance = current_dist + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(pq, (distance, neighbor))
return distances
时间：O((V + E) log V)（使用最小堆）
6. 并查集（不相交集合）
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # 路径压缩
return self.parent[x]
def union(self, x, y):
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return False
# 按秩合并
if self.rank[root_x] < self.rank[root_y]:
self.parent[root_x] = root_y
elif self.rank[root_x] > self.rank[root_y]:
self.parent[root_y] = root_x
else:
self.parent[root_y] = root_x
self.rank[root_x] += 1
return True
用途：环检测、Kruskal 最小生成树、连通分量
常见图问题
1. 岛屿数量
def num_islands(grid):
if not grid:
return 0
count = 0
rows, cols = len(grid), len(grid[0])
def dfs(r, c):
if (r < 0 or r >= rows or c < 0 or c >= cols or
grid[r][c] == '0'):
return
grid[r][c] = '0' # 标记为已访问
dfs(r + 1, c)
dfs(r - 1, c)
dfs(r, c + 1)
dfs(r, c - 1)
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
count += 1
dfs(r, c)
return count
2. 课程表（环检测）
def can_finish(num_courses, prerequisites):
graph = defaultdict(list)
for course, prereq in prerequisites:
graph[course].append(prereq)
WHITE, GRAY, BLACK = 0, 1, 2
color = [WHITE] * num_courses
def has_cycle(course):
color[course] = GRAY
for prereq in graph[course]:
if color[prereq] == GRAY:
return True
if color[prereq] == WHITE and has_cycle(prereq):
return True
color[course] = BLACK
return False
for course in range(num_courses):
if color[course] == WHITE:
if has_cycle(course):
return False
return True
3. 克隆图
def clone_graph(node):
if not node:
return None
clones = {}
def dfs(node):
if node in clones:
return clones[node]
clone = Node(node.val)
clones[node] = clone
for neighbor in node.neighbors:
clone.neighbors.append(dfs(neighbor))
return clone
return dfs(node)
何时使用何种方法
树的遍历：
- DFS（中序）：BST → 有序序列
- DFS（前序）：复制树、前缀表示法
- DFS（后序）：删除树、后缀表示法
- BFS：层序遍历、最短路径
图的遍历：
- DFS：环检测、拓扑排序、连通分量
- BFS：最短路径（无权图）、按层探索
最短路径：
- BFS：无权图
- Dijkstra：有权图（非负权重）
- Bellman-Ford：有权图（可含负权重）
- Floyd-Warshall：所有点对最短路径
树/图表示选择：
- 邻接表：稀疏图（E << V²）
- 邻接矩阵：稠密图、快速边查询