PYTHON LESSON 083
图书检索二叉排序树
理解二叉排序树“小左大右”的规则，会插入建树，会用查找路径统计比较次数。
00 · 学习目标
这一课要解决什么？
学完后，你应该能够
- class Node: 键 + 左右孩子
- 递归插入：小走左、大走右、空位落户
- while 循环查找：每比较一次就下一层
01 · 核心概念
二叉排序树的插入与查找
二叉排序树的插入与查找：二叉排序树（BST）只有一条规矩：对每个节点来说，左边整棵子树的编号都比它小，右边整棵子树的编号都比它大。规矩立好了，查找就不用翻遍全馆，而是像查字典一样逐层缩小范围。
GESP Python 6 级 · 二叉排序树GESP Python 6 级 · 二叉排序树的插入与查找大量从队首删除时 list.pop(0) 是 O(n)，应使用 collections.deque。
02 · 语法与规则
先记住这 3 条，再开始写程序
class Node: 键 + 左右孩子先准确读出这条写法的结构与作用。
递归插入：小走左、大走右、空位落户换一组最小数据，手工推演一次结果。
while 循环查找：每比较一次就下一层再用边界值或反例确认它的适用条件。
03 · 完整实例
代码、运行结果和解释放在一起看
# 图书检索二叉排序树：插入自动排好序
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
def insert(root, key):
if root is None:
return Node(key)
if key < root.key:
root.left = insert(root.left, key)
else:
root.right = insert(root.right, key)
return root
def inorder(node, bag):
if node is None:
return
inorder(node.left, bag)
bag.append(str(node.key))
inorder(node.right, bag)
def search(root, key):
steps = 0
while root is not None:
steps = steps + 1
if key == root.key:
return steps
if key < root.key:
root = root.left
else:
root = root.right
return -steps # 没找到：返回比较次数的相反数做标记
books = [35, 18, 50, 12, 25, 42, 60]
root = None
for b in books:
root = insert(root, b)
bag = []
inorder(root, bag)
print("入库顺序：" + " ".join(map(str, books)))
print("中序遍历：" + " ".join(bag))
r1 = search(root, 25)
print("查找编号 25：找到了，比较了", r1, "次")
r2 = search(root, 55)
print("查找编号 55：查无此书，比较了", -r2, "次")入库顺序：35 18 50 12 25 42 60 中序遍历：12 18 25 35 42 50 60 查找编号 25：找到了，比较了 3 次 查找编号 55：查无此书，比较了 3 次
中序遍历二叉排序树，得到的正好是从小到大的有序序列。
04 · 逐步理解
每一步只解决一个问题
- 01
排序树的规矩
二叉排序树（BST）只有一条规矩：对每个节点来说，左边整棵子树的编号都比它小，右边整棵子树的编号都比它大。规矩立好了，查找就不用翻遍全馆，而是像查字典一样逐层缩小范围。
- 02
插入：给新编号找空位
从根开始比较：比当前节点小就往左走，否则往右走；走到 None（空位）就把新节点安放在这里。递归函数返回建好的子树根，层层挂回去，是 BST 插入的经典写法。
def insert(root, key): if root is None: return Node(key) if key < root.key: root.left = insert(root.left, key) else: root.right = insert(root.right, key) return root - 03
中序遍历 = 自动排序
对 BST 做中序遍历（左→自己→右），按规矩左边小、右边大，输出的自然就是升序序列。这也是为什么它叫“排序树”——建树的过程顺便完成了排序。
bag = [] inorder(root, bag) print(" ".join(bag)) - 04
查找：每步排除一半
查找不需要递归：用 while 循环，每比较一次就下一层，找到返回比较次数，走到空位说明查无此书。树越平衡，层数越少，比较次数越接近 log₂(n)——十万册书也就十几次。
while root is not None: steps = steps + 1 if key == root.key: return steps - 05
用正负号传两个信息
search 找到时返回正的比较次数，没找到时返回负的。一个返回值同时表达“找到没有”和“比较了几次”，这是竞赛里常用的小技巧；当然也可以返回两个值的元组，更直白。
return -steps - 06
最斜的树
如果按 12、18、25、35、42、50、60 的升序插入，每个新编号都比前面大，全部挂到右边——树退化成一条链，查找又回到“一本本翻”。所以真实系统会用更高级的“平衡树”，但思想都是从 BST 长出来的。
05 · 练习与检验
自己写出来，才算真正学会
- 1运行程序，看中序遍历是否自动排好序
- 2换一批编号重新建树
- 3预测查找 42 要比较几次再核对
- 4想一想：编号按从小到大插入，树会变成什么样
06 · 完整知识
继续理解定义、规则和适用边界
第一次学习先完成上面的六个步骤；需要查定义、核对规则、分析误区或理解“为什么”时，再展开对应知识章。
核心数据结构列表、元组、字典与集合按顺序、可变性、唯一性和查找需求选择容器，并掌握遍历、推导式、排序与复制。＋
正式定义
容器保存多个对象。list 是可变有序序列，tuple 是不可变有序序列，dict 保存唯一键到值的映射，set 保存无序且不重复的可哈希对象。
必须掌握
- list 支持下标、切片、append、extend、insert、pop、remove 与 sort；多数修改方法返回 None。
- tuple 的逗号比括号更关键，单元素元组必须写成 (value,)。
- dict 保持插入顺序；键必须可哈希且唯一，get 可提供缺省值，items 同时遍历键和值。
- set 用于去重与集合运算：| 并、& 交、- 差、^ 对称差；空集合必须写 set()。
- enumerate 同时给出序号和值，zip 并行遍历多个可迭代对象，默认在最短输入处停止。
- 浅复制只复制最外层容器；嵌套可变对象仍可能共享。
CORE CONTAINER METHODS
四类核心容器方法完整速查
修改型方法多数返回 None；表中“浅复制”不会递归复制内部可变对象。
| 类型 | 方法 | 核心作用 |
|---|---|---|
list | append(x) | 末尾加入一个对象 |
list | extend(iterable) | 末尾加入可迭代对象的每一项 |
list | insert(i, x) | 在下标 i 前插入 |
list | remove(x) | 删除第一个等于 x 的元素，不存在时报错 |
list | pop([i]) | 删除并返回指定项，默认末项 |
list | clear() | 删除全部元素 |
list | index(x[, start[, stop]]) | 返回第一个匹配下标 |
list | count(x) | 统计等于 x 的元素数 |
list | sort(*, key=None, reverse=False) | 稳定地原地排序 |
list | reverse() | 原地逆序 |
list | copy() | 浅复制列表 |
tuple | count(x) | 统计元素次数 |
tuple | index(x[, start[, stop]]) | 返回第一个匹配下标 |
dict | clear() | 删除全部键值对 |
dict | copy() | 浅复制字典 |
dict | fromkeys(iterable[, value]) | 用一组键创建新字典 |
dict | get(key[, default]) | 安全取值，缺键返回默认值 |
dict | items() | 键值对动态视图 |
dict | keys() | 键动态视图 |
dict | pop(key[, default]) | 删除键并返回值 |
dict | popitem() | 删除并返回最后加入的键值对 |
dict | setdefault(key[, default]) | 缺键时写入默认值并返回 |
dict | update(other) | 用映射或键值对更新 |
dict | values() | 值动态视图 |
set | add(x) | 加入一个元素 |
set | clear() | 删除全部元素 |
set | copy() | 浅复制集合 |
set | discard(x) | 删除元素，不存在也不报错 |
set | remove(x) | 删除元素，不存在时报错 |
set | pop() | 删除并返回任意元素 |
set | union(*others) | 返回并集 |
set | update(*others) | 用并集原地更新 |
set | intersection(*others) | 返回交集 |
set | intersection_update(*others) | 用交集原地更新 |
set | difference(*others) | 返回差集 |
set | difference_update(*others) | 用差集原地更新 |
set | symmetric_difference(other) | 返回对称差 |
set | symmetric_difference_update(other) | 用对称差原地更新 |
set | issubset(other) | 是否为子集 |
set | issuperset(other) | 是否为超集 |
set | isdisjoint(other) | 是否没有共同元素 |
常见误区
- 把 list.sort() 的返回值赋回列表
- 遍历 dict 时同时改变其大小
- 用可变 list 当字典键
- 把 set 当成有固定顺序的序列
适用边界
- 大量从队首删除时 list.pop(0) 是 O(n)，应使用 collections.deque。
- 需要有序映射的特殊操作、计数或默认值时可查阅 collections，但先理解基本 dict。
程序组织函数、参数、返回值与作用域用明确的输入、输出和职责拆分程序，理解参数绑定、作用域、递归与可变对象。＋
正式定义
函数把一段可复用行为绑定到名字。调用时实参按规则绑定到形参，函数执行后用 return 交回结果；没有显式 return 时返回 None。名字解析遵循局部、闭包、全局、内置的 LEGB 顺序。
必须掌握
- 位置参数先于关键字参数；默认值在 def 执行时创建一次，不应直接使用可变容器作默认值。
- return 立即结束当前函数；return a, b 实际返回一个元组。
- 函数内赋值默认创建局部变量；global 声明模块级名字，nonlocal 声明最近外层函数名字。
- 传参传递的是对象引用；函数是否影响调用方取决于对象是否可变以及函数是否原地修改。
- 递归必须有可到达的终止条件，并要考虑调用深度、重复子问题和栈空间。
- 纯函数更容易测试；把输入输出、计算逻辑和全局状态分开能显著减少错误。
常见误区
- 可变默认参数在多次调用间共享
- 忘记 return 导致得到 None
- 局部变量遮蔽全局同名变量
- 递归没有缩小问题规模
适用边界
- lambda 只能包含一个表达式，适合短小的排序键，不适合塞入复杂业务逻辑。
- 装饰器、生成器和闭包属于函数模型的进阶应用，应在基本参数与作用域稳定后学习。
核心数据结构树、图、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 语法。
- 递归也能表达重复，但有调用开销和递归深度限制，不能无条件代替循环。
完成检查