数据结构 04｜树与二叉树：遍历怎么手算、两个序列怎么还原一棵树

2011 年第 5 题，我卡了整整十分钟。

题目给的是：某二叉树先序 1,2,3,4、后序 4,3,2,1，问中序序列不可能是哪一个。我的第一反应是"先序后序都有了，树不就确定了吗"，然后开始推唯一的那棵树——推了半天推不出来，因为压根就不唯一。

关键在于这两个序列互为逆序。互为逆序意味着：树里任何一个结点，都不可能同时有左右两个孩子（否则先序里"根"在中间某处，后序里同一个根也会在中间，不可能刚好倒过来）。所以这棵树必然是一条高为 4 的链——每个结点最多一个孩子。

有了这个前提，四个选项一验就出来了：C 选项 3,2,4,1 要求结点 2 同时有左右孩子，直接矛盾。

先序 + 后序不能唯一确定一棵二叉树——这条我背过，但直到这道题才知道它长什么样。

〇、先花两分钟：树、二叉树、遍历是什么

树：一堆结点，除了最上面那个（根），每个结点都有且只有一个"上级"，并且不能成环。像家谱。

二叉树：每个结点最多两个孩子，而且分左右——"一个左孩子"和"一个右孩子"是两棵不同的树。

遍历：按某种顺序把所有结点不重不漏地各访问一次。二叉树的遍历有四种：

"根左右"这三个字里的"左""右"指的是整棵左子树、整棵右子树，而且每个子树内部递归地按同样规则走。

四种遍历对照、两序列还原三步法、完全二叉树与森林转换公式

一、四种遍历怎么手算（一棵树跑四遍）

拿这棵树当例子，四种遍历一起算：

      a
      / \\
    b   c
    / \\   \\
  d   e   f
      /
    g

先序（根左右）：先访问 a；再走左子树 b——访问 b，走 b 的左 d（访问 d），走 b 的右 e（访问 e，再走 e 的左 g）；最后走右子树 c——访问 c，走 c 的右 f。

a b d e g c f

中序（左根右）：先走 a 的左子树——b 的左 d（访问 d），访问 b，再走 b 的右 e（e 的左 g → 访问 g，访问 e）；访问 a；走右子树 c——c 无左，访问 c，走 c 的右 f。

d b g e a c f

后序（左右根）：d；（g, e）；b；f；c；a

d g e b f c a

层次：一层一层，从左到右

a b c d e f g

手算技巧：不要试图一次写完整个序列。对每个结点，只在心里记住"我现在在走它的哪一部分"，递归往下。练三棵树就熟了。

二、三条性质（选择题直接套）

① 先序序列 == 中序序列？ 那所有非叶结点只有右子树。

道理：先序是"根左右"，中序是"左根右"。要让两者相同，每个结点的"左"必须为空 → 只有右子树。（真题 408 真题 2017 年第 4 题，答案 B）

反过来：中序 == 后序 → 所有非叶结点只有左子树。

② 中序序列里，相邻的两个结点 p、q（p 在前）：

• q 是 p 的双亲 —— 可能

• q 是 p 的右孩子 —— 可能

• q 是 p 的双亲的双亲 —— 可能

• q 是 p 的右兄弟 —— 不可能

最后一条为什么不可能？因为中序是"左根右"，p 和它的右兄弟 q 之间一定夹着它们的父结点。（真题 408 真题 2022 年第 3 题，答案 B 仅 III）

③ 中序序列里，若 v 有两个孩子，则它前一个结点 p 一定没有右孩子，后一个结点 q 一定没有左孩子。

理由：p 若有右孩子，p 和 v 之间还会插入别的结点，就不相邻了。q 同理。（真题 408 真题 2024 年第 3 题，答案 A）

三、由两个序列还原二叉树（三步法）

这是本节最值钱的部分。规则一句话：

先序（或后序）用来找根，中序用来切左右。

三步法（以先序 + 中序为例）：

真题 408 真题 2021 年第 4 题（先序 + 中序 → 森林有几棵树）：

