01先把问题说具体
同一棵树 4(2(1,3),7),为什么先走到底再访问根,会得到 [1,2,3,4,7]?
02一步步得到方法
访问根之前还有一项未完成工作
中序为左子树、根、右子树。第一次来到根时不能立刻输出,要先处理完整左子树;因此把根压栈表示稍后回来。沿左链走到空节点后,弹出最近祖先并访问,再转入其右子树。
每个栈元素是一个暂停点,不只是尚未见过的节点。弹出节点时它的左子树已经处理完成,但右子树还没有。这个状态区分是迭代中序最重要的理解。
为什么有时有序、有时没有
二叉搜索树保证左子树所有键小于根、右子树所有键大于根。结合左右子树自身的中序有序,可推出全树中序有序。普通二叉树没有这些大小关系,中序只是一种访问顺序。
有序输出依赖搜索树条件
中序先处理左子树,再处理根,最后右子树。若左子树所有键小于根、右子树所有键大于根,就能归纳得到升序;普通二叉树没有这条大小关系。
迭代实现先沿左链入栈,直到没有左孩子,弹出最近未处理节点后转向其右子树。栈保存的是已经见到、但还在等待左侧处理完成的祖先。
03把一个小例子完全算清楚
树 4(2(1,3),7)。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| 沿左链入栈 | [4,2,1] | 暂不访问 |
| 弹 1,再弹 2 | 输出 [1,2] | 1 无右子树,返回到 2 |
| 转入 2 的右子树 3 | 输出 [1,2,3] | 完成整个左子树 |
| 回 4,再处理 7 | 输出 [1,2,3,4,7] | 根在左右之间 |
窄屏可左右滑动表格,阅读完整计算与理由。
排序性质来自 BST 约束,而不是中序算法自动排序。
04为什么这个方法成立
- 内层循环保存所有等待左子树完成的祖先。
- 弹出时左子树已完成,访问根后只剩右子树,恰好符合中序定义。
- 每个节点恰好压入、弹出一次,既不遗漏也不重复。
05把推导翻译成代码
Python · 可独立运行的教学实现
def inorder(tree):
output, stack = [], []
current = tree
while current is not None or stack:
while current is not None:
stack.append(current)
current = current[1]
value, left, right = stack.pop()
output.append(value)
current = right
return output逐个理解关键决定
current is not None or stack- 当前路径结束但栈里仍有祖先时必须继续。
current = right- 访问根之后转向右子树,不应再次回左孩子。
06时间、空间与实现范围
时间 O(n),栈 O(h),输出 O(n)。
在 BST 上可把输出改为生成器,按需产生有序键,不必一次性保存全部结果。
07改变条件,检查哪里会出错
任意树中序都排序
例如根 1、左孩子 9,中序 [9,1] 并不升序。
看到中序就宣称结果有序
只有满足二叉搜索树的键值约束及相应重复键规则时才有此保证。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
只有左链 3→2→1,中序是什么?
需要一点提示
从最左端开始返回。
查看解析与答案
[1,2,3]。
循环条件改为 current is not None 会怎样?
需要一点提示
最左端后 current 为空。
查看解析与答案
会丢掉栈内等待访问的祖先。
找 BST 第 k 小可如何改?
需要一点提示
对访问次数计数。
查看解析与答案
每次弹栈访问时递增,计到 k 返回;仍需确认树确实满足 BST,且 k 合法。