树(Tree)

有根树把节点组织成层级,除根外每个节点只有一个父节点。它适合表示可递归分解的层级数据;一般无向树则是连通且无环的图。

一句话定义

有根树把节点组织成层级,除根外每个节点只有一个父节点。它适合表示可递归分解的层级数据;一般无向树则是连通且无环的图。

为什么重要

  • 层级数据无处不在:文件系统、HTML/DOM、JSON、组织架构、代码的语法树(AST)。
  • 许多高效结构都是特化的树:二叉搜索树、堆、Trie、B 树(数据库索引)、决策树(机器学习模型)。

使用边界

深度与高度有按边数、按层数计数的不同约定。本批示例的 height 返回层数,叶子高度为 1;共享子节点、符号链接或回指会让实际结构成为图。

原理 / 图解

图 1
术语 含义
根(root) 没有父节点的节点
叶子(leaf) 没有子节点的节点
深度 / 高度 深度常按根到节点的边数;本篇 height 示例按子树层数计高度,叶子高度为 1
子树 任一节点及其所有后代

一棵有 nn 个节点的树恰好有 n−1n-1 条边。树天然适合递归:一棵树 = 根 + 若干棵子树。

可运行示例

用类表示文件树,递归打印、求高度与叶子数、查找路径;再看 Python 自带的语法树 ast 和 JSON 嵌套结构(Python 3.15.0 一稿运行记录):

# 文件:examples/13_tree.py
# 树:有层级、无环的结构。文件系统、DOM、JSON、AST、组织架构都是树
from dataclasses import dataclass, field

@dataclass
class TreeNode:
    name: str
    children: list["TreeNode"] = field(default_factory=list)
    def add(self, *kids): self.children.extend(kids); return self

root = TreeNode("project").add(
    TreeNode("src").add(TreeNode("main.py"), TreeNode("utils.py")),
    TreeNode("tests").add(TreeNode("test_main.py")),
    TreeNode("README.md"))

def show(node, prefix=""):                   # 前序遍历:先处理自己再处理孩子
    print(prefix + node.name)
    for c in node.children: show(c, prefix + "  ")
show(root)

def height(n): return 1 + max((height(c) for c in n.children), default=0)
def count_leaves(n): return 1 if not n.children else sum(count_leaves(c) for c in n.children)
print("高度:", height(root), "| 叶子数:", count_leaves(root))

def path_to(n, target, path=()):
    path = path + (n.name,)
    if n.name == target: return "/".join(path)
    for c in n.children:
        if (p := path_to(c, target, path)): return p
print("查找路径:", path_to(root, "test_main.py"))

# Python 代码本身就是一棵树(AST)
import ast
tree = ast.parse("y = (a + b) * 2")
print(ast.dump(tree.body[0].value, indent=1)[:200])

# JSON 也是树
import json
doc = json.loads('{"model": {"name": "x", "layers": [{"type": "attn"}, {"type": "mlp"}]}}')
print("JSON 树深处取值:", doc["model"]["layers"][1]["type"])

一稿留存输出:

project
  src
    main.py
    utils.py
  tests
    test_main.py
  README.md
高度: 3 | 叶子数: 4
查找路径: project/tests/test_main.py
BinOp(
 left=BinOp(
  left=Name(id='a'),
  op=Add(),
  right=Name(id='b')),
 op=Mult(),
 right=Constant(value=2))
JSON 树深处取值: mlp

ast.dump 显示 (a + b) * 2 的语法树:乘法是根,左子树是加法——括号决定了树的形状,也决定了计算顺序。ast 模块:https://docs.python.org/3/library/ast.html

常见误区

  • 深度与高度的定义不统一:有的教材从 0 计、有的从 1 计,读题时先确认。
  • 很深的树用递归遍历:可能触发递归上限(见 k2.ds.stack),可改用显式栈。
  • 把有共享子节点的结构当树处理:一个节点有两个父节点就是图(DAG)了(见 k2.ds.graph),遍历时要防重复。

与 AI 开发的关系

  • 决策树与随机森林:sklearn 的树模型(见 k2.ml.sklearn)、XGBoost/LightGBM 的梯度提升树。
  • 代码智能:代码分析、重构工具和部分代码模型基于 AST 或 tree-sitter 语法树。https://tree-sitter.github.io/tree-sitter/
  • 思维树(Tree of Thoughts):把 LLM 推理组织为树状搜索。https://arxiv.org/abs/2305.10601
  • 文档切分:按标题层级(Markdown 树)切分文档用于 RAG。

延伸阅读

理解检查

目录中有指向父目录的链接,能无条件按树递归吗?

参考答案:不能。需要识别链接或维护访问记录,避免重复遍历或循环。

核验与复现

核验日期:2026-10-14。示例状态:运行通过。本轮日志:13_tree.py。

配套代码与核验资料

继续浏览基础 返回知识 →返回顶部 ↑
本篇目录
教程图解100%
教程图解