森林 F 对应的二叉树 T，T 的先序 a,b,d,c,e,g,f，中序 b,d,a,e,g,c,f，F 中树的棵数是？

第一步：先序首字符 a 是 T 的根。 第二步：中序里 a 的左边是 b,d（a 的左子树），右边是 e,g,c,f（a 的右子树）。

• 左子树：中序 b,d，先序对应 b,d → b 为根，d 是 b 的右孩子（中序里 d 在 b 右边）

• 右子树：中序 e,g,c,f，先序对应 c,e,g,f → c 为根；中序里 c 左边 e,g、右边 f

  • c 的左子树：中序 e,g，先序 e,g → e 为根，g 是 e 的右孩子

  • c 的右子树：f

还原出来的 T：

      a
      / \\
    b   c
      \\ /\\
      d e f
        \\
          g

森林的棵数 = 二叉树根结点右链上的结点个数：从 a 往右走 → a → c → f，共 3 个。

答案 C：3。

真题 408 真题 2020 年第 4 题（森林的遍历 → 二叉树的遍历）：

森林 F 先根 a,b,c,d,e,f，中根 b,a,d,f,e,c，则对应二叉树 T 的后根序列是？

关键换算（背下来）：

所以 T 的先序 = a,b,c,d,e,f，中序 = b,a,d,f,e,c。按三步法还原：

• 根 a；中序里 a 左 b、右 d,f,e,c

• 右子树：先序 c,d,e,f，中序 d,f,e,c → c 为根，中序里 c 左边 d,f,e、右边空

  • c 的左子树：先序 d,e,f，中序 d,f,e → d 为根，中序里 d 左边空、右边 f,e

    • d 的右子树：先序 e,f，中序 f,e → e 为根，f 是 e 的左孩子

后序遍历这棵树：b, f, e, d, c, a

答案 C。

四、为什么先序 + 后序不能唯一确定（重点）

先序是"根左右"，后序是"左右根"。两个序列里根都在两端——先序首个、后序末个。但光靠两端，分不出左右子树的分界在哪，这就是不能唯一确定的原因。

真题 408 真题 2012 年第 3 题：

先序 a,e,b,d,c，后序 b,c,d,e,a，根结点的孩子结点是？

• 先序首 = 后序末 = a，a 是根

• 剩下：先序 e,b,d,c，后序 b,c,d,e

判断"e 是不是 a 唯一的孩子"：看剩下这段的先序首（e）和后序末（e）——同一个 e 分别占据两端，说明 e 是这棵子树的根，而 b,d,c 全在它的子树里。所以 a 的孩子只有 e。

答案 A：只有 e。

一条很好用的推论：在两个序列里，若片段 XY… 在先序中 X 在 Y 前，而在后序中 Y 在 X 前（即 …YX），则 X 是 Y 的祖先。

回到开头那道 2011(5)：先序 1,2,3,4 与后序 4,3,2,1 完全互逆 → 任何结点都不可能同时有左右孩子 → 树是单链。选项 C 3,2,4,1 要求 2 同时有左孩子 3 和右孩子 4，矛盾。

答案 C。

五、完全二叉树的两类计算

完全二叉树：按层次编号，从上到下、从左到右，编号是连续的 1~n，中间不跳号。

性质 1：编号为 i 的结点，左孩子 2i、右孩子 2i+1、父结点 ⌊i/2⌋。 性质 2：最后一个分支结点是 ⌊n/2⌋，它之后全是叶子。

真题 408 真题 2011 年第 4 题：

完全二叉树有 768 个结点，叶结点个数是？

最后分支结点 = ⌊768/2⌋ = 384，所以叶子 = 768 − 384 = 384。

答案 C。

真题 408 真题 2009 年第 5 题（反着考）：

完全二叉树第 6 层（根为第 1 层）有 8 个叶结点，结点个数最多是？

要让总数最多，树要尽可能高。第 6 层有叶子说明树高可能是 6 或 7，取 7 更高更多。

• 前 6 层是满的：2⁶ − 1 = 63 个

