模块 07: 递归、树与图

递归函数在更小子问题上调用自身，基础情况不再调用。非负阶乘满足 fact(0)=1、fact(n)=n×fact(n−1)。每个未完成调用在栈中保存局部状态，返回时逐层展开。需证明非负度量递减，仅有基础情况不保证终止。深递归消耗栈，Python 限制深度，大输入可用迭代或显式栈。

有根树有根及父子结构，无环。二叉树每节点最多两子节点。前序为节点、左、右，中序为左、节点、右，后序为左、右、节点。二叉搜索树左右键满足大小约束，所以中序有序。高度控制搜索成本：平衡树对数高度，链形树线性高度。实验用嵌套元组，而非完整可变搜索树。

图由顶点和边组成，边可有向、无向或带权。邻接表通常 O(V+E) 存储，邻接矩阵 O(V²) 并支持直接查边。图可有环和多路径，遍历需访问状态。安排处理时就标记，避免重复入队。需规定孤立点、未知端点及平行边。

DFS 先深入分支，用递归或显式栈。BFS 用队列，按到起点的边距离非递减访问。邻接表和常数访问检查下，两者 O(V+E)。BFS 首次发现节点时保存前驱，逆向追踪可恢复路线。DFS 可找路线，但通常不保证边数最少。

BFS 在等边成本时最小化边数。非负不同权重可用 Dijkstra，反复确定暂定距离最小节点并松弛出边，优先队列帮助选择。成本百的一条边输给两条成本一的边。负权破坏 Dijkstra 的确定论证，需要其他算法。称最短之前需说明目标，并区分不可达与未知顶点。

下载脚本，在终端中使用 Python 3.11 或更新版本运行：python m07_tree.py. Windows 也可使用 py -3；部分系统使用 python3。实验仅用标准库。先预测结果，再运行并完成变体。不要使用 -O，以保留断言。下方输出由构建器实际运行捕获，两种语言使用相同代码与输出。

画树、预测遍历与高度，跟踪 None 基础情况。

下载 m07_tree.py

"""Recursive traversal with an explicit empty-tree base case."""
def inorder(node):
    if node is None:
        return []
    value, left, right = node
    return inorder(left) + [value] + inorder(right)

def height(node):
    if node is None:
        return 0
    return 1 + max(height(node[1]), height(node[2]))

tree = (4, (2, (1, None, None), (3, None, None)), (6, None, None))
print("inorder:", inorder(tree))
print("height:", height(tree))
assert inorder(tree) == [1, 2, 3, 4, 6]
assert inorder(None) == [] and height(None) == 0

inorder: [1, 2, 3, 4, 6]
height: 3

1. 实现前序。
2. 构建三节点链。
3. 解释反复拼接列表的复制成本。

图包含环与孤立点，BFS 发现时记录前驱，不可达返回 None。

下载 m07_routes.py

"""BFS finds a shortest path measured in edges in an unweighted graph."""
from collections import deque
def route(graph, start, goal):
    if start not in graph or goal not in graph:
        raise KeyError("unknown vertex")
    queue, parent = deque([start]), {start: None}
    while queue:
        vertex = queue.popleft()
        if vertex == goal:
            path = []
            while vertex is not None:
                path.append(vertex); vertex = parent[vertex]
            return path[::-1]
        for neighbour in graph[vertex]:
            if neighbour not in parent:
                parent[neighbour] = vertex; queue.append(neighbour)
    return None

graph = {"A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D"], "D": ["B", "C"], "E": []}
print("A to D:", route(graph, "A", "D"))
print("A to E:", route(graph, "A", "E"))
assert route(graph, "A", "D") == ["A", "B", "D"]
assert route(graph, "A", "A") == ["A"]
assert route(graph, "A", "E") is None

A to D: ['A', 'B', 'D']
A to E: None

1. 交换 A 邻居顺序。
2. 加入 D 与 E 的双向边。
3. 查询未知点，对比不可达 E。

先尝试，再展开解答。★ 应用概念；★★ 结合概念；★★★ 进行设计或证明。

选择答案查看反馈，重置后可重做。无需 JavaScript 也可阅读答案表。

• MIT 算法讲义 — 阅读图搜索与最短路径，区分目标。

跟踪不可达与等长路径的前驱，解释递归空情况。模块 08 将比较更广泛设计策略。