考研笔记

数据结构第 5 章：树与二叉树总览

本章是 第 7 章树形查找 的地基。 二叉排序树、平衡二叉树、红黑树、B 树的所有性质， 都建立在这一章的「」「完全二叉树编号」「遍历序列」之上。

页面导航

节页一句话
5.1.1~5.1.3树的定义、术语与性质术语无须硬背，三式联立必须会
5.2.1+5.2.2二叉树的概念、性质与存储 与八条编号性质
5.3.1二叉树的遍历三种含中序的组合才能还原
5.3.2线索二叉树 个空链域的废物利用
5.4.1~5.4.3树、森林与二叉树的转换左孩子右兄弟
5.5.1+5.5.2哈夫曼树与并查集WPL 手算 + 并查集的负数
—📖 第 5 章名词库33 条名词 + 35 行范围限定清单

全章的两条线

① 一切都从 长出来

flowchart TD
    P["5.2.1   n₀ = n₂ + 1"]
    P --> A["完全二叉树：<br/>n 奇 ⇒ n₁=0，n 偶 ⇒ n₁=1<br/>直接由 n 求 n₀"]
    P --> B["5.2.2 二叉链表<br/>空链域 = 2n₀+n₁ = n+1"]
    B --> C["5.3.2 线索二叉树<br/>把 n+1 个空链域改成线索"]
    P --> D["5.5.1 哈夫曼树是正则二叉树<br/>n₂ = n−1 ⇒ 总结点 2n−1"]

    classDef root fill:#ffcdd2,stroke:#b71c1c,stroke-width:3px
    classDef norm fill:#e3f2fd,stroke:#1565c0
    classDef leaf fill:#c8e6c9,stroke:#1b5e20
    class P root
    class A,B,D norm
    class C leaf

教材对 加了注意框：「希望读者牢记并灵活应用。」 这是全书少数直接说「牢记」的地方，原因就在上图——它是三条独立结论的共同源头。

② 树 / 森林的一切定义都借二叉树来给

树和森林本身没有「中序」的说法（子树可能有很多棵，根该插在哪？）。教材的解法是先用「左孩子右兄弟」把它们变成二叉树，再借二叉树的遍历来定义。

树 / 森林对应二叉树
树的先根遍历先序
树的后根遍历中序
森林的先序遍历先序
森林的中序遍历中序

「后根 ↔ 中序」是最反直觉也最常考的一条。 原因：转换后「树的根」位于左子树的上方、右兄弟的左边——走完子树再访问根，在二叉树上正是中序的位置。

公式速查

对象公式
一般树度数；边数
度为 的树第 层至多 ；最小高度 ；最大高度
叉树高度 至多 个结点
二叉树；第 层至多 ；高度 至多
完全二叉树高度 ；双亲 、孩子 /、层次
二叉链表空链域
哈夫曼树非叶结点权值；结点总数 ；
并查集Find 、Union ；按大小合并后深度

高频边界

第一组 · 两个「像但不是」

  • 「度为 的树」≠「 叉树」——前者至少有一个结点有 个孩子，后者只要求至多。
  • 二叉树 ≠ 度为 2 的有序树——二叉树可空，且左右次序是绝对的。

第二组 · 数什么

  • 树的路径长度数边；第 7 章的查找长度数结点。两章方向相反。
  • WPL 只累加叶结点， 是路径长度不是层数。
  • 二叉链表空链域是 不是 。

第三组 · 完全二叉树的连锁推理

  • 叶结点只可能在最后两层。
  • 度为 1 的结点最多一个，且只有左孩子。
  • 奇 ， 偶 ；配合 直接出 。

第四组 · 遍历

  • 不含中序的两两组合都不能唯一确定二叉树。
  • 层次遍历用队列，其余三种用栈。
  • 树没有后序遍历；树的后根 ↔ 二叉树的中序。

第五组 · 教材实现细节（算竞背景最容易踩）

  • 并查集的根存负数，绝对值是成员数量（不是自环、不是深度、不是秩）。
  • ltag/rtag 的 0 是孩子、1 是线索。
  • CreateInThread 末尾要单独处理最后一个结点。
  • Firstnode 返回的最左下结点不一定是叶结点。

复习顺序

  1. 5.2 — 先学这一节， 和八条编号性质是全章地基。
  2. 5.1 — 术语快扫，重点做 5.1.3 的三式联立题。
  3. 5.3.1 — 遍历，重点是「哪些组合能还原」。
  4. 5.4 — 左孩子右兄弟 + 四条遍历对应，画三遍转换。
  5. 5.5.1 — 哈夫曼，手算两遍 WPL 和编码。
  6. 5.3.2 — 线索二叉树。细节最密，放在熟悉遍历之后学。
  7. 5.5.2 — 并查集，重点是教材实现与算竞写法的差异。
  8. 名词库 — 考前扫 35 行范围限定清单。

只有 3 小时的话：5.2 的性质 → 5.3.1 的序列还原 → 5.4.3 的四条对应 → 5.5.1 的 WPL → 名词库清单。

链接

反向链接