• 第 6 层共有 2⁵ = 32 个结点，其中 8 个是叶子 → 剩下 24 个各带 2 个孩子 → 第 7 层有 48 个

总数 = 63 + 48 = 111

答案 C。

（另一种算法：高 7 的满二叉树有 127 个，第 6 层的 8 个叶子各少了 2 个孩子 → 127 − 16 = 111）

⚠️ 一个高频陷阱：完全二叉树可以有度为 1 的结点（比如只有 2 个结点时，根度为 1）。2025(4) 的 A 选项就是拿这个挖坑。

六、树的度与结点数（一个公式打天下）

核心公式（任何树都成立）：

结点总数 N = 1 + Σ (i × nᵢ)       nᵢ 表示度为 i 的结点个数

因为总度数 = N − 1（除根以外，每个结点都有一条边连着父结点）。

真题 408 真题 2010 年第 5 题：

度为 4 的树，有 20 个度为 4 的结点、10 个度为 3 的、1 个度为 2 的、10 个度为 1 的，叶结点（度 0）有几个？

总度数 = 4×20 + 3×10 + 2×1 + 1×10 = 80 + 30 + 2 + 10 = 122
N = 122 + 1 = 123
叶结点 n₀ = 123 − (20 + 10 + 1 + 10) = 123 − 41 = 82

答案 B：82。

真题 408 真题 2022 年第 4 题（推广到三叉树）：

三叉树有 244 个结点，高度至少是多少？

高度为 h 的三叉树，结点数最多是 (3ʰ − 1)/2：

h = 5 → (243 − 1)/2 = 121 < 244
h = 6 → (729 − 1)/2 = 364 ≥ 244

答案 C：6。

二叉树版本（最常用）：高度为 h 的二叉树最多 2ʰ − 1 个结点。

七、森林与二叉树的转换：左孩子右兄弟

转换规则（就一句话）：第一个孩子当左孩子，兄弟当右孩子。

三条推论（都是真题）：

① 森林的叶子数 = 二叉树中"左孩子指针为空"的结点数

叶子没有孩子，转成二叉树后就没有左孩子。（真题 408 真题 2014 年第 5 题，答案 C）

② 树的分支结点数 + 1 = 对应二叉树中"无右孩子"的结点数

每个分支结点的最右那个孩子没有右兄弟（无右孩子），另外根结点转换后也没有右孩子。

真题 408 真题 2011 年第 6 题：

2011 个结点的树，116 个叶结点，对应二叉树中无右孩子的结点数是？

分支结点 = 2011 − 116 = 1895，加根结点 → 1896。

答案 D。

③ 森林中树的棵数 = 二叉树根结点右链上的结点个数（见第三节 2021(4)）

真题 408 真题 2009 年第 6 题（反向推导）：

二叉树中 u 是 v 的父结点的父结点，则原森林中 u 和 v 的关系可能是？ I. 父子 II. 兄弟 III. u 的父与 v 的父是兄弟

• I 可能：v 是 u 的第二个孩子 → 转换后 v 成了 u 第一个孩子的右孩子，正好是"父的父"

• II 可能：u、v 是兄弟且中间还有个兄弟 k → 转换后 v 是 k 的右孩子、k 是 u 的右孩子

• III 不可能：那样 u 和 v 会落在两棵不同子树里，不可能在同一条路径上

答案 B：I 和 II。

八、线索二叉树：线索指向谁

线索：把结点里空的指针域利用起来，指向它在某种遍历序列里的前驱或后继。左空指针指向前驱（左线索），右空指针指向后继（右线索）。

做题方法（万能）：先写出遍历序列，再看这个结点在序列里的前一个是谁、后一个是谁。

真题 408 真题 2014 年第 4 题：

某二叉树中序线索化，结点 x 的左、右线索分别指向？

先写出中序序列（题目解析给出）：d e b x a c。x 的前一个是 b，后一个是 a。

答案 D：b、a。

真题 408 真题 2013 年第 5 题（纯概念，不用图）：

X 是后序线索二叉树中的叶结点，且 X 有左兄弟 Y，则 X 的右线索指向？

