数据结构 第 5 章 名词库
每条最多四行：是（定义）／不是（划掉最常见的误解）／易混（成对的对手）／范围（该结论在什么条件下才成立）。
建设进度：✅ 5.1 树的基本概念 ✅ 5.2 二叉树的概念 ✅ 5.3 遍历与线索二叉树 ✅ 5.4 树、森林 ✅ 5.5 树与二叉树的应用 （全章完整）
5.1 树的基本概念
树
- 是：
个结点的有限集；非空时有且仅有一个根，其余分为 个互不相交的子树。 - 范围：根无前驱，其余结点有且只有一个前驱；
个结点有 条边。
堂兄弟
- 是：双亲在同一层的结点互为堂兄弟。
- 不是：不要求双亲相同。图 5.1 中
与 互为堂兄弟。
层次 / 深度 / 高度
- 是：根为第 1 层；结点的深度 = 所在层次；树的高度 = 最大层数；结点的高度 = 以它为根的子树的高度。
- 易混：深度自上而下数，结点的高度自下而上数。
度
- 是：结点的度 = 孩子个数；树的度 = 结点的最大度数。
- 易混：「度为
的树」至少有一个结点有 个孩子；「 叉树」只要求至多 个孩子。 - 范围：性质 2、4、5 说的是度为
的树，性质 3 说的是 叉树。
路径 / 路径长度
- 是：两结点之间所经过的结点序列；路径长度是路径上经过的边的个数。
- 不是：不是结点数。与第 7 章的「查找长度数结点」正相反。
- 范围：分支有向，同一双亲的两个孩子之间不存在路径。
森林
- 是：
棵互不相交的树的集合。 - 范围：删去树根即成森林；给
棵树加一个根即成树（2016）。
三式联立
- 是：①
；② ；③ 。 - 范围：教材原话「这类题目常在选择题中出现，应当熟练掌握并灵活应用」。
5.2 二叉树的概念
二叉树
- 是：每个结点至多两棵子树，且子树有左右之分，次序不能任意颠倒。
- 不是：不等于度为 2 的有序树——二叉树可以为空，且左右次序是绝对的而非相对的。
- 范围：5 种基本形态；只有一个孩子时也必须确定它是左是右。
满二叉树
- 是：高度为
且有 个结点。 - 范围：叶结点全在最下一层，除叶结点外每个结点度数均为 2。
完全二叉树
- 是：高度为
、有 个结点，当且仅当每个结点都与高度为 的满二叉树中编号 的结点一一对应。 - 范围：可视为从满二叉树中删去若干最底层、最右边的连续叶结点所得。
正则二叉树
- 是：每个分支结点都有 2 个孩子，即只有度为 0 或 2 的结点。
- 不是：不等于满二叉树，形状可以很不规则。
- 易混：哈夫曼树就是正则二叉树。
- 是：非空二叉树上叶结点数等于度为 2 的结点数加 1。
- 范围：只对二叉树成立；教材注意框明说「希望读者牢记并灵活应用」。
完全二叉树的编号性质
- 是：双亲
、左孩子 、右孩子 、层次 、最后一个分支结点 。 - 范围：下标从 1 开始时才成立；叶结点只可能在最后两层；度为 1 的结点最多一个且只有左孩子。
二叉链表的空链域
- 是：含
个结点的二叉链表有 个空链域。 - 范围：推导
，用到 。这 个空链域是线索二叉树的全部原料。
5.3 遍历与线索二叉树
先序 / 中序 / 后序 / 层次遍历
- 是：NLR / LNR / LRN / 逐层。
- 范围：前三种时间
、空间 ；层次遍历用队列，其余用栈。
由遍历序列构造二叉树
- 是：先序+中序、后序+中序、层序+中序三种组合可唯一确定。
- 不是：先序、后序、层序的两两组合无法唯一确定（反例：
/ / ）。 - 范围：中序是唯一能把根的左边和右边切开的序列。
线索 / 线索二叉树
- 是：把二叉链表的空链域改为指向遍历序列中前驱或后继的指针，这些指针称为线索。
- 范围：引入线索二叉树正是为了加快查找结点前驱和后继的速度；全树最多
个线索。
ltag / rtag
- 是：0 表示指向孩子，1 表示指向前驱 / 后继。
- 不是：不要记反。
线索化
- 是：实质就是遍历一次二叉树，用
pre指针记住刚访问过的结点。 - 范围：
CreateInThread末尾必须单独处理中序遍历的最后一个结点（pre->rchild=NULL; pre->rtag=1;）。
Firstnode
- 是：沿
ltag==0一路向左到底，返回中序序列的第一个结点。 - 不是：教材注释明说「最左下结点，不一定是叶结点」——它可能有右孩子。
带头结点的线索链表
- 是：头结点
lchild指根、rchild指中序最后一个结点；中序首尾结点的相应指针都指向头结点。 - 范围：相当于建立了一个双向线索链表，可从前往后或从后往前遍历。
5.4 树、森林
双亲表示法
- 是：连续空间 + 伪指针
parent，根的伪指针域为 −1。 - 范围：找双亲快，求孩子需遍历整个结构；并查集用的就是它。
孩子兄弟表示法
- 是：又称二叉树表示法，
fch指第一个孩子、nsib指下一个兄弟。 - 范围：它就是「左孩子右兄弟」转换的存储形式。
左孩子右兄弟
- 是：树转二叉树的规则——左指针指第一个孩子，右指针指相邻右兄弟。
- 范围：根结点没有兄弟，所以树转换得到的二叉树没有右子树。 画法：兄弟连线 → 只留第一个孩子的连线 → 顺时针转 45°。
二叉树转森林
- 是：沿根的右链逐段断开，每段还原成一棵树。
- 范围：二叉树转换为树或森林是唯一的；根有右子树 ⇒ 对应的是森林而非一棵树。
树 / 森林的遍历对应
- 是：树的先根 ↔ 二叉树先序；树的后根 ↔ 二叉树中序；森林的先序 ↔ 先序；森林的中序 ↔ 中序。
- 不是：树没有「后序遍历」，只有先根 / 后根（加层次）；森林只有先序 / 中序。
5.5 树与二叉树的应用
带权路径长度 WPL
- 是：
， 是叶结点的权， 是它到根的路径长度。 - 不是：不累加非叶结点；
不是层数。 - 范围：也等于所有非叶结点权值之和，可用来验算。
哈夫曼树
- 是：含
个带权叶结点的二叉树中 WPL 最小者，也称最优二叉树。 - 不是：不唯一（左右分支表 0 / 1 无规定，且权值相同的结点会造成不同形态）。
- 范围：WPL 必然相同且为最优；结点总数
，新建 个，不存在度为 1 的结点。
哈夫曼树的构造
- 是：每次取两棵根权值最小的树合并，新结点权为两者之和，放回森林，直至只剩一棵。
- 范围：权值越小的结点到根的路径长度越大。
前缀编码
- 是：没有一个编码是另一个编码的前缀。
- 不是：不是「有公共前缀」。
- 范围：
0/10/110是前缀编码；再加11就不是了（11是110的前缀）。
哈夫曼编码
- 是：以字符频度为权构造哈夫曼树，从根到叶的分支标记串即编码。
- 范围：利用哈夫曼树可以设计出总长度最短的二进制前缀编码；教材例子相对 3 位定长压缩了 25%。
并查集
- 是：支持
Initial/Union/Find三种操作的集合表示，用树的双亲表示存储。 - 范围：
Find为， Union为； Union要求两根互不相交，否则不执行合并。
并查集的根
- 是：根结点的双亲域为负数，可设置为该子集合元素数量的相反数。
- 不是：不是
fa[x]==x自环，不是深度、不是秩。 - 范围：优化后把小树合并到大树，深度不超过
；路径压缩是进一步的优化。
高频范围限定清单
| 常见说法 | 范围限定 |
|---|---|
| 「 | 错。 |
| 「兄弟结点之间存在路径」 | 错。分支有向，同一双亲的孩子之间无路径 |
| 「路径长度是结点数」 | 错。是边数。与第 7 章的查找长度相反 |
| 「堂兄弟必须同一个祖父」 | 错。只要双亲同层 |
| 「 | 错。至多 |
| 「度为 | 错。 |
| 「森林至少一棵树」 | 错。 |
| 「二叉树就是度为 2 的有序树」 | 错。可以为空，且左右次序是绝对的 |
| 「 | 错。只对二叉树 |
| 「正则二叉树 = 满二叉树」 | 错。正则只要求没有度为 1 的结点 |
| 「完全二叉树的叶结点都在最后一层」 | 错。只可能在最后两层 |
| 「完全二叉树可以有多个度为 1 的结点」 | 错。最多一个，且只有左孩子 |
| 「左孩子是 | 错。只对完全二叉树且下标从 1 开始 |
| 「二叉链表有 | 错。 |
| 「先序 + 后序可唯一确定二叉树」 | 错。三种非中序序列两两组合都不行 |
| 「层次遍历用栈」 | 错。用队列 |
| 「非递归遍历比递归省空间」 | 错。都是 |
「ltag=1 表示有左孩子」 | 错。0 才是孩子，1 是线索 |
| 「线索化不需要遍历」 | 错。线索化的实质就是遍历一次 |
「Firstnode 返回最左下的叶结点」 | 错。不一定是叶结点 |
| 「中序线索树遍历需要栈」 | 错。空间 |
| 「双亲表示法找孩子快」 | 错。求孩子要遍历整个结构 |
| 「树转换的二叉树可能有右子树」 | 错。根没有兄弟 |
| 「二叉树转树的结果不唯一」 | 错。唯一 |
| 「树的后根遍历对应二叉树的后序」 | 错。对应中序 |
| 「树有先序中序后序三种遍历」 | 错。只有先根、后根（加层次） |
| 「WPL 累加所有结点」 | 错。只算叶结点 |
| 「哈夫曼树唯一」 | 错。树不唯一，WPL 唯一 |
| 「哈夫曼树有 | 错。 |
| 「哈夫曼树可能有度为 1 的结点」 | 错。不存在 |
| 「前缀编码 = 有公共前缀」 | 错。是没有一个编码是另一个的前缀 |
「并查集根的 fa[x]==x」 | 错。教材口径是 S[x] 为负数 |
| 「根存的负数是深度或秩」 | 错。是成员数量的相反数 |
「Union 是 | 错。Find |
「Union 可对同一集合执行」 | 错。要求两根互不相交 |
链接
- 🏠 返回总览：数据结构第 5 章：树与二叉树总览
- 📕 附录入口：数据结构附录