PYTHON LESSON 082
完全二叉树的门牌号
掌握完全二叉树的数组表示法，熟练运用“父 k//2、左 2k、右 2k+1”的编号规律。
00 · 学习目标
这一课要解决什么？
学完后，你应该能够
- tree[k] 用下标当节点编号
- k // 2 找爸爸，2 * k 找左孩子
- while k >= 1: 一路爬回树根
01 · 核心概念
完全二叉树与数组表示
完全二叉树与数组表示：把一棵二叉树按层序一排排坐满，最后一排可以不满但必须靠左坐——这就是完全二叉树。因为它的形状规规矩矩，所以可以用一套“门牌号”规律直接编号：根是 1 号，接下来每层从左到右依次编号。
GESP Python 6 级 · 完全二叉树GESP Python 6 级 · 树的数组表示课程使用普通类解释对象模型；dataclass、property、抽象基类和元类是后续工程工具。
02 · 语法与规则
先记住这 3 条，再开始写程序
tree[k] 用下标当节点编号先准确读出这条写法的结构与作用。
k // 2 找爸爸，2 * k 找左孩子换一组最小数据，手工推演一次结果。
while k >= 1: 一路爬回树根再用边界值或反例确认它的适用条件。
03 · 完整实例
代码、运行结果和解释放在一起看
# 完全二叉树的门牌号：数组下标就是编号
tree = ["", "太阳", "月亮", "星星", "白云", "彩虹", "雨滴", "雪花"] # 0 号位空着不用
print("整棵树按层序住进数组：")
print(tree[1:])
print()
k = 6
print(k, "号住户是", tree[k])
print("它的爸爸住", k // 2, "号，是", tree[k // 2])
left = k * 2
right = k * 2 + 1
if left < len(tree):
print("它的左孩子住", left, "号，是", tree[left])
else:
print("它没有左孩子（叶子住户）")
if right < len(tree):
print("它的右孩子住", right, "号，是", tree[right])
# 从 6 号一路回根部 1 号的路线
route = []
while k >= 1:
route.append(str(k))
k = k // 2
route.reverse()
print("从根部到 6 号的路线：" + " ".join(route))整棵树按层序住进数组： ['太阳', '月亮', '星星', '白云', '彩虹', '雨滴', '雪花'] 6 号住户是 雨滴 它的爸爸住 3 号，是 星星 它没有左孩子（叶子住户） 从根部到 6 号的路线：1 3 6
0 号位置故意空着，让数组下标和节点编号完全对齐，规律才成立。
04 · 逐步理解
每一步只解决一个问题
- 01
什么是完全二叉树
把一棵二叉树按层序一排排坐满，最后一排可以不满但必须靠左坐——这就是完全二叉树。因为它的形状规规矩矩，所以可以用一套“门牌号”规律直接编号：根是 1 号，接下来每层从左到右依次编号。
- 02
门牌号三条铁律
编号为 k 的节点：爸爸住 k // 2 号（整除），左孩子住 2 * k 号，右孩子住 2 * k + 1 号。这套规律让我们不用任何 left/right 指针，一个数组就能装下整棵树。
dad = k // 2 left = k * 2 right = k * 2 + 1 - 03
数组下标对齐编号
让数组的 0 号位置空着，从 1 号开始住人，下标就直接等于门牌号：tree[6] 就是 6 号住户。层序遍历完全二叉树，正好等于从头到尾扫一遍数组。
tree = ["", "太阳", "月亮", "星星", "白云", "彩虹", "雨滴", "雪花"] - 04
先查边界再访问
6 号的双倍是 12 号，可数组一共才 8 个格子——访问前必须判断 2 * k < len(tree)，否则程序会因下标越界而崩溃。用数组表示树时，“孩子存在吗”是第一安全检查。
if left < len(tree): print(tree[left]) else: print("没有左孩子") - 05
一路爬回树根
从任意编号 k 出发，反复执行 k = k // 2，必定在有限步内回到 1 号。把沿途编号存进列表再 reverse，就得到从根到该节点的完整路线。这也是判断两个节点“谁是谁祖先”的基本功。
while k >= 1: route.append(str(k)) k = k // 2 - 06
手算挑战
不看程序回答：10 号住户的爸爸是谁？从根到 13 号经过哪些编号？13 号有孩子吗（数组有 20 个格子时）？三题都答对，数组表示法就算过关了。
05 · 练习与检验
自己写出来，才算真正学会
- 1运行程序，核对 6 号住户的家人信息
- 2把 k 改成 7，预测它的爸爸和路线
- 3算出 12 号住户的左右孩子编号
- 4不用程序，手算从 1 号到 13 号的路线再核对
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 忽略深度限制
适用边界
- 有向无环图、拓扑排序、强连通分量和负权最短路是图论后续主题。
- 网格搜索也是图搜索：格子是顶点，可移动关系是边；不要只背二维数组模板。
Python 基础条件、循环与程序流程准确理解 if、for、while、range、break、continue 和循环嵌套，而不是背代码模板。＋
正式定义
控制流决定下一条要执行的语句。分支依据布尔条件选择路径；循环在满足规则时重复执行代码块。Python 用冒号和缩进界定代码块。
必须掌握
- if/elif/else 从上到下判断，只执行第一个为真的分支；else 不写条件。
- for 依次取得可迭代对象中的元素；range(start, stop, step) 包含 start、不包含 stop，step 不能为 0。
- while 在每轮开始前检查条件；循环体必须让状态向终止条件推进。
- break 结束最内层循环，continue 跳过本轮剩余语句，循环的 else 仅在没有被 break 终止时执行。
- 嵌套循环的总执行次数通常需要把各层次数相乘；内层 break 不会结束外层循环。
- 边界测试至少覆盖空范围、单个元素、第一项命中、最后一项命中和始终不命中。
常见误区
- range 的右端点多算或少算一次
- while 忘记更新状态造成死循环
- 把两个互斥条件写成两个独立 if
- 误以为 break 会跳出所有嵌套循环
适用边界
- 流程图是算法的表示方法，不是 Python 语法。
- 递归也能表达重复，但有调用开销和递归深度限制，不能无条件代替循环。
Python 基础运算符、表达式与优先级完整区分算术、比较、逻辑、成员、身份和位运算，并用优先级表消除歧义。＋
正式定义
表达式求值得到一个值。运算符规定如何组合操作数；当一个表达式含多个运算符时，优先级和结合方向决定求值顺序，括号可以明确改变顺序。
必须掌握
- / 总是得到浮点结果；// 是向负无穷方向取整的整除；% 与 // 满足 a == (a // b) * b + a % b。
- 比较可以链式书写，如 0 <= x < 10；and/or 会短路并返回最后求值的操作数，不一定返回 bool。
- == 比较值是否相等，is 比较是否为同一个对象；判断 None 应写 is None。
- in/not in 做成员测试；对 dict 测试的是键。
- 位运算作用于整数的二进制位；负整数按无限长二进制补码语义理解。
- 复杂表达式即使能靠优先级正确运行，也应使用括号表达意图。
常见误区
- 把 // 当成简单截断
- 用 is 比较数字或字符串的值
- 忘记 and 的优先级高于 or
- 连续位移、比较和逻辑运算却不加括号
适用边界
- 浮点数比较受二进制表示误差影响，需要按问题选择容差。
- 运算符可由自定义类重载，因此相同符号对不同类型可能有不同语义。
完成检查