- 一、 树的基本概念
- 1.1 树的 性质
- 二、 二叉树
- 2.1 二叉树定义及其主要特性
- 2.1.1 定义
- 2.1.2 几个特殊的二叉树
- ⭐ 满二叉树 与 完全 二叉树
- ⭐ 二叉排序树 与 平衡 二叉树
- 2.1.3 小知识回顾
- 2.1.4 二叉树的性质
- 2.2 二叉树的存储
- 2.2.1 顺序存储
- 2.2.2 链式存储
- 三、 二叉树的遍历 与 线索二叉树
- 3.1 二叉树的遍历
- 3.1.1 先序遍历
- 3.1.2 中序遍历
- 3.1.3 后序遍历
- 3.1.4 求树的深度
- 3.1.5 层次遍历
- 3.2 由遍历序列 构造 二叉树
- 3.2.1 只通过前、中、后 序 序列 其中的一个 不能确定一个唯一的二叉树
- 3.2.2 通过中序 加 任一 一个 遍历序列 就可以构造一棵唯一的二叉树
- 3.2.3 通过 遍历序列 确定 唯一 二叉树 总结
- 3.3 线索 二叉树
- 3.3.1 线索二叉树 解决什么？
- 3.3.2 先、中、后二叉树的线索化
- 1. 土办法 找 中序 遍历的 某结点的 前驱
- 2. 先、中、后 线索化 （⭐ 视频 讲解版本的代码）
- 3. 先、中、后 线索化 （⭐ 王道书版本）
- 3.3.3 先、中、后序 线索化后的 二叉树 如何 找到 前驱 后继？
- 1. 中序 线索化的 树 找前驱、后继
- ⭐ 寻找后继
- ⭐ 寻找前驱
- 2. 先序 线索化的 树 找前驱、后继
- 找后续
- 找前驱
- 3. 后序 线索化的 树 找前驱、后继
- 找后继
- 找前驱
- 4. 找前驱后驱，非线索总结
- 四、 树 与 森林
- 4.1 树的存储结构
- 4.1.1 双亲表示法
- 4.1.2 孩子表示法
- 4.1.3 孩子兄弟表示法
- 4.2 树、森林与二叉树的转换
- 4.3 树、森林 的遍历
- 4.3.1 树的先根遍历
- 4.3.2 树的 后根 遍历
- 4.3.3 树的层次遍历 （通过 队列实现）
- 4.3.4 森林的先序遍历
- 4.3.5 森林的中序遍历
- 4.3.6 树、森林 与对应的二叉树 遍历小总结
- 五、 树的应用 （哈夫曼树 与 并查集）
- 5.1 哈夫曼树
- 5.1.1 带权路径
- 5.1.2 哈夫曼树
- 5.1.3 构造一个 哈夫曼树
- 5.1.4 哈夫曼编码
- 5.1.5 小回顾
- 5.2 并查集
- 5.2.1 查 并查集
- 5.2.2 并 并查集
- 5.2.3 并查集 的 初始化、 查 、并 （代码，时间复杂度分析）
- 5.2.4 并查集 的优化
- 5.2.4.1 并的 优化
- 5.2.4.1 查的 优化
- 5.2.4.2 并查集的 优化 （代码、时间复杂度）
⭐ 五种基本形态
标准的错误 的 完全二叉树
- 如果 一个 二叉排序树 同时是 平衡 二叉树 的话，那么 平衡二叉树的搜索效率更高!
-
叶子结点 比 度为2 的结点 多一个
-
二叉树 第 i 层 有 多少个结点？
-
高度 为 h 的 二叉树的 结点 最大数
-
知道 结点个数 推断 二叉树高度
推法一：
推法二：
-
完全二叉树 由 总结点数 推出 度为 0 、1 、 2 分别的个数！
- ⭐ 只适合存储 完全二叉树
⭐ 完全二叉树 的顺序存储
⭐ 非 完全 二叉树 的顺序存储
2.2.2 链式存储 三、 二叉树的遍历 与 线索二叉树 3.1 二叉树的遍历 3.1.1 先序遍历 3.1.2 中序遍历 3.1.3 后序遍历 3.1.4 求树的深度
- 这种方式会浪费 掉 大量的存储空间
- 判断是否有左孩子、右孩子不能通过 与总结点比较的方式， 可通过 结构体里设置的 isEmpty变量判断！
3.1.5 层次遍历
- 因为树的深度是结点最大层次
- 二叉树最多只有 两个 分支 ， 判断从根结点开始， 通过递归 判断 最大的深度返回！
- 通过 队列实现 层次遍历
- 实现思想如下：
- 初始化一个队列，根结点入栈；
- 队列非空， 队头出栈， 判断出队元素是否有孩子结点， 如果有，将左、右孩子依次 队尾 入队；
- 重复步骤② ， 直至 队列为 空；
⭐ 代码实现
⭐ 先序
⭐中序
⭐ 后序
⭐ 中序 ＋ 前序 确定 一个 唯一的 二叉树
- 例子1
- 例子2
⭐ 中序 ＋ 后序 确定 一个 唯一的 二叉树
例子
⭐ 中序 ＋ 层次 确定 一个 唯一的 二叉树
- 例子1
- 例子2
⭐ 没有 中序 序列 外的 任两 序列组合 确定不了 一棵 唯一的 二叉树
⭐ 小总结
⭐ 普通二叉树只是在根结点开始，遍历。
- 弊端1，无法从任意一个结点开始遍历，只能在根结点开始。
- 弊端2，任意一个结点，无法直接找到他的前驱、后继。(这里的前驱后继指的是按先中后层次遍历的顺序序列的前驱后继）
- 如果 想去查找， 通过 从根结点 按 先、中、后遍历过程中， 修改访问根节点的 哪个方法的 逻辑 进行实现。
⭐ 将二叉树线索化 (把没有指向的（n+1）个空指针利用起来)
- 利用 空指针域 来填充前驱后继。
- 空的左指针指向前驱； 空的右指针指向后继
⭐ - 但是 有的结点左、右指针 指向自己的孩子结点。 所以线索化后的二叉树需要分别 左右指针指向的是 孩子结点还是前驱后继；通过 加 ltag与rtag 属性（0孩子 1线索）
⭐ 前中后遍历的线索二叉树形状
⭐ 小总结
3.3.2 先、中、后二叉树的线索化 1. 土办法 找 中序 遍历的 某结点的 前驱 2. 先、中、后 线索化 （⭐ 视频 讲解版本的代码）- 中序 线索化
(完整代码)
- 先序 线索化
- 注意这是 一个 有瑕疵的， 就是 会引发 左孩子循环的 代码
- 这个代码就是健壮性的代码
- 左指针线索化后，可能 指向自己的前驱，然后 再左递归的时候又回到自己的前驱了，形成循环。 所以 判断一下 rtag是线索还是孩子。
（先序线索化的完整代码）
- 后序 线索化
- 中序 序列化
- 与视频讲解第一个区别： pre为啥是引用类型?
答： pre是引用类型，是因为pre每次都要记录移动后的前驱，所以带引用的话就 不是局部作用了
- 为啥直接把 right设置为 null？
答： 王道书中直接把最后一个阶段right设置为null，因为中序遍历，最后访问落在的结点没有right
-
先序 线索化
-
后序 线索化
- 思想
- 假如找 P 的 后续结点
- 如果右指针 是线索（右指针无孩子） 即 rtag == 1；则右指针就是指向后继
- 但是 如果 右指针指向 孩子， 即 rtag==0； 则
因为 中序 序列 是 左>根>右 ， 所以P的 后继为 （P的 右孩子） 开始的最左下的结点；因此我们写一个方法： 传入 P->rchild, 让这个结点一直寻找 最左下 的结点；注意P的后继！！！右子树的最左下；
- 代码实现（寻找某个结点的后继、从某节点开始中序遍历）
⭐ 寻找前驱
- 补充 这种方式的中序遍历，时间复杂度为 O(1)；
注意: 通过找后续的方式是从指定结点正序 的 中序遍历
- 思想
- 假如找 P 的前驱
- ltag为1； 即 P的左指针指向线索； 所以前驱就是 就是 P-> lchild；
- ltag为0； 即 P的左指针指向孩子； 进行推理； 中序是 左>根>右；
注意 是 P的前驱， 又是中序遍历； 所以 就是 左子树的最右下边的结点；
2. 代码实现
- 思想
找前驱
- 假如找P 的 后继
- 如果 rtag == 1； 即 右指针为线索， 所以 后继就是P->rchild;
- 但是 rtag == 0； 即 右指针指向 右孩子， 所以 我们就要推理 先序 遍历的 后继为啥；
先序遍历 为 根>左>右； 因此我们可以看出 P为根， 如果P有 左孩子，后续就是左孩子， P没有左孩子那么一定有右孩子， 那么后继就是 右孩子。 所以写一个方法去判断是左右孩子就行。 那么有人会说为啥没有左必须有右孩子？傻瓜？ 既然不是线索了，那么肯定就至少存在一个孩子老！
- 思想
- 因为我们 每个结点的 前驱后继 线索一定是 建立在 P的孩子结点身上， 而 我们如果找前驱的话，针对 先序遍历 而言！ P结点的前驱一定不在它的孩子结点。 而是 父亲结点
- 所以只通过 有左右指针的结点 的线索二叉树 是无法完成的
3. 后序 线索化的 树 找前驱、后继 找后继
- 因此 如果建立在 结点除了 左右指针域 ，还要有 一个 指向 父级的结点； 可以通过一下思想寻找 先序线索二叉 的 前驱；
- 思想
- 与先序线索化 找 前驱一样， 后序 找 后继 也是 无法通过孩子结点来找 因为 后续遍历为 左> 右> 根， 后边没东西了
- 所以只通过 有左右指针的结点 的线索二叉树 是无法完成的
找前驱
- 因此 如果建立在 结点除了 左右指针域 ，还要有 一个 指向 父级的结点； 可以通过一下思想寻找 先序线索二叉 的 前驱；
- 思想
4. 找前驱后驱，非线索总结
- 假如找P 的 前驱
- 如果 rtag == 1； 即 左指针为线索， 所以 前驱就是P->lchild;
- 但是 rtag == 0； 即 左指针指向 左孩子， 所以 我们就要推理 后序 遍历的 后继为啥；
后续 遍历 为 左> 右 > 根； 所以 P为 根 前驱为 有 右孩子就是 右孩子， 没有 右孩子就是左孩子， 没有右孩子一定会存在左孩子！！
四、 树 与 森林 4.1 树的存储结构 4.1.1 双亲表示法重在理解! 根据 先、中、后遍历去理解
1 双亲表示法，这种方式，可以用顺序存储实现，就是数组。 每个结点有一个记录双亲的下标的属性，这个方式，找双亲比较容易，但是找孩子得遍历。删除的时候，两种方式，一是设置双亲为-1，二是将被删除位置替代其他元素。 删除时如果删除的是叶子结点，直接删除，如果是中间结点，就要遍历把这个结点的孩子都删了
4.1.3 孩子兄弟表示法2 孩子表示法，这种方式是，每个结点都指向自己的孩子。通过顺序加链式方式实现，顺序存储的是每个结点，并且有一个指向自己第一个孩子的next指针yu，每个结点都一个指向孩子和有兄弟的指针。
4.2 树、森林与二叉树的转换3 双亲兄弟表示法，这个方式链式存储，就是可以将树或者森林转换成二叉树进行存储（左孩子右兄弟思想）
就是 左孩子 右兄弟 的思想
4.3.2 树的 后根 遍历树的先根遍历 对应 转换成二叉树后 先序遍历
4.3.3 树的层次遍历 （通过 队列实现）树的 后根 遍历 对应 其二叉树 的 中序遍历
4.3.4 森林的先序遍历树的层次遍历 通过 队列 实现
4.3.5 森林的中序遍历方案 1 ： 先序遍历森林，有两层递归，理解的时候就是对每个树先序遍历，然后排序就行
方案 2 ： 森林转为二叉树后的先序遍历与森林先序遍历一致
4.3.6 树、森林 与对应的二叉树 遍历小总结 五、 树的应用 （哈夫曼树 与 并查集） 5.1 哈夫曼树 5.1.1 带权路径 5.1.2 哈夫曼树对森林的中序，就是对每个树的后续遍历！
转为二叉树后就是对二叉树的中序 (因为对树的后根序就是对转换二叉树的中序)
5.1.3 构造一个 哈夫曼树带权 路径 长度 最小 的 二叉树 称为 哈夫曼树 也 叫 最优二叉树。
5.1.4 哈夫曼编码
- 权值越小， 到根越远
- 结点总数： 2n-1
- 不存在度为 1的结点
- 并不唯一，但 WPL必然相同，且为最小/优
- 不一定 非要是 完全二叉树
-
固定长度编码
-
变长编码
5.1.5 小回顾注意 编码符合前缀编码： 没有一个编码是另一个编码的前缀；
5.2 并查集 5.2.1 查 并查集（学习启迪，开发时，哈夫曼树，可以优化搜索。如果在设计搜索时，对搜索的数据或者内容有频率统计时，可以将频率看成权值，然后把数据保存成哈夫曼树，可以以最优方式搜索数据。
可以将集合用树表示
通过互不相交的树表示多个集合，如何查一个元素属于那个集合？
通过查这个元素属于哪个树，树根标识，找到树根！
同样判断两个元素是否属于同一个集合的思想就是找这两个元素的树根，看看是否相同
5.2.3 并查集 的 初始化、 查 、并 （代码，时间复杂度分析） 5.2.4 并查集 的优化 5.2.4.1 并的 优化因为集合通过树表示，而且并和查，都需要找到根。所以并查集可以通过双亲表示法存储。树根标识为-1
优化并查集的查，其实查的时间复杂度取决于树的深度，而并的时候如果小树并入到大树，并不会增加深度，因此优化查其实是在并的时候做优化，将小树并入到大树
但是如何通过代码知道哪个树的深度更深呢，呢，因为我们通过双亲表示法存储的树，每棵树的树根都是-1，表示不再有双亲。因此我们可以通过修改-1为-n，其中n表示树的深度。在并的操作时比较两个树的深度大小。将小树并入大树
同时注意修改。小树根不再是根，而是实现大树的根，也就是大树的根成为小树的双亲了。
但是视频讲解中，并不是考察的树的深度，而是结点的个数，我个人认为结点个数多少并不能决定深度
⭐ 代码：
5.2.4.2 并查集的 优化 （代码、时间复杂度）在查的时候进行路径压缩
- 第一步找到查找结点的根结结点。
- 第二部，将x寻找根经过的每个结点都挂到根部
点开链接玩一玩: (可视化的数据结构)
