一、线索二叉树
- 规律：在有n个节点的链式二叉树中必定存在 n+1 个空指针
- 链式二叉树中有很多的空指针，可以让这些空指针指向前一个节点\后一个节点，从而在有序遍历（中序遍历）二叉树时，不需要使用递归而通过循环即可以完成，并且效率要比递归快得多
- 一定是搜索二叉树
线索二叉树的结构
typedef struct TreeNode {
int data; // 数据域
struct TreeNode* left;
bool lflag; // 左子树是否是线索 为真时，左子树是线索 指向前一个节点
struct TreeNode* right;
bool rflag; // 右子树是否是线索 为真时，右子树是线索 指向下一个节点
} TreeNode;
构建线索二叉树
- 首先需要有一颗搜索二叉树，然后通过中序遍历并生成线索，通过检查右子树是否为空来决定是否生成线索，让右子树指向下一个节点。
- 当构成线索二叉树后 ，可以通过循环遍历的方式有序遍历二叉树，不需要中序递归遍历也可以
二、选择树
- 是一种完全二叉树，把待比较的数据存储在最后一层，根节点的值是左右子树中其中一个，是它们的最大值或最小值，选择树的功能是快速地找出最大值或最小值
三、堆
堆结构介绍
大顶堆（大根堆）：根节点的值比左右子树都大，同时左右子树都满足该规则
小顶堆（小根堆）：根节点的值比左右子树都小，同时左右子树都满足该规则
堆结构是一种特殊的完全二叉树，它与堆内存是两种概念
堆结构的根节点一定是整棵树中的最大值、最小值
堆结构如何存储：
首先堆结构是一种完全二叉树，并且需要在使用的时候频繁地找双亲节点进行比较，所以链式不好找双亲节点，因此堆结构非常适合用顺序存储，通过二叉树性质5来实现找双亲：
性质5：
有一个n个结点的完全二叉树，结点按照从上到下从左到右的顺序排序为1~n。
1、i > 1时，i/2就是它的双亲结点。
2、i*2是i的左子树，当i*2>n时，则i没有左子树。
3、2*i+1是i的右子树，2*i+1>n时，则i没有右子树
堆排序
- 借助堆结构，先把待排序数组先调整成大顶堆或者小顶堆结构，然后堆顶与末尾元素交换，从堆顶到末尾元素的前一个元素之间重新调整成堆结构，重复该步骤，最后当堆中只剩一个元素时，待排序数组就有序了。
- 可以循环实现、也可以递归实现
- 堆结构还是优先队列的底层逻辑
平衡二叉树(AVL树)
- 前提一定是搜索二叉树，对于根节点的左右子树的高度差不能超过1，并且所有子树都要循序这个要求
- 如果一个搜索二叉树呈现或接近单支状，它的查找效率很低，很接近链表，因此如果能让它平衡时，查找效率最高
- 由于节点的位置要受到相互之间值的影响，并且在往平衡二叉树中添加节点或者删除节点前，二叉树本身是平衡的，所以只可能在最后操作的节点附近不满足平衡条件，因此需要在该过程中对该节点进行判断并调整。
- 因此一棵平衡二叉树因为添加操作导致不平衡的原因，总结就四种：
第一种：
x y
/ \ / \
y t1 z x
/ \ / \ / \
z t2 t3 t4 t2 t1
/ \
t3 t4 以y为轴 右旋转
第二种：
x y
/ \ / \
t1 y x z
/ \ / \ / \
t2 z t1 t2 t3 t4
/ \
t3 t4 以y为轴 左旋转
第三种：
x x z
/ \ / \ / \
y t1 z t1 y x
/ \ / \ / \ / \
t2 z y t4 t2 t3 t4 t1
/ \ / \
t3 t4 t2 t3
先以z为轴左旋转 再以z为轴右旋转 达到平衡
第四种：
x x z
/ \ / \ / \
t1 y t1 z x y
/ \ / \ / \ / \
z t2 t3 y t1 t3 t4 t2
/ \ / \
t3 t4 t4 t2
先以z为轴右旋转 再以z为轴左旋转 达到平衡
删除节点
- 待删除的节点是叶子节点，直接删除
- 待删除节点的左子树或者右子树为空，则使用非空节点替换
- 待删除节点左右子树非空，则根据左右子树的高度，选择高的一边子树，如果是左子树高，选择左子树中的最大节点赋值给待删除节点，然后再左子树中继续删除该最大节点，相当于继续处理情况1或情况2；如果是右子树高，则在右子树选择最小值节点继续同样处理。
- 删除后可能导致不平衡，需要重新调整平衡
平衡二叉树的优点：
避免了二叉搜索树呈现单支状，让其能以最佳的效率进行查找操作 O(log2n)
平衡二叉树的缺点：
在插入、删除操作时，为了达到平衡需要进行大量的左旋、右旋操作、计算高度，所以此时操作速度慢
因此AVL树适合在数据量大并且数据量比较稳定，没有太多的插入、删除操作，适合大量的查找操作。
红黑树
- 是一种自平衡的有序二叉树，不是根据树的高来调整平衡、而是树节点的颜色来调整
红黑树的特性:
（1）每个节点或者是黑色，或者是红色。
（2）根节点是黑色。
（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
（4）如果一个节点是红色的，则它的子节点必须是黑色的。
（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
红黑树的优点：
插入、删除操作的效率比AVL高
缺点：
没有AVL那么均匀，查找效率略低于AVL树，但是因为性质5决定了不至于太差，综合而言，综合性能优秀，所以应用场景很多
哈夫曼树
相关基础概念
路径长度：从一个节点到另一个节点之间的路径条数目
从根节点到第L层节点路径长度是L-1
树的路径长度： 从根节点出发到每个节点的路径长度之和
节点的权：如果给树中每个节点赋予一个某种含义的数值，该数值称为该节点的权值
节点的带权路径长度：从根节点到该节点的路径长度与该节点的权值的乘积
树的带权路径长度:所有叶子节点的带权路径长度之和 WPL
成绩： <60 60~69 70~79 80~89 90~100
等级 E D C B A
比例 5% 30% 40% 15% 10%
普通带权二叉树的WPL：
WPL=1*5+2*30+3*40+4*15+4*10 = 285
哈夫曼树的WPL：
WPL=40+2*30+3*15+4*5+4*10 = 205
WPL是评价一棵带权二叉树优劣重要标准
哈夫曼树：一定是一棵WPL最小的带权二叉树
构建哈夫曼树：
1、把n个带权节点先存储一个集合F中，每个节点的左右子树都为空
2、从F中选取根节点的权值最小的两个节点作为左右子树构成一棵新的二叉树，左小右大，这颗二叉树的根节点的权值等于两个子树权值之和
3、从F中删除刚刚取出来的两个节点，并把新形成的二叉树根节点放入F中
4、重复步骤2、3，直到F中只剩下一棵树，就是哈夫曼树
哈弗曼编码
目的：当年是为了解决远距离通信传输内容最优解问题
代发送文字：ABBCD EEAFD
方法1：转换成二进制 001 总共要发送30个二进制数
方法2：
1、根据字母出现频率，构建哈夫曼树
假设：A 28 B 5 C 7 D 18 E 30 F 12、
2、规定哈夫曼树中左分支为0，右分支为1，从根节点出发到叶子节点经过的路径分支组成的0和1的有序序列就是该叶子节点的哈弗曼编码
A 10 B 0110 C 0111 D 00 E11 F010
ABBCD EEAFD哈夫曼编码：100110011001110011111001000 总共27字符
作用：数据压缩、文件压缩也是一种解法
标签：子树,t4,t2,t3,二叉树,数据结构,节点 From： https://www.cnblogs.com/sleeeeeping/p/18328451