考研复习Day 16 | 数据结构与算法 --树与二叉树（上）
一、树的基本概念
1.1 树的定义
树：n（n≥0）个结点的有限集。
当 n=0 时，称为空树
当 n>1 时，其余结点可分为 m 个互不相交的有限集，每个集合本身又是一棵树，称为根的子树
树的定义是递归的——在定义中引用了自身，因此树是一种典型的递归数据结构。
树的逻辑特征：
| 特征 | 说明 |
|---|---|
| 根结点 | 没有前驱，唯一 |
| 其他结点 | 有且仅有一个前驱 |
| 所有结点 | 可拥有零个或多个后继 |
重要结论：在包含 n 个结点的树中，恰好存在n-1 条边。
1.2 基本术语
以图5.1中的树为例（根A，子结点B、C、D...）：
| 术语 | 说明 | 示例 |
|---|---|---|
| 祖先 | 从根到某结点路径上的所有结点 | B是K的祖先 |
| 子孙 | 某结点子树中的所有结点 | K是B的子孙 |
| 双亲 | 路径上最接近该结点的结点 | E是K的双亲 |
| 孩子 | 双亲的直接后继 | K是E的孩子 |
| 兄弟 | 具有相同双亲的结点 | K与L互为兄弟 |
| 堂兄弟 | 双亲位于同一层的结点 | G与E、F、H、I、J互为堂兄弟 |
| 结点的层次 | 根为第1层，其孩子为第2层，以此类推 | |
| 结点的深度 | 结点所在的层次 | |
| 树的高度（深度） | 树中结点的最大层数 | |
| 结点的高度 | 以该结点为根的子树的高度 | |
| 结点的度 | 结点的孩子个数 | |
| 树的度 | 树中所有结点的度的最大值 | |
| 分支结点（非终端结点） | 度 > 0 的结点 | |
| 叶结点（终端结点） | 度 = 0 的结点 | |
| 有序树 | 子树从左到右有固定次序，不可互换 | |
| 无序树 | 子树无固定次序 | |
| 路径 | 从一个结点到另一个结点所经过的结点序列 | |
| 路径长度 | 路径上边的数目 | |
| 森林 | m（m>0）棵互不相交的树的集合 |
森林与树的关系：将树的根结点移除后，其各子树构成一个森林；反之，为m棵独立的树添加一个新结点作为共同根，森林便转化为一棵树。
1.3 树的性质
| 性质 | 公式 | 说明 |
|---|---|---|
| 结点数与度数的关系 | n = 总度数 + 1 | 除根结点外，每个结点都有唯一双亲 |
| 度为m的树第i层最多结点数 | m^(i-1) | 第1层1个，第2层m个，第3层m²个... |
| 高度为h的m叉树最多结点数 | (m^h - 1)/(m - 1) | 各层结点数达到最大时 |
| 度为m、n个结点的树最小高度 | 树应尽可能饱满 | |
| 度为m、n个结点的树最大高度 | n - m + 1 | 至少一个结点有m个孩子，其他层仅一个结点 |
二、二叉树的概念
2.1 二叉树的定义及其主要特性
二叉树：每个结点至多拥有两棵子树（不存在度大于2的结点），且子树有明确的左右之分，次序固定，不可交换。
二叉树的5种基本形态：
空二叉树
只有根结点
只有左子树
只有右子树
左右子树都有
二叉树与度为2的有序树的区别：
度为2的树至少3个结点，二叉树可以为空
度为2的有序树中，只有一个孩子时无须区分左右；二叉树中左右位置是结构本身的固有属性
2.2 几种特殊的二叉树
| 特殊二叉树 | 定义 | 特点 |
|---|---|---|
| 满二叉树 | 高度为h，包含2^h-1个结点 | 每一层结点数都达到最大；所有叶结点在最下一层；除叶结点外，每个结点度均为2 |
| 完全二叉树 | 高度为h，n个结点，与满二叉树中编号1~n的结点一一对应 | 叶结点只出现在最后两层；最多只有一个度为1的结点 |
| 二叉排序树 | 左子树所有结点 < 根结点 < 右子树所有结点 | 左右子树本身也是二叉排序树 |
| 平衡二叉树 | 任意结点左右子树高度差绝对值 ≤ 1 | — |
| 正则二叉树 | 每个分支结点均有2个孩子 | 树中仅有度为0或2的结点 |
完全二叉树的编号性质（编号从1开始）：
| 性质 | 公式 |
|---|---|
| 最后一个分支结点编号 | ⌊n/2⌋ |
| 结点i的双亲编号 | ⌊i/2⌋（i>1） |
| 结点i的左孩子编号 | 2i（若存在） |
| 结点i的右孩子编号 | 2i+1（若存在） |
| 结点i所在层次 | ⌊log₂i⌋ + 1 |
| 完全二叉树高度 | ⌈log₂(n+1)⌉或⌊log₂n⌋ + 1 |
2.3 二叉树的性质
| 性质 | 公式 | 说明 |
|---|---|---|
| 叶子结点与度为2的结点关系 | n₀ = n₂ + 1 | 非空二叉树 |
| 第k层最多结点数 | 2^(k-1) | k≥1 |
| 高度为h的二叉树最多结点数 | 2^h - 1 | — |
性质1的证明：设n₀、n₁、n₂分别为度为0、1、2的结点数，n = n₀ + n₁ + n₂。分支数B = n - 1 = n₁ + 2n₂，代入得n₀ = n₂ + 1。
2.4 二叉树的存储结构
1. 顺序存储结构
使用一组连续的存储单元，按层序（自上而下、自左至右）存储二叉树结点。
适用场景：完全二叉树和满二叉树最适用，能最大限度节省存储空间。
缺点：一般二叉树需插入“空结点”补全为完全二叉树形状，最坏情况（单支树）需要近2^h-1个存储单元，空间利用率极低。
建议：从数组下标1开始存储，保证数组下标与结点编号一致。
2. 链式存储结构（二叉链表）
typedef struct BiTNode { ElemType data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree;重要结论：在含有n个结点的二叉链表中，共有n+1个空链域（常考选择题）。
三、二叉树的遍历
3.1 三种递归遍历
| 遍历方式 | 访问顺序 | 遍历序列（图5.7二叉树） |
|---|---|---|
| 先序遍历（PreOrder） | 根 → 左 → 右 | 1,2,4,6,3,5 |
| 中序遍历（InOrder） | 左 → 根 → 右 | 2,6,4,1,3,5 |
| 后序遍历（PostOrder） | 左 → 右 → 根 | 6,4,2,5,3,1 |
递归算法模板：
// 先序遍历 void PreOrder(BiTree T) { if (T != NULL) { visit(T); // 访问根结点 PreOrder(T->lchild); PreOrder(T->rchild); } } // 中序遍历 void InOrder(BiTree T) { if (T != NULL) { InOrder(T->lchild); visit(T); InOrder(T->rchild); } } // 后序遍历 void PostOrder(BiTree T) { if (T != NULL) { PostOrder(T->lchild); PostOrder(T->rchild); visit(T); } }时间复杂度：O(n)（每个结点访问一次）
空间复杂度：O(h)（递归工作栈深度等于树高，最坏情况O(n)）
3.2 层次遍历
借助队列，从上到下、从左到右逐层访问。
void LevelOrder(BiTree T) { Queue Q; InitQueue(Q); BiTree p = T; if (p != NULL) EnQueue(Q, p); while (!QueueEmpty(Q)) { DeQueue(Q, p); visit(p); if (p->lchild != NULL) EnQueue(Q, p->lchild); if (p->rchild != NULL) EnQueue(Q, p->rchild); } }3.3 由遍历序列构造二叉树
核心原则：必须知道中序序列，再辅以先序、后序或层序中的任意一种，才能唯一确定一棵二叉树。
| 已知序列组合 | 是否能唯一确定二叉树 |
|---|---|
| 先序 + 中序 | 能 |
| 后序 + 中序 | 能 |
| 层序 + 中序 | 能 |
| 先序 + 后序 | 不能 |
| 先序 + 层序 | 不能 |
| 后序 + 层序 | 不能 |
构造方法：
| 组合 | 方法 |
|---|---|
| 先序+中序 | 先序第一个为根 → 在中序中划分左右子树 → 递归 |
| 后序+中序 | 后序最后一个为根 → 在中序中划分左右子树 → 递归 |
| 层序+中序 | 层序第一个为根 → 在中序中划分左右子树 → 层序中后续结点依次为各子树的根 |
四、线索二叉树
4.1 线索二叉树的基本概念
背景：在n个结点的二叉树中，有n+1个空链域。利用这些空指针指向遍历序列中的前驱或后继，称为线索化。
结点结构：
| 标志位 | 含义 |
|---|---|
ltag = 0 | lchild指向左孩子 |
ltag = 1 | lchild指向前驱线索 |
rtag = 0 | rchild指向右孩子 |
rtag = 1 | rchild指向后继线索 |
存储结构定义：
typedef struct ThreadNode { ElemType data; struct ThreadNode *lchild, *rchild; int ltag, rtag; } ThreadNode, *ThreadTree;4.2 中序线索二叉树的构造
设
pre指向刚刚访问过的结点，p指向当前正在访问的结点。
void InThread(ThreadTree &p, ThreadTree &pre) { if (p != NULL) { InThread(p->lchild, pre); // 递归线索化左子树 if (p->lchild == NULL) { // 左孩子为空，建立前驱线索 p->lchild = pre; p->ltag = 1; } if (pre != NULL && pre->rchild == NULL) { // 前驱的右孩子为空，建立后继线索 pre->rchild = p; pre->rtag = 1; } pre = p; // 标记当前结点为刚访问过的结点 InThread(p->rchild, pre); // 递归线索化右子树 } } void CreateInThread(ThreadTree T) { ThreadTree pre = NULL; if (T != NULL) { InThread(T, pre); pre->rchild = NULL; // 处理最后一个结点 pre->rtag = 1; } }4.3 中序线索二叉树的遍历
找中序第一个结点：
ThreadNode *FirstNode(ThreadNode *p) { while (p->ltag == 0) p = p->lchild; // 最左下结点 return p; }找中序后继：
ThreadNode *NextNode(ThreadNode *p) { if (p->rtag == 0) return FirstNode(p->rchild); // 右子树的最左下结点 else return p->rchild; // 直接返回后继线索 }非递归中序遍历：
void InOrder(ThreadNode *T) { for (ThreadNode *p = FirstNode(T); p != NULL; p = NextNode(p)) visit(p); }4.4 先序和后序线索二叉树
| 遍历方式 | 查找后继的复杂度 |
|---|---|
| 先序线索 | 较简单：有左孩子则左孩子为后继，否则右孩子为后继，否则线索直接指向 |
| 后序线索 | 较复杂：需要知道双亲信息，通常需用三叉链表 |
后序线索查找后继的三种情况：
| 情况 | 后继 |
|---|---|
| 结点是根 | 后继为空 |
| 结点是双亲的右孩子，或是双亲的左孩子且双亲无右孩子 | 后继为双亲 |
| 结点是双亲的左孩子且双亲有右子树 | 后继为右子树中后序第一个结点 |
五、思考
1. 树 ≈ 文件系统
电脑文件夹结构就是一棵树：根目录是根结点，子文件夹是子树，文件是叶子结点。
2. 递归遍历 ≈ 俄罗斯套娃
每打开一个套娃，里面还有一个更小的套娃，直到最小的那个（空树）。递归就是这种“自己包含自己”的结构。
3. 层次遍历 ≈ 逐层打印
就像BFS（广度优先搜索），一层一层地处理，先处理根，再处理所有孩子，再处理所有孙子。
4. 线索二叉树 ≈ 链表的“快速跳转”
把二叉树变成链表一样的结构，遍历时不需要递归，直接沿着线索走。
注：以上内容参考 2027年数据结构考研复习指导 王道论坛 组编，其中有一些个人想法，如有任何错误或不妥，欢迎各位大佬指出，如果各位有一些有意思的想法，也可以和我交流一下~感谢！
六、一点题外话
学习了二叉树，脑海中不由得浮现出了中学学过的一篇课文：美国诗人罗伯特·弗罗斯特创作的《未选择的路》：
黄色的树林里分出两条路，
可惜我不能同时去涉足，
我在那路口久久伫立，
我向着一条路极目望去，
直到它消失在丛林深处。
但我却选了另外一条路，
它荒草萋萋，十分幽寂，
显得更诱人、更美丽，
虽然在这条小路上，
都很少留下旅人的足迹，
虽然那天清晨落叶满地，
两条路都未经脚印污染。
啊，留下一条路等改日再见！
但我知道路径延绵无尽头，
恐怕我难以再回返。
也许多少年后在某个地方，
我将轻声叹息把往事回顾，
一片树林里分出两条路，
而我选了人迹更少的一条，
因此走出了这迥异的旅途。
1. 二叉树的结构 = 人生的“分岔点”
每一个选择，都是一个结点；选择的结果，决定你走向哪一棵子树。
我们的人生，就是一棵巨大的、不断生长的二叉树。每一个自己，都是由无数次“左拐还是右拐”塑造出来的。
2. 路径的“不可逆性” = 人生没有撤回键
“啊，留下一条路等改日再见！但我知道路径延绵无尽头，恐怕我难以再回返。”
二叉树中，一旦你选择了左子树，就无法再回到父结点去走右子树（除非有父指针）。
人生也一样：你选择了一条路，就不可能同时体验另外那条路。
这就是选择的代价，也是选择的庄严。
3. “成功路不止一条” = 二叉树有多条路径到达叶结点
“这些路径中有很多都是可以通向成功的，成功的路不止一条。”
二叉树中，从根到任何一个叶结点的路径，都是一条完整的、独特的旅途。没有哪条路径是“标准答案”，也没有哪条路径是“绝对的错误”。只要最终到达了你想去的“叶结点”，这条路径就是对的。
4.“受挫折时想二叉树”
受到挫折时候想一想二叉树，只要没有结束，就永远会有翻盘的机会。
二叉树的高度 ≠ 成功的早晚
二叉树中，从根到叶结点的路径长度可以完全不同：
有的叶结点在第3层（早早成功）
有的叶结点在第10层（大器晚成）
只要还没到NULL（放弃），你就还在遍历中。
人生就像是二叉树，是在无数次的选择中成长的，选择决定了我是怎么样的一个我。只要没有结束，永远会有翻盘的机会。这些路径中有很多都是可以通向成功的，成功的路不止一条。
七、明日计划
树与二叉树（下）— 树、森林与二叉树的转换、哈夫曼树