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

理解先访问根的用途,并推导迭代栈为何先压右孩子。

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

前序遍历Preorder

按根、左、右访问,适合记录进入节点时的状态。

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

本课要建立的能力

理解先访问根的用途,并推导迭代栈为何先压右孩子。

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

01先把问题说具体

输出树 4(2(1,3),7) 的根、左、右遍历顺序,并在迭代代码中保持相同顺序。

02一步步得到方法

前序描述的是访问时机

来到节点先处理根,再递归左子树,最后右子树,所以树根总是首先出现。常用于复制结构、记录进入节点的路径状态;但只记录值通常不足以唯一恢复一棵任意二叉树。

递归调用本身保存尚未执行的右子树。改写为显式栈时,要主动把待办任务压入栈。由于后进先出,应先压右孩子,再压左孩子,这样左边先被弹出。

遍历与序列化有何区别

若要从前序结果恢复一般二叉树,需要保留空孩子标记,例如 [4,2,1,#,#,3,#,#,7,#,#]。没有空标记时,[1,2] 可以表示根 1 的左孩子 2,也可以表示右孩子 2。

访问时机与栈顺序对应

前序在刚进入节点时处理它,再进入左子树、右子树,因此根一定最先出现。它适合先处理父级再展开下级,例如输出目录结构或生成带空标记的树表示。

用显式栈模拟时,后压入的孩子先出栈。要让左孩子先处理,应先压右、再压左。遇到只存在一个孩子的树也应保持同样规则。

03把一个小例子完全算清楚

树 4(2(1,3),7),栈右侧为栈顶。

步骤计算与状态为什么这样做
弹出 4输出 [4],栈 [7,2]右先压,左后压
弹出 2输出 [4,2],栈 [7,3,1]保持根左右
弹出 1、3、7[4,2,1,3,7]叶子不增加任务

窄屏可左右滑动表格,阅读完整计算与理由。

前序结果 [4,2,1,3,7]。

04为什么这个方法成立

  1. 栈顶始终为递归顺序中下一棵待处理子树的根。
  2. 访问根后把右子树任务放在左子树任务下方,保持左先右后的安排。
  3. 每个节点只入栈一次,最终所有节点恰好访问一次。

05把推导翻译成代码

Python · 可独立运行的教学实现

def preorder(tree):
    # tree 用 (value, left, right) 表示,空树为 None
    if tree is None:
        return []
    stack, output = [tree], []
    while stack:
        value, left, right = stack.pop()
        output.append(value)
        if right is not None:
            stack.append(right)
        if left is not None:
            stack.append(left)
    return output

逐个理解关键决定

stack.append(right)
先保存稍后才处理的右子树。
output.append(value)
访问发生在孩子之前,是前序与其他遍历的核心区别。

06时间、空间与实现范围

时间 O(n),栈最多 O(h) 个待处理分支,输出 O(n)。

递归和迭代只是保存待办状态的不同方式,不会自动改变遍历定义。

07改变条件,检查哪里会出错

先压左再压右

会得到根右左顺序;根据栈的后进先出倒推压栈顺序。

仅前序序列就声称能唯一还原任意二叉树

没有额外结构信息时通常不唯一;需空节点标记或在满足条件时结合中序等信息。

08从手算到独立迁移

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

练习 1 · 复现与理解

根 1 只有右孩子 2,前序是什么?

需要一点提示

空左子树不输出。

查看解析与答案

[1,2]。

练习 2 · 边界与辨析

前序值序列能唯一确定树吗?

需要一点提示

考虑只有一个孩子的根。

查看解析与答案

一般不能;加入空节点标记,或结合满足条件的另一种遍历才能恢复。

练习 3 · 变式与迁移

要统计根到叶路径的前缀,何时加入当前值?

需要一点提示

在进入孩子前建立父路径。

查看解析与答案

进入节点时加入,完成子树后撤销;注意为输出路径保存快照。

继续深入这个专题

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

Princeton · 查找结构

理解之后,继续递进

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