树的通用特点
- N 个结点的树有 N-1 条分支
树的遍历
- 树的遍历需要栈的支持
- 中序遍历序列+(先序序列 || 后序序列 || 层序序列)=唯一确定的一棵二叉树
void InOrder(BiTree t){
if(t!=null){
visit(t); //先序遍历
InOrder(t->lchild);
visit(t); //中序遍历
InOrder(t->rchild);
visit(t); //后序遍历
}
}完全二叉树
结点的位置与层序遍历的结果一一对应的二叉树。
线索二叉树
- 当没有左右孩子时，child 域指向其前驱（后继）
- 线索二叉树不能有效解决先序线索二叉树查找先序前驱和后序线索二叉树查找后序后继 (点击跳转解析)
- 由于上面原因，后序线索树的遍历仍需要压栈保存辅助，而前序和中序线索树可以靠线索遍历，不需要用到栈
结点结构：
| lchild | ltag | data | rtag | rchild |
|---|---|---|---|---|
| ltag=0: 指示结点的左孩子; ltag=1: 指示结点的前驱 | 0 或 1 | 0 或 1 | ltag=0: 指示结点的左=右孩子; ltag=1: 指示结点的后驱 |
树、森林和二叉树的转换
1. 树转换为二叉树
- 在兄弟结点之间加线连接
- 每个结点只保留和第一个（最左边）孩子的连线，去掉和其他孩子的连线
- 以树根为轴心，顺时针旋转 45 度
- 最终结果就是每个结点的左子树是第一个孩子，右子树是该结点的兄弟（左孩子右兄弟）
2. 二叉树转换为树
为树转换为二叉树的逆过程
3. 森林转换为二叉树
- 先把森林中每棵树转换为二叉树
- 此时每棵树的根视为兄弟关系，所以将每棵树的根成为前一棵树的右子树
4. 二叉树转换为森林
森林转换为二叉树的逆过程，把根结点和每个右子树拆开
5. 总结特征
树：父结点和其子结点直接连接
二叉树：父结点左结点连接第一个子结点，子结点的右结点连接其兄弟结点
森林：多个树
树和森林的遍历
| 树 | 森林 | 二叉树 |
|---|---|---|
| 先根遍历（先序遍历） | 先序遍历：对每棵树进行先序遍历 | 先序遍历 |
| 后根遍历（后序遍历） | 中序遍历：对每棵树进行后序遍历，之所以叫做中序遍历是因为森林的中序遍历和森林转换成二叉树后对二叉树的中序遍历是一样的顺序，对于森林的每颗单独的树来说仍是后序遍历。 | 中序遍历 |
堆
堆是由数组实现的完全二叉树，同时必须是部分有序的 (partially ordered)，并由此分为
- 大根堆 max heap：任意结点的值都大于等于其子结点值
- 小根堆 min heap：任意结点的值都小于等于其子结点值
1. 堆的调整
堆的调整算法，分为两个：
自顶向下
数据长度为 m，从根结点数据开始，一直到第 个数据，依次比较以该结点为根结点的树的结点大小并调整位置。
主要用于堆删除结点，删除结点之后把最后一个结点替换到，当前根结点位置，对此结点进行自顶向下操作。
自底向上
数据长度为 m，从第 个数据开始，一直到第 1 个也就是根结点数据，依次比较该结点为根结点的树的结点大小并调整位置。
主要用于结点的插入，当一个结点插入到这个堆之后，向上调整堆，堆还能符合大顶堆或者小顶堆的定义。
2. 构建堆的过程
将 m 个数据构成一个完全二叉树，然后进行 自底向上 的调整
哈夫曼树
- 度为 m 的哈夫曼树，只包含度为 0 的叶子结点和度为 m 的分支结点两种结点
- 普通的二叉哈夫曼树，n 个元素生成哈夫曼树需要 n-1 个分支结点，所以一共有 2n-1 个结点
- WPL（带权路径长度）=（每个叶子结点的权值*路径长度）之和=所有分支结点的值之和
- 加权平均长度= （每个叶子结点的权值*路径长度）之和/(每个结点的权值之和)
补虚段问题
在一般情况下，对于 k 路平衡归并来说，若 ，则不需要增加虚段；否则需附加 个虚段。
Link to original
并查集
- 并查集通常用树的双亲表示作为并查集的存储结构
- 并查集的根结点的双亲域为负数（当一个结点的双亲域为负数时判断该结点为根结点）
- 并查集的 Find() 函数 return 包含 x 的树的根的位置
- 并查集的 Union() 函数合并两个不同根的并查集
- 路径优化：查询到一个结点的根为根节点 root 后，修改路径上的所有结点的根为 root，以减少查找长度