XP02 DAY7 树与图学习笔记
一、树的基础概念
1. 为什么要学习树？
以前我们学过数组。
数组像一排队伍：
它是一条直线，一个接一个。
但是生活中很多关系不是一条直线。
比如：
这种关系有分支、有层次，就很适合用树来描述。
2. 树是什么？
树是一种：
通俗理解：
它能很好地描述：
3. 生活中的树结构
树结构很常见：
例如电脑文件夹：
最上面的 D盘 就像树根。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
二、树中的常见名字
1. 节点
树上的每一个对象叫做：
比如下面这棵树：
1、2、3、4、5 都是节点。
2. 边
连接两个节点的线叫做：
例如：
边表示两个节点之间有关系。
3. 根
一棵树最上面的节点叫做：
例如：
这里 1 是根。
根可以理解为：
4. 父子关系
如果一个节点直接连着下面的节点，那么上面的叫：
下面的叫：
例如：
1 是 2 和 3 的父亲。
2 和 3 是 1 的儿子。
5. 兄弟关系
如果两个节点有同一个父亲，它们就是：
例如：
2 和 3 有同一个父亲 1，所以它们是兄弟。
6. 祖先
一个节点往上走，经过的节点都可以叫它的：
例如：
4 的父亲是 2。
4 的祖先有：
7. 叶子节点
没有儿子的节点叫做：
例如：
叶子节点是：
因为它们下面没有儿子。
8. N 个点，N - 1 条边
树有一个非常重要的性质：
例如：
这句话要记住：
9. 特殊的树：一条链
有一种特殊的树长得像一条线：
它没有明显的分叉。
这种树叫：
链也是树，只是它比较“瘦”。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
三、树的存储
1. 为什么要存树？
题目不会真的画一棵树给程序看。
程序只能读数字。
比如输入：
表示：
我们要把这些关系存进程序里。
2. VECTOR 存儿子
如果知道父子关系，可以用：
含义：
例如：
可以存成：
3. 数组存父亲
也可以用数组记录每个节点的父亲：
含义：
例如：
可以写成：
4. 树存储关键操作
每读入一组：
就表示：
所以：
表示把 child 放到 father 的儿子列表里。
表示记录 child 的父亲是 father。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
四、二叉树
1. 什么是二叉树？
二叉树是一种特殊的树。
它的特点是：
这两个儿子一般叫：
例如：
这里每个节点最多只有两个儿子，所以它是二叉树。
2. 不是二叉树的例子
如果一个节点有 3 个儿子：
这就不是二叉树。
因为节点 1 有三个儿子。
3. 满二叉树
满二叉树可以理解为：
例如：
这棵树就是满二叉树。
4. 完全二叉树
完全二叉树可以理解为：
例如：
这是完全二叉树。
因为最后一层虽然没满，但节点是从左往右连续摆放的。
不是完全二叉树的例子：
中间有空位，不是从左往右连续放。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
五、二叉树的常见性质
1. 性质 1：第 I 层最多有多少节点？
二叉树第 i 层最多有：
例如：
层数 最多节点数 第 1 层 1 第 2 层 2 第 3 层 4 第 4 层 8
为什么？
因为每往下一层，每个节点最多分成两个儿子。
2. 性质 2：深度为 K 的二叉树最多有多少节点？
深度为 k 的二叉树最多有：
例如深度为 3：
总共：
3. 性质 3：叶子节点和度为 2 的节点
先认识一个词：
例如：
在二叉树中：
这个性质初学时先会用即可。
例子：
叶子节点：
所以 n0 = 3。
度为 2 的节点：
所以 n2 = 2。
满足：
4. 性质 4：完全二叉树的深度
如果一棵完全二叉树有 n 个节点，它的深度大约是：
初学时可以理解成：
例如：
5. 性质 5：数组编号
如果一棵完全二叉树按层编号：
对于编号为 i 的节点：
例如：
这个性质常用于：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
六、二叉树的存储
1. 用数组存左右儿子
普通二叉树可以用两个数组存：
含义：
如果没有儿子，可以记为 0。
例如：
可以存成：
2. 完全二叉树可以直接用编号
如果是完全二叉树，并且节点按层编号，那么不一定要开 leftSon 和 rightSon。
因为可以直接算：
前提是：
3. 用数组遍历完全二叉树的思路
如果完全二叉树从 1 开始编号：
当儿子编号超过 n 时，说明这个儿子不存在。
比如 n = 7，访问节点 2 时：
访问节点 4 时：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
七、树的遍历顺序
1. 什么是遍历？
遍历就是：
例如有一棵树：
遍历就是要把：
都访问到。
只是访问顺序可能不同。
2. 前序遍历
前序遍历顺序：
也就是：
例子：
前序遍历：
3. 中序遍历
中序遍历顺序：
也就是：
上面的树中序遍历：
4. 后序遍历
后序遍历顺序：
也就是：
上面的树后序遍历：
5. 如何记住？
看“根”在哪里：
6. 中序 + 其他一种遍历能确定二叉树
性质：
为什么中序很重要？
因为中序可以告诉我们：
前序或后序可以告诉我们：
所以两者配合，就能确定树。
7. 为什么只有前序和后序不一定够？
如果一棵树是一条链，可能会出现不确定。
例如：
它也可能是：
前序都是：
后序都是：
但是它们不是同一棵树。
所以：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
八、图的基础概念
1. 为什么要学习图？
树是一种有层次的关系。
但是生活中很多关系不是上下级，而是互相连接。
比如城市道路：
这种关系更适合用图。
2. 图是什么？
图由两部分组成：
点表示对象。
边表示对象之间的关系。
例如：
3. 有向图和无向图
无向图：
例如：
如果 A 是 B 的朋友，B 也是 A 的朋友。
有向图：
例如：
A 关注 B，不代表 B 关注 A。
4. 带权图
如果边上有一个数，这个数叫：
带权图就是：
例如：
这里 5 和 3 就是边权。
5. 度
无向图中，一个点连了几条边，这个数量叫：
例如：
那么 A 的度是：
有向图中还会分：
6. 自环与重边
自环：
例如：
重边：
例如：
7. 完全图
完全图就是：
比如有 4 个同学，每两个人都互相认识。
这就可以看成完全图。
8. 路径
路径就是：
例如：
就是从 A 到 C 的一条路径。
9. 环路
如果从一个点出发，走了一圈又回到自己，这叫：
例如：
就是一个环。
10. 连通性
如果两个点之间可以通过若干条边走到，就说它们是：
如果图中任意两个点都能互相到达，这个图就是：
11. 稀疏图和稠密图
稀疏图：
稠密图：
比如 1000 个点：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
九、树和图的关系
1. 树其实是一种特殊的图
树可以看成一种特殊的图。
它满足：
2. 树和图的区别
内容 树 图 关系特点 有层次，像上下级 更自由，任意点之间都可能有边 是否有环 没有环 可以有环 边数 n 个点有 n - 1 条边 不一定 例子 文件夹、家族树 地图、朋友关系
简单记：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
十、图的存储
1. 为什么要存图？
图也不能直接画给程序看。
题目通常会输入：
表示：
我们需要把这些边存起来。
2. 边的表示方法
一条边可以用两个点表示：
表示：
如果是带权边：
表示：
例如：
表示：
3. 邻接矩阵
邻接矩阵用二维数组存图。
含义：
如果：
表示有边。
如果：
表示没有边。
4. 无向图邻接矩阵
如果是无向图，u 和 v 互相连接。
所以要写两次：
5. 邻接矩阵优缺点
优点：
缺点：
例如 100000 个点，二维数组会非常大，不能这样开。
6. 邻接表
邻接表用 vector 存每个点连着哪些点。
含义：
例如有边：
那么：
7. 无向图邻接表
无向图中，u 连 v，v 也连 u。
所以要写：
8. 邻接矩阵和邻接表对比
存储方式 适合情况 优点 缺点 邻接矩阵 点少，边可能多 判断是否有边很快 占空间大 邻接表 点多，边比较少 省空间 判断两点是否直接相连没那么直接
初学建议：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
十一、综合应用与学习建议
1. 树题常见问法
树题可能会问：
2. 图题常见问法
图题可能会问：
今天只学习基础概念和存储。
后面做图题时，会继续学习：
3. 学习建议
树和图一开始会觉得抽象。
不要急着背所有术语。
先抓住：
然后再慢慢理解：
