Day7 树与图学习笔记
2026-07-27 20:12:13
发布于：广东
XP02 Day7 树与图学习笔记
一、树的基础概念
1. 为什么要学习树？
以前我们学过数组。
数组像一排队伍：
1 2 3 4 5
它是一条直线，一个接一个。
但是生活中很多关系不是一条直线。
比如：
学校
├── 一年级
│ ├── 一班
│ └── 二班
├── 二年级
│ ├── 一班
│ └── 二班
这种关系有分支、有层次，就很适合用树来描述。
2. 树是什么？
树是一种：
非线性结构。
通俗理解：
不是一条直线，而是像树枝一样会分叉。
它能很好地描述：
分支关系；
层次关系；
上下级关系；
父子关系。
3. 生活中的树结构
树结构很常见：
家族关系
学校年级班级
电脑文件夹
公司组织结构
比赛晋级表
例如电脑文件夹：
D盘
├── 课程资料
│ ├── Day1
│ ├── Day2
│ └── Day3
└── 图片
├── 课堂截图
└── 作业截图
最上面的 D盘 就像树根。
二、树中的常见名字
1. 节点
树上的每一个对象叫做：
节点。
比如下面这棵树：
1
├── 2
│ ├── 4
│ └── 5
└── 3
1、2、3、4、5 都是节点。
2. 边
连接两个节点的线叫做：
边。
例如：
1 和 2 之间有一条边。
1 和 3 之间有一条边。
2 和 4 之间有一条边。
边表示两个节点之间有关系。
3. 根
一棵树最上面的节点叫做：
根。
例如：
1
├── 2
└── 3
这里 1 是根。
根可以理解为：
整棵树的起点。
4. 父子关系
如果一个节点直接连着下面的节点，那么上面的叫：
父亲。
下面的叫：
儿子。
例如：
1
├── 2
└── 3
1 是 2 和 3 的父亲。
2 和 3 是 1 的儿子。
5. 兄弟关系
如果两个节点有同一个父亲，它们就是：
兄弟。
例如：
1
├── 2
└── 3
2 和 3 有同一个父亲 1，所以它们是兄弟。
6. 祖先
一个节点往上走，经过的节点都可以叫它的：
祖先。
例如：
1
└── 2
└── 4
4 的父亲是 2。
4 的祖先有：
2 和 1
7. 叶子节点
没有儿子的节点叫做：
叶子节点。
例如：
1
├── 2
│ ├── 4
│ └── 5
└── 3
叶子节点是：
3, 4, 5
因为它们下面没有儿子。
8. n 个点，n - 1 条边
树有一个非常重要的性质：
如果一棵树有 n 个点，那么它一定有 n - 1 条边。
例如：
3 个点的树，有 2 条边。
5 个点的树，有 4 条边。
10 个点的树，有 9 条边。
这句话要记住：
树：n 个点，n - 1 条边。
9. 特殊的树：一条链
有一种特殊的树长得像一条线：
1 - 2 - 3 - 4 - 5
它没有明显的分叉。
这种树叫：
链。
链也是树，只是它比较“瘦”。
三、树的存储
1. 为什么要存树？
题目不会真的画一棵树给程序看。
程序只能读数字。
比如输入：
1 2
1 3
2 4
2 5
表示：
1 和 2 有关系
1 和 3 有关系
2 和 4 有关系
2 和 5 有关系
我们要把这些关系存进程序里。
2. vector 存儿子
如果知道父子关系，可以用：
vector<int> son[N];
含义：
son[x] 里面存 x 的所有儿子。
例如：
1 的儿子：2, 3
2 的儿子：4, 5
可以存成：
son[1].push_back(2);
son[1].push_back(3);
son[2].push_back(4);
son[2].push_back(5);
3. 数组存父亲
也可以用数组记录每个节点的父亲：
int fa[N];
含义：
fa[x] 表示 x 的父亲是谁。
例如：
2 的父亲是 1
3 的父亲是 1
4 的父亲是 2
5 的父亲是 2
可以写成：
fa[2] = 1;
fa[3] = 1;
fa[4] = 2;
fa[5] = 2;
4. 树存储关键操作
每读入一组：
father child
就表示：
father 是 child 的父亲。
child 是 father 的儿子。
所以：
son[father].push_back(child);
表示把 child 放到 father 的儿子列表里。
fa[child] = father;
表示记录 child 的父亲是 father。
四、二叉树
1. 什么是二叉树？
二叉树是一种特殊的树。
它的特点是：
每个节点最多有 2 个儿子。
这两个儿子一般叫：
左儿子；
右儿子。
例如：
1
/ \
2 3
/ \
4 5
这里每个节点最多只有两个儿子，所以它是二叉树。
2. 不是二叉树的例子
如果一个节点有 3 个儿子：
1
/ | \
2 3 4
这就不是二叉树。
因为节点 1 有三个儿子。
3. 满二叉树
满二叉树可以理解为：
每一层都放满了节点。
例如：
1
/ \
2 3
/ \ / \
4 5 6 7
这棵树就是满二叉树。
4. 完全二叉树
完全二叉树可以理解为：
前面的层都是满的，最后一层从左往右连续放。
例如：
1
/ \
2 3
/ \ /
4 5 6
这是完全二叉树。
因为最后一层虽然没满，但节点是从左往右连续摆放的。
不是完全二叉树的例子：
1
/ \
2 3
\ \
5 7
中间有空位，不是从左往右连续放。
五、二叉树的常见性质
1. 性质 1：第 i 层最多有多少节点？
二叉树第 i 层最多有：
2^(i - 1) 个节点
例如：
| 层数 | 最多节点数 |
|---|---|
| 第 1 层 | 1 |
| 第 2 层 | 2 |
| 第 3 层 | 4 |
| 第 4 层 | 8 |
为什么？
因为每往下一层，每个节点最多分成两个儿子。
2. 性质 2：深度为 k 的二叉树最多有多少节点？
深度为 k 的二叉树最多有：
2^k - 1 个节点
例如深度为 3：
第 1 层最多 1 个
第 2 层最多 2 个
第 3 层最多 4 个
总共：
1 + 2 + 4 = 7 = 2^3 - 1
3. 性质 3：叶子节点和度为 2 的节点
先认识一个词：
度：一个节点的儿子数量。
例如：
有 0 个儿子，度为 0，也就是叶子节点。
有 1 个儿子，度为 1。
有 2 个儿子，度为 2。
在二叉树中：
如果叶子节点数量是 n0，
度为 2 的节点数量是 n2，
那么 n0 = n2 + 1。
这个性质初学时先会用即可。
例子：
1
/ \
2 3
/ \
4 5
叶子节点：
3, 4, 5
所以 n0 = 3。
度为 2 的节点：
1, 2
所以 n2 = 2。
满足：
n0 = n2 + 1
3 = 2 + 1
4. 性质 4：完全二叉树的深度
如果一棵完全二叉树有 n 个节点，它的深度大约是：
log2(n) + 1
初学时可以理解成：
完全二叉树长得比较矮，因为每一层都尽量放满。
例如：
7 个节点的满二叉树，深度是 3。
5. 性质 5：数组编号
如果一棵完全二叉树按层编号：
1
/ \
2 3
/ \ / \
4 5 6 7
对于编号为 i 的节点：
左儿子编号：2 * i
右儿子编号：2 * i + 1
例如：
节点 2 的左儿子是 4，右儿子是 5。
节点 3 的左儿子是 6，右儿子是 7。
这个性质常用于：
用数组存完全二叉树。
六、二叉树的存储
1. 用数组存左右儿子
普通二叉树可以用两个数组存：
int leftSon[N];
int rightSon[N];
含义：
leftSon[x] 表示 x 的左儿子。
rightSon[x] 表示 x 的右儿子。
如果没有儿子，可以记为 0。
例如：
1
/ \
2 3
可以存成：
leftSon[1] = 2;
rightSon[1] = 3;
2. 完全二叉树可以直接用编号
如果是完全二叉树，并且节点按层编号，那么不一定要开 leftSon 和 rightSon。
因为可以直接算：
左儿子 = 2 * i
右儿子 = 2 * i + 1
前提是：
这个儿子的编号不能超过 n。
3. 用数组遍历完全二叉树的思路
如果完全二叉树从 1 开始编号：
访问当前节点 i；
再去访问左儿子 2 * i；
再去访问右儿子 2 * i + 1。
当儿子编号超过 n 时，说明这个儿子不存在。
比如 n = 7，访问节点 2 时：
左儿子是 4
右儿子是 5
访问节点 4 时：
左儿子是 8，超过 n，不存在
右儿子是 9，超过 n，不存在
七、树的遍历顺序
1. 什么是遍历？
遍历就是：
按照某种顺序，把树上的每个节点都访问一遍。
例如有一棵树：
1
/ \
2 3
/ \
4 5
遍历就是要把：
1, 2, 3, 4, 5
都访问到。
只是访问顺序可能不同。
2. 前序遍历
前序遍历顺序：
根 -> 左 -> 右
也就是：
先访问自己，再访问左子树，再访问右子树。
例子：
1
/ \
2 3
/ \
4 5
前序遍历：
1 2 4 5 3
3. 中序遍历
中序遍历顺序：
左 -> 根 -> 右
也就是：
先访问左子树，再访问自己，再访问右子树。
上面的树中序遍历：
4 2 5 1 3
4. 后序遍历
后序遍历顺序：
左 -> 右 -> 根
也就是：
先访问左子树，再访问右子树，最后访问自己。
上面的树后序遍历：
4 5 2 3 1
5. 如何记住？
看“根”在哪里：
前序：根在前面。
中序：根在中间。
后序：根在后面。
6. 中序 + 其他一种遍历能确定二叉树
性质：
中序遍历 + 前序遍历，可以确定一棵二叉树。
中序遍历 + 后序遍历，也可以确定一棵二叉树。
为什么中序很重要？
因为中序可以告诉我们：
哪些节点在根的左边；
哪些节点在根的右边。
前序或后序可以告诉我们：
谁是根。
所以两者配合，就能确定树。
7. 为什么只有前序和后序不一定够？
如果一棵树是一条链，可能会出现不确定。
例如：
1
└── 2
它也可能是：
1
\
2
前序都是：
1 2
后序都是：
2 1
但是它们不是同一棵树。
所以：
前序 + 后序 不一定能唯一确定二叉树。
八、图的基础概念
1. 为什么要学习图？
树是一种有层次的关系。
但是生活中很多关系不是上下级，而是互相连接。
比如城市道路：
A 城市和 B 城市有路
B 城市和 C 城市有路
A 城市和 C 城市也有路
这种关系更适合用图。
2. 图是什么？
图由两部分组成：
点；
边。
点表示对象。
边表示对象之间的关系。
例如：
城市是点，道路是边。
学生是点，朋友关系是边。
网页是点，链接是边。
3. 有向图和无向图
无向图：
边没有方向。
例如：
A 和 B 是朋友。
如果 A 是 B 的朋友，B 也是 A 的朋友。
有向图：
边有方向。
例如：
A 关注了 B。
A 关注 B，不代表 B 关注 A。
4. 带权图
如果边上有一个数，这个数叫：
权值。
带权图就是：
边带有权值的图。
例如：
A 到 B 的路长 5 公里。
B 到 C 的路长 3 公里。
这里 5 和 3 就是边权。
5. 度
无向图中，一个点连了几条边，这个数量叫：
度。
例如：
A 连着 B、C、D
那么 A 的度是：
3
有向图中还会分：
入度：有多少条边指向它。
出度：有多少条边从它指出去。
6. 自环与重边
自环：
一个点连向自己。
例如：
A -> A
重边：
两个点之间有多条边。
例如：
A 和 B 之间有两条不同的路。
7. 完全图
完全图就是：
任意两个点之间都有边。
比如有 4 个同学，每两个人都互相认识。
这就可以看成完全图。
8. 路径
路径就是：
从一个点走到另一个点，经过的一串点和边。
例如：
A -> B -> C
就是从 A 到 C 的一条路径。
9. 环路
如果从一个点出发，走了一圈又回到自己，这叫：
环路。
例如：
A -> B -> C -> A
就是一个环。
10. 连通性
如果两个点之间可以通过若干条边走到，就说它们是：
连通的。
如果图中任意两个点都能互相到达，这个图就是：
连通图。
11. 稀疏图和稠密图
稀疏图：
边比较少。
稠密图：
边比较多。
比如 1000 个点：
只有 999 条边，比较稀疏。
接近每两个点都有边，比较稠密。
九、树和图的关系
1. 树其实是一种特殊的图
树可以看成一种特殊的图。
它满足：
连通；
没有环；
n 个点，n - 1 条边。
2. 树和图的区别
| 内容 | 树 | 图 |
|---|---|---|
| 关系特点 | 有层次，像上下级 | 更自由，任意点之间都可能有边 |
| 是否有环 | 没有环 | 可以有环 |
| 边数 | n 个点有 n - 1 条边 | 不一定 |
| 例子 | 文件夹、家族树 | 地图、朋友关系 |
简单记：
树更像家族关系。
图更像道路网络。
十、图的存储
1. 为什么要存图？
图也不能直接画给程序看。
题目通常会输入：
n m
u1 v1
u2 v2
...
um vm
表示：
有 n 个点，m 条边。
每条边连接 ui 和 vi。
我们需要把这些边存起来。
2. 边的表示方法
一条边可以用两个点表示：
u v
表示：
u 和 v 之间有一条边。
如果是带权边：
u v w
表示：
u 到 v 有一条边，权值是 w。
例如：
1 2 5
表示：
1 到 2 的边，权值是 5。
3. 邻接矩阵
邻接矩阵用二维数组存图。
int g[N][N];
含义：
g[u][v] 表示 u 和 v 之间是否有边。
如果：
g[u][v] = 1;
表示有边。
如果：
g[u][v] = 0;
表示没有边。
4. 无向图邻接矩阵
如果是无向图，u 和 v 互相连接。
所以要写两次：
g[u][v] = 1;
g[v][u] = 1;
5. 邻接矩阵优缺点
优点：
判断两个点之间有没有边很方便。
直接看 g[u][v]。
缺点：
如果点很多，会占很多空间。
例如 100000 个点，二维数组会非常大，不能这样开。
6. 邻接表
邻接表用 vector 存每个点连着哪些点。
vector<int> g[N];
含义：
g[u] 里面存所有和 u 相连的点。
例如有边：
1 - 2
1 - 3
2 - 4
那么：
g[1] 里面有 2, 3
g[2] 里面有 1, 4
g[3] 里面有 1
g[4] 里面有 2
7. 无向图邻接表
无向图中，u 连 v，v 也连 u。
所以要写：
g[u].push_back(v);
g[v].push_back(u);
8. 邻接矩阵和邻接表对比
| 存储方式 | 适合情况 | 优点 | 缺点 |
|---|---|---|---|
| 邻接矩阵 | 点少，边可能多 | 判断是否有边很快 | 占空间大 |
| 邻接表 | 点多，边比较少 | 省空间 | 判断两点是否直接相连没那么直接 |
初学建议：
如果题目点很多，优先想到邻接表。
十一、综合应用与学习建议
1. 树题常见问法
树题可能会问：
谁是谁的父亲？
谁有哪些儿子？
某个节点有几个儿子？
树上有多少叶子节点？
按照某种顺序遍历树。
2. 图题常见问法
图题可能会问：
两个点之间有没有边？
一个点连着哪些点？
从 A 能不能走到 B？
图中有没有环？
最短路是多少？
今天只学习基础概念和存储。
后面做图题时，会继续学习：
DFS；
BFS；
最短路；
连通块。
3. 学习建议
树和图一开始会觉得抽象。
不要急着背所有术语。
先抓住：
树：有层次，像家族关系。
图：点和边，像地图道路。
然后再慢慢理解：
怎么存？
怎么遍历？
怎么解决题目？
这里空空如也
有帮助，赞一个