AI Agent Engineer

AI Agent Engineer

树与层级遍历

5 min read

树与层级遍历

本节目标

用树表达单一根下的层级关系，掌握根、父子、叶、深度与子树，并分别用深度优先（DFS）和广度优先（BFS）遍历，同时限制不可信嵌套深度和节点数。

树：一个节点到多个子节点

树常用术语：根、父节点、子节点、叶节点、深度。文件目录、JSON 嵌套对象和决策步骤都可看作树。

tree = {
    "label": "root",
    "children": [
        {"label": "option-a", "children": []},
        {"label": "option-b", "children": []},
    ],
}

遍历时要明确深度优先（先走到底）还是广度优先（逐层处理）。二者都会访问每个节点一次，差别在访问顺序和辅助空间。

迭代式 DFS

def node_parts(value: object) -> tuple[str, list[object]]:
    if not isinstance(value, dict):
        raise ValueError("树节点必须是对象")
    if set(value) != {"label", "children"}:
        raise ValueError("树节点字段必须恰好为 label 和 children")
    label = value["label"]
    children = value["children"]
    if not isinstance(label, str) or not isinstance(children, list):
        raise ValueError("树节点格式非法")
    return label, children
 
 
def dfs_labels(root: object, *, max_nodes: int = 1_000) -> list[str]:
    if max_nodes < 1:
        raise ValueError("max_nodes 必须至少为 1")
    result: list[str] = []
    stack = [root]
    while stack:
        if len(result) >= max_nodes:
            raise ValueError("树节点数超过上限")
        node = stack.pop()
        label, children = node_parts(node)
        result.append(label)
        # 逆序压栈，使原 children 的左侧先访问。
        stack.extend(reversed(children))
    return result

显式栈避免用 Python 递归深度当作输入控制，但仍必须限制总节点数、最大深度和单节点子项数。这里为突出遍历省略了完整递归 schema 校验；不可信输入应在遍历前或遍历中逐层验证。

BFS 与层级

from collections import deque
 
 
def bfs_levels(
    root: object, *, max_depth: int = 100, max_nodes: int = 1_000
) -> list[tuple[int, str]]:
    if max_depth < 0 or max_nodes < 1:
        raise ValueError("max_depth/max_nodes 上限非法")
    result: list[tuple[int, str]] = []
    queue = deque([(root, 0)])
    while queue:
        if len(result) >= max_nodes:
            raise ValueError("树节点数超过上限")
        node, depth = queue.popleft()
        if depth > max_depth:
            raise ValueError("树深度超过上限")
        label, children = node_parts(node)
        result.append((depth, label))
        queue.extend((child, depth + 1) for child in children)
    return result

BFS 适合逐层展示或找最浅满足条件节点；DFS 适合子树处理、路径搜索和显式进入/退出语义。两者都不是自动的“最佳选择”。

树、DAG 与普通图

树通常有一个根，每个非根节点只有一个父节点且不存在环。DAG 可让一个节点有多个前驱；普通图还可能含环。一个文件夹层级是树，但“笔记互相链接”通常是图。不要因为数据用嵌套 JSON 表示，就假定业务关系必然是树。

资源与安全边界

  • 限制最大深度、总节点数、每节点子项数和标签长度；
  • 不让用户输入直接控制无限递归；
  • 若结构可共享节点或出现回边，使用 visited，否则它已不是严格树；
  • 明确输出顺序，不能依赖集合迭代；
  • 计算路径时决定复制列表还是用父指针重建，避免大量路径副本。

练习

  1. 把一个三层文件目录画成树，标出根、内部节点、叶和最大深度。
  2. 对同一棵 7 节点树手算 DFS 与 BFS 顺序，再运行代码验证。
  3. 扩展 BFS：超过 max_depth 立即失败，并为边界值写测试。
  4. 写 leaf_labels(root)，不修改输入；测试空子项、单节点和多分支。
  5. 举例说明一个“看起来像层级”但实际允许多父节点的 DAG。

自测

  1. 树中的根、叶和深度分别是什么？
  2. DFS 与 BFS 各使用什么辅助结构？
  3. 迭代式 DFS 为什么仍需深度/节点上限？
  4. 多个父节点的层级关系还是严格树吗？
  5. 若输入可能含回边，为什么要使用 visited？

下一步与相关概念

下一节：图、依赖与拓扑顺序。

参考资料

获取日期：2026-07-14。

Backlinks