数据结构第 5 章：树与二叉树——性质、遍历与哈夫曼树

写于 2026-11-01

树是本课程里第一个非线性结构。前面四章的线性表、栈、队列、串、数组，元素之间都是一对一；树是一对多，所以"遍历"这件事第一次变得有内容——同一个结构有四种走法，走法不同结果不同。这一章的重点是：五条性质要能推、四种遍历要能写、由遍历序列还原树要会、哈夫曼树要会构造。

一、基本术语（先把话说准）

结点的度是它拥有的子树个数；叶子是度为 0 的结点；层次从根算第 1 层；深度（高度）是最大层次；森林是 m 棵互不相交的树的集合。

树的性质里最常用的一条：总结点数 = 总分支数 + 1（除根外每个结点都对应一条入边）。

二、二叉树的五条性质（必背，且要会推）

第 i 层上最多有 2^(i−1) 个结点
深度为 h 的二叉树最多有 2^h − 1 个结点（满二叉树）
对任何二叉树，n₀ = n₂ + 1（叶子数 = 度为 2 的结点数 + 1）
具有 n 个结点的完全二叉树深度为 ⌊log₂n⌋ + 1
完全二叉树按层序从 1 编号，则结点 i 的左孩子是 2i、右孩子是 2i+1、双亲是 ⌊i/2⌋

第 3 条的推导要会：设总结点 n = n₀+n₁+n₂，总分支数 = n−1 = n₁ + 2n₂，两式相减得 n₀ = n₂ + 1。这条性质在选择题里几乎每年出现。

满二叉树 vs 完全二叉树的区别要说清：满二叉树每层都满；完全二叉树只允许最下面一层右侧连续缺失，即按层序编号与满二叉树一一对应。性质 5 只对完全二叉树成立。

三、存储结构

顺序存储：按完全二叉树的编号把结点放进数组。对完全二叉树非常紧凑；但对一般二叉树会浪费大量空间（最坏退化成单支树时，n 个结点要 2ⁿ 大小的数组）。

二叉链表：每个结点 lchild | data | rchild，n 个结点有 n+1 个空指针域。这个数字是后面线索化的依据——空指针不该浪费，可以用来存遍历时的前驱后继。

三叉链表再加一个 parent 指针，方便找双亲。

四、四种遍历：写不出递归就别谈这一章

先序：根 → 左 → 右
中序：左 → 根 → 右
后序：左 → 右 → 根
层序：按层从左到右，用队列实现

前三种递归写法都是三行，差别只在访问根的位置。非递归写法：前序/中序用栈，后序最麻烦（需要记录上一个访问的结点）；层序用队列——这正是第 3 章"用栈还是用队列决定遍历差异"的具体体现。

复杂度都是 O(n)（每个结点访问一次），递归栈空间平均 O(log n)、最坏 O(n)（单支树）。

五、由遍历序列构造二叉树

这是必考题型，规则只有两条：

先序 + 中序 可以唯一确定一棵二叉树（先序的第一个是根，在中序里定位根，左边是左子树、右边是右子树，递归）
后序 + 中序 也可以唯一确定（后序的最后一个才是根）
先序 + 后序不能唯一确定（分不清单孩子的左右），只能确定根和子树集合。先序 + 层序也不行

解题步骤固定：找根 → 在中序里切左右 → 数左子树结点个数 → 回到先序/后序里切出对应的段 → 递归。

六、线索二叉树

利用那 n+1 个空指针：结点没有左孩子时，lchild 指向遍历序列中的前驱；没有右孩子时，rchild 指向后继。为了区分"指针指向孩子"还是"指向线索"，增加 ltag / rtag 两个标志位（0 表示孩子，1 表示线索）。

价值：中序线索化之后，找中序前驱/后继都是 O(1)，不需要栈也不需要递归，适合需要频繁按序遍历的场景。

七、哈夫曼树与哈夫曼编码

带权路径长度 WPL = Σ(叶子权值 × 叶子的路径长度)。哈夫曼树是WPL 最小的二叉树，也叫最优二叉树。

构造方法（贪心）：每次取权值最小的两棵树合并成新结点，新结点权值为两者之和，放回集合；重复 n−1 次。n 个叶子的哈夫曼树共有 2n−1 个结点，没有度为 1 的结点。

哈夫曼编码是它的直接应用：把每个字符的频次当权值建树，左分支记 0、右分支记 1，从根到叶的路径就是编码。天然满足前缀码（没有任何编码是另一个编码的前缀），所以解码无歧义；频次高的字符路径短，平均码长最短。这是压缩算法（如 DEFLATE）的核心思想之一。

注意：哈夫曼树不唯一（左右子树可以互换、等权值结点的合并顺序可以换），但 WPL 唯一。

八、树、森林与二叉树的转换

口诀"左孩子右兄弟"：树的每个结点，第一个孩子作为二叉树的左孩子，其余兄弟依次挂在右链上。森林转换则是把各棵树的根当作兄弟串在右链上。

反过来，二叉树还原成森林时，根结点有右孩子的说明有兄弟，所以是森林。

树的遍历对应关系： - 树的先根遍历 ≡ 对应二叉树的先序遍历 - 树的后根遍历 ≡ 对应二叉树的中序遍历

易错点

n₀ = n₂ + 1 里的 n₂ 是"度为 2 的结点数"，不是总结点数。
性质 5 只适用于完全二叉树。
先序 + 后序无法唯一还原，别被题目骗。
哈夫曼树没有度为 1 的结点；WPL 唯一但树形不唯一。
层序遍历必须用队列，不能用栈（用栈出来的是另一种顺序）。

这一章在整门课里的位置

本章的递归遍历直接复习第 3 章的递归与栈；层序遍历用的队列来自第 3 章。往后看，第 6 章的图遍历就是"树遍历的推广"（多分支、要判重）；第 7 章的堆排序建立在完全二叉树的编号性质上；第 8 章的二叉排序树、平衡树、B 树则是二叉树性质在查找场景的延伸。这一章是整门课承上启下的一章。

本篇是《数据结构与算法（93 讲）》第 5 章的知识点摘要。四种遍历的代码与递归树演示见课程页；上一章串与数组，下一章图。