X 是叶子且有左兄弟 → X 是右孩子。后序遍历是"左右根"，X 作为叶子先被访问，接着访问的是它的父结点（因为 X 没有右子树，X 这一小支就走完了）。

所以 X 的后序后继 = 父结点。

答案 A。

九、二叉树的顺序存储

规则：按完全二叉树的编号方式存进数组——编号 i 的结点放在下标 i（或 i−1，看题目从 0 还是 1 开始），不存在的结点也要占位置。

真题 408 真题 2020 年第 3 题：

任意一棵高度为 5、有 10 个结点的二叉树，顺序存储至少要多少存储单元？

因为要"任意"——最坏情况下编号要撑满 5 层，所以按高 5 的满二叉树算：

1 + 2 + 4 + 8 + 16 = 31

答案 A：31。

⚠️ 注意这里问的是"至少需要多少才能保证任意情况都能存"，不是"这棵树实际占多少"。

真题 408 真题 2025 年第 3 题（反向：给数组，判断能不能表示二叉树）：

用 −1 表示结点不存在，哪个数组不能表示一棵二叉树？

规则很简单：除了根以外，任何非 −1 的结点，它的父结点必须存在（不能是 −1）。父结点下标 = ⌊(i−1)/2⌋（数组从 0 开始时）。

选项 D：R[] = {17, 20, 35, -1, 18, 45, -1, -1, 19, 27}

下标 8 的值是 19（存在），它的父结点下标 = ⌊(8−1)/2⌋ = 3，而 R[3] = −1（父结点不存在）→ 违反规则。

答案 D。

十、25 道题考在哪（树与二叉树遍历类）

本文引用的题库中，标签属于二叉树遍历 / 树的概念 / 完全二叉树 / 森林转换 / 线索二叉树 / 二叉树存储的单选共 25 道：

命题规律，四条：

口径说明：依据 zhenti_all.json 中 subject=数据结构 的 187 道单选，按标签筛出 25 道。其中 2010(3)、2017(5)、2023(5) 三道题的树形图在题库中为 OCR 乱码或缺失，本文只在考频表列出年份与答案，正文不作图形推演（沿用此前"图缺失不还原原图"的处理口径）。考频仅供参考，★ 少不等于不考。

十一、易错点清单

速查表（文末收藏版）

四种遍历

还原三步法

① 先序首个（或后序末个）= 根
② 在【中序】里找到根，左边=左子树，右边=右子树
③ 数出左右子树结点数 → 回先序切两段 → 递归

能否唯一确定

完全二叉树

结点 i 的左孩子 2i、右孩子 2i+1、父结点 ⌊i/2⌋
最后一个分支结点 = ⌊n/2⌋
叶子数 = n − ⌊n/2⌋
高度 h 最多 2^h − 1 个结点

度与结点数

总度数 = N − 1
N = 1 + Σ(i × nᵢ)
高度 h 的 m 叉树最多 (m^h − 1)/(m − 1) 个结点

森林 ↔ 二叉树（左孩子右兄弟）

线索二叉树

左空指针 → 前驱（遍历序列的前一个）
右空指针 → 后继（遍历序列的后一个）
做法：先写出遍历序列，再看前后是谁

做题三问

本文依据

• 真题数据：zhenti_all.json（2009—2025 年 799 题），本文引用的 25 道单选均与库中题干、选项、答案逐条核对；第三节两道还原题、第五节两道完全二叉树计算、第六节度与结点数均经本文自行演算验证

• 考点范围：408 考试大纲「数据结构 · 四、树与二叉树」（遍历、线索二叉树、完全二叉树、森林与二叉树转换、顺序与链式存储）

• 说明：2010(3)、2017(5)、2023(5) 三道题的树形图在题库中缺失或 OCR 乱码，仅在考频表列出年份与答案，正文不作图形推演；B 树、哈夫曼树、二叉排序树、平衡二叉树不在本篇范围（另有专篇）

• 考频统计：按题库标签筛出，口径见第十节说明，仅供参考