一句话定义
有根树把节点组织成层级,除根外每个节点只有一个父节点。它适合表示可递归分解的层级数据;一般无向树则是连通且无环的图。
为什么重要
- 层级数据无处不在:文件系统、HTML/DOM、JSON、组织架构、代码的语法树(AST)。
- 许多高效结构都是特化的树:二叉搜索树、堆、Trie、B 树(数据库索引)、决策树(机器学习模型)。
使用边界
深度与高度有按边数、按层数计数的不同约定。本批示例的 height 返回层数,叶子高度为 1;共享子节点、符号链接或回指会让实际结构成为图。
原理 / 图解
| 术语 | 含义 |
|---|---|
| 根(root) | 没有父节点的节点 |
| 叶子(leaf) | 没有子节点的节点 |
| 深度 / 高度 | 深度常按根到节点的边数;本篇 height 示例按子树层数计高度,叶子高度为 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。
延伸阅读
- 维基百科:树(数据结构)https://en.wikipedia.org/wiki/Tree_(abstract_data_type)
- Python
ast模块:https://docs.python.org/3/library/ast.html - 《算法导论》第 10、12 章。
理解检查
目录中有指向父目录的链接,能无条件按树递归吗?
参考答案:不能。需要识别链接或维护访问记录,避免重复遍历或循环。
核验与复现
核验日期:2026-10-14。示例状态:运行通过。本轮日志:13_tree.py。
配套代码与核验资料