PYTHON LESSON 081
家族族谱树
理解树的基本概念，会用类构造二叉树，掌握前序、中序、后序、层序四种遍历。
00 · 学习目标
这一课要解决什么？
学完后，你应该能够
- class 类名: 创建自己的数据类型
- self.left / self.right 指向孩子节点
- def 递归函数(node): 空节点就返回
01 · 核心概念
树的构造与四种遍历
树的构造与四种遍历：树是一种“一个连多个”的结构：最顶端是根节点，每个节点可以伸出若干个孩子节点，没有孩子的叫叶子。族谱、文件夹目录、比赛对阵图都是树。二叉树规定每个节点最多两个孩子：左孩子和右孩子。
GESP Python 6 级 · 树的定义与构造GESP Python 6 级 · 树的遍历GESP Python 6 级 · 面向对象思想课程使用普通类解释对象模型；dataclass、property、抽象基类和元类是后续工程工具。
02 · 语法与规则
先记住这 3 条，再开始写程序
class 类名: 创建自己的数据类型先准确读出这条写法的结构与作用。
self.left / self.right 指向孩子节点换一组最小数据，手工推演一次结果。
def 递归函数(node): 空节点就返回再用边界值或反例确认它的适用条件。
03 · 完整实例
代码、运行结果和解释放在一起看
# 家族族谱树：用“类”造一棵树，再做四种遍历
from collections import deque
class TreeNode:
def __init__(self, name):
self.name = name # 节点上存的名字
self.left = None # 左孩子
self.right = None # 右孩子
# 造一棵家族树：
# 爷爷是根；左孩子爸爸、右孩子姑姑；爸爸的孩子是“我”和“妹妹”
grandpa = TreeNode("爷爷")
dad = TreeNode("爸爸")
aunt = TreeNode("姑姑")
me = TreeNode("我")
sis = TreeNode("妹妹")
grandpa.left = dad
grandpa.right = aunt
dad.left = me
dad.right = sis
def preorder(node, bag):
if node is None:
return
bag.append(node.name) # 前序：先记自己
preorder(node.left, bag)
preorder(node.right, bag)
def inorder(node, bag):
if node is None:
return
inorder(node.left, bag)
bag.append(node.name) # 中序：夹在中间
inorder(node.right, bag)
def postorder(node, bag):
if node is None:
return
postorder(node.left, bag)
postorder(node.right, bag)
bag.append(node.name) # 后序：最后记自己
bag = []
preorder(grandpa, bag)
print("前序遍历：" + " ".join(bag))
bag = []
inorder(grandpa, bag)
print("中序遍历：" + " ".join(bag))
bag = []
postorder(grandpa, bag)
print("后序遍历：" + " ".join(bag))
# 层序遍历：排队参观，一层一层来
queue = deque([grandpa])
bag = []
while queue:
node = queue.popleft()
bag.append(node.name)
if node.left is not None:
queue.append(node.left)
if node.right is not None:
queue.append(node.right)
print("层序遍历：" + " ".join(bag))前序遍历：爷爷 爸爸 我 妹妹 姑姑 中序遍历：我 爸爸 妹妹 爷爷 姑姑 后序遍历：我 妹妹 爸爸 姑姑 爷爷 层序遍历：爷爷 爸爸 姑姑 我 妹妹
三种递归遍历的差别只在“记录自己”这一行的位置；层序遍历用队列实现。
04 · 逐步理解
每一步只解决一个问题
- 01
什么是树
树是一种“一个连多个”的结构：最顶端是根节点，每个节点可以伸出若干个孩子节点，没有孩子的叫叶子。族谱、文件夹目录、比赛对阵图都是树。二叉树规定每个节点最多两个孩子：左孩子和右孩子。
- 02
用类造一个节点
class 让我们创造自己的数据类型。TreeNode 的每个对象都有三个属性：name 存数据，left 和 right 指向左右孩子（初始为 None 表示“没有”）。这就是面向对象的入门动作：把“节点”这个概念变成代码里的图纸。
class TreeNode: def __init__(self, name): self.name = name self.left = None self.right = None - 03
把节点连成树
先按图纸造出五个节点对象，再用 grandpa.left = dad 这样的赋值把关系接上。画图对照代码，弄清楚每一行连接的是谁和谁——结构想清楚，代码只是照抄图纸。
grandpa.left = dad grandpa.right = aunt dad.left = me dad.right = sis - 04
递归遍历的秘密
“遍历一棵树”可以拆成“访问自己 + 遍历左子树 + 遍历右子树”三件小事，而遍历子树又是同一个问题——这就是递归。前、中、后序唯一的区别是 bag.append(node.name) 放在三件小事的哪个位置：开头、中间、还是结尾。
def preorder(node, bag): if node is None: return bag.append(node.name) preorder(node.left, bag) preorder(node.right, bag) - 05
递归必须有出口
if node is None: return 是递归的“刹车”：遇到空节点就立刻返回，不再往下钻。没有这行，函数会永远调用自己，直到程序崩溃。写递归先写出口，是不摔跤的第一要诀。
if node is None: return - 06
层序遍历用队列
层序遍历按“辈分”一排排访问，递归不好使，改用队列：根先入队，每次从队首请出一位、记录下名字，再把它的孩子依次排到队尾。先进先出，保证了长辈永远比晚辈先被访问。
queue = deque([grandpa]) while queue: node = queue.popleft() if node.left is not None: queue.append(node.left) - 07
给族谱添丁
试着再造一个 TreeNode("堂哥")，挂到姑姑名下，预测四种遍历的新顺序再运行核对。能把变化说对，说明你已经会用“树的视角”思考了。
05 · 练习与检验
自己写出来，才算真正学会
- 1运行程序，观察四种遍历的顺序差异
- 2给家族树再加一位成员
- 3交换中序遍历里两行代码的位置，看输出怎么变
- 4用层序遍历的思路说出“辈分”是怎么排的
06 · 完整知识
继续理解定义、规则和适用边界
第一次学习先完成上面的六个步骤；需要查定义、核对规则、分析误区或理解“为什么”时，再展开对应知识章。
程序组织类、对象、属性与方法理解对象模型和封装边界，用类表达有状态的实体，而不是把所有程序都强行改成类。＋
正式定义
类描述一类对象的数据与行为；实例是类创建的具体对象。实例方法的第一个参数通常命名为 self，用来访问当前实例；__init__ 在实例创建后负责初始化状态。
必须掌握
- 实例属性通常在 __init__ 中通过 self.name = value 建立。
- 实例方法通过 object.method() 调用；Python 会自动把实例绑定给 self。
- 类属性由实例共享，实例属性属于单个对象；同名实例属性会遮蔽类属性。
- __repr__ 面向开发与调试，__str__ 面向用户显示；特殊方法应遵守其协议。
- 继承表达“是一种”关系，组合表达“拥有一个”关系；能用组合清晰表达时不要滥用继承。
- 对象相等默认仍是身份比较；需要按内容相等时要定义相应协议。
常见误区
- 在方法中漏写 self
- 把每个实例独有的可变数据写成类属性
- 只为包装几个无状态函数而建类
- 继承层次过深导致行为难以追踪
适用边界
- 课程使用普通类解释对象模型；dataclass、property、抽象基类和元类是后续工程工具。
- 算法题常用函数和基本容器更直接，不要求为了“面向对象”而增加结构。
核心数据结构树、图、DFS、BFS 与最短路从节点与边的模型出发，掌握遍历、连通性、树结构、最小生成树和最短路径的适用条件。＋
正式定义
图由顶点和边构成；树是连通且无环的无向图。DFS 沿路径深入后回溯，BFS 按距离层次扩展。算法的正确选择取决于图是否有向、边权是否为负、是否稠密以及目标是遍历、连通还是最短路。
必须掌握
- 邻接矩阵占 O(V²) 空间，适合稠密图和快速查边；邻接表占 O(V+E)，适合稀疏图。
- DFS 常用递归或显式栈，BFS 使用队列；一般图都必须记录 visited 防止重复和死循环。
- 无权图的 BFS 首次到达即得到最少边数距离，可用 parent 还原路径。
- 树有 V-1 条边且任意两点路径唯一；二叉树前/中/后序描述根的访问时机。
- Dijkstra 只适用于非负边权；Floyd 求所有点对最短路并允许负边，但不能有可达负环。
- Kruskal 按边权排序并用并查集避环，得到连通无向带权图的最小生成树。
常见误区
- 遍历一般图时不记录 visited
- 对负权边使用 Dijkstra
- 混淆最短路径树与最小生成树
- 递归 DFS 忽略深度限制
适用边界
- 有向无环图、拓扑排序、强连通分量和负权最短路是图论后续主题。
- 网格搜索也是图搜索：格子是顶点，可移动关系是边；不要只背二维数组模板。
程序组织函数、参数、返回值与作用域用明确的输入、输出和职责拆分程序，理解参数绑定、作用域、递归与可变对象。＋
正式定义
函数把一段可复用行为绑定到名字。调用时实参按规则绑定到形参，函数执行后用 return 交回结果；没有显式 return 时返回 None。名字解析遵循局部、闭包、全局、内置的 LEGB 顺序。
必须掌握
- 位置参数先于关键字参数；默认值在 def 执行时创建一次，不应直接使用可变容器作默认值。
- return 立即结束当前函数；return a, b 实际返回一个元组。
- 函数内赋值默认创建局部变量；global 声明模块级名字，nonlocal 声明最近外层函数名字。
- 传参传递的是对象引用；函数是否影响调用方取决于对象是否可变以及函数是否原地修改。
- 递归必须有可到达的终止条件，并要考虑调用深度、重复子问题和栈空间。
- 纯函数更容易测试；把输入输出、计算逻辑和全局状态分开能显著减少错误。
常见误区
- 可变默认参数在多次调用间共享
- 忘记 return 导致得到 None
- 局部变量遮蔽全局同名变量
- 递归没有缩小问题规模
适用边界
- lambda 只能包含一个表达式，适合短小的排序键，不适合塞入复杂业务逻辑。
- 装饰器、生成器和闭包属于函数模型的进阶应用，应在基本参数与作用域稳定后学习。
Python 基础程序执行、输入输出、变量与数据类型从一条语句怎样执行开始，系统掌握 print、input、变量、对象、类型与显式转换。＋
正式定义
Python 程序由语句和表达式组成，通常按从上到下的顺序执行。变量名通过赋值绑定到对象；对象有类型和值。input() 始终返回 str，是否转换成 int 或 float 必须由题意决定。
必须掌握
- print(*objects, sep=' ', end='\n') 可以控制对象之间的分隔符和末尾字符。
- input(prompt) 读取一行并去掉行末换行符，返回值一定是字符串。
- 赋值符号 = 建立或更新名字与对象的绑定；== 才是相等比较。
- 核心标量类型包括 int、float、bool、str 和 NoneType；bool 是 int 的子类，但语义上应当用于真假判断。
- int、float、str、bool 可做显式类型转换；转换可能失败，不能把任意文本直接当数字。
- 注释以 # 开始；规范的变量名应表达含义，不能使用关键字。
常见误区
- 把 input() 的结果直接与整数相加
- 混淆 = 与 ==
- 用 float 表示必须精确的十进制金额却不考虑误差
- 变量名覆盖 print、list 等内置名称
适用边界
- 课程先讲同步的文本输入输出；文件、网络、图形界面和异步输入分别在对应章节说明。
- Python 的变量没有固定类型，但对象有类型；这不等于程序可以随意混用类型。
完成检查