专题进阶 · 树与范围查询推荐总顺序 · 第 46 / 148 课

模拟左根右的暂停状态,并解释 BST 中序有序的额外前提。

先学会这些,再进入本课 二叉树 栈
还有 2 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 树与范围查询

中序遍历Inorder

按左、根、右访问;二叉搜索树的中序序列有序。

建议 40 分钟 · 含手算、代码与三层练习

本课要建立的能力

模拟左根右的暂停状态,并解释 BST 中序有序的额外前提。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

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为什么这个方法成立

  1. 内层循环保存所有等待左子树完成的祖先。
  2. 弹出时左子树已完成,访问根后只剩右子树,恰好符合中序定义。
  3. 每个节点恰好压入、弹出一次,既不遗漏也不重复。

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从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

只有左链 3→2→1,中序是什么?

需要一点提示

从最左端开始返回。

查看解析与答案

[1,2,3]。

练习 2 · 边界与辨析

循环条件改为 current is not None 会怎样?

需要一点提示

最左端后 current 为空。

查看解析与答案

会丢掉栈内等待访问的祖先。

练习 3 · 变式与迁移

找 BST 第 k 小可如何改?

需要一点提示

对访问次数计数。

查看解析与答案

每次弹栈访问时递增,计到 k 返回;仍需确认树确实满足 BST,且 k 合法。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Princeton · 查找结构

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。