树的存储结构
双亲表示法
这种存储结构采用一组连续空间来存储每个结点,同时在每个结点中增设一个伪指针,指示其双亲节点在数组中的位置,根结点下标为0,其伪指针为-1。
孩子表示法
孩子表示法是将每个结点的孩子都用单链表链接起来的一个线性结构,此时n个节就有n个孩子链表,叶结点的孩子链表为空表。寻找双亲的操作需要遍历n个结点中孩子链表指针域所指针的n个孩子链表
孩子兄弟表示法
又称二叉树表示法, 以二叉链表作为树的存储结构。孩子兄弟表示法使得每个结点包括三内容:节点值,指向结点第一个孩子的结点的指针,以及指向下一个兄弟结点的指针。这种存储表示法比较灵活,其最大优点是可以方便地实现树转换为二叉树的操作,易于查找节点的孩子等。若为每个结点增设一个parent,则查找节点的父节点也很方便。
树、森林与二叉树的转换
树转二叉树
树转换为二叉树的规则:每个结点左指针指向它的第一个孩子,右指针指向它在树中的相邻右兄弟,这个规则又称“”“左孩子右兄弟”。由于根节点没有兄弟,所以对应的二叉树没有右子树
1. 在兄弟结点之间加一条连线
2. 对每个结点,只保留它与第一个孩子的连线,其他孩子的连线全部抹掉
3. 以树根为轴心,顺时针旋转$45^。$
森林转二叉树
- 将森林中的每棵树都转换成相应的二叉树
- 每棵树的根也可视为兄弟关系,在每科树的根之间加一根连线
- 以第一棵树的根为轴心顺时针旋转$45^。$
二叉树转森林
若二叉树非空,则以二叉树的根及其左子树为第一棵树的二叉树形式,故将根的右链断开。二叉树根的右子树又可视为一个由除第一棵树外的森林转换后的二叉树,应用同样的方法,直到最后一棵没有右子树的二叉树为止。二叉树转换为树或深林是唯一的。
树和森林的遍历
树的先根遍历
先访问根结点,再依次遍历根结点的每棵子树,与二叉树的先序序列相同。
树的后根遍历
先依次遍历根结点的每棵子树,再访问根结点。与二叉树的中序序列相同。
先序遍历森林
- 访问森林中第一棵树的根结点
- 先序遍历第一棵树中根结点的子树森林
- 先序遍历除去第一棵树之后剩余的树构成的森林
中序遍历森林
- 中序遍历森林中第一棵树的根结点的子树森林
- 访问第一棵树的根结点
- 中序遍历除去第一棵树之后剩余的树构成的森林
对应
树 | 森林 | 二叉树 |
---|---|---|
先根遍历 | 先序遍历 | 先序遍历 |
后根遍历 | 中序遍历 | 中序遍历 |
# 哈夫曼树和哈夫曼编码
树的结点被赋予一个表示某种意义的值,称为该结点的权。从权的根结点到任意结点的路径长度(经过的边数)与该结点上权值的乘积称为该结点的带权路径长度,记为:
$$
WPL=\sum^{n}_{i=1}w_il_i
$$
在含有n个带权结点的二叉树中,其中WPL最小的二叉树称为哈夫曼树,也称最优二叉树。
哈夫曼树的构造
- 选两个权值最小的结点
- 把这两个结点相加生成新结点C作为这连个结点的双亲
-
重复以上步骤,直到还剩一个点没选选过
-
构建过程中新建了n-1个结点,哈夫曼树总结点数为2n-1
- 每个初始结点都称为了叶节点
- 哈夫曼树不存在度为1的节点
并查集
直接上代码
#include<iostream>
using namespace std;
const int N = 110;
int p[N];
int find(int x){
if(x = p[x]) p[x] = find(p[x]);
return p[x];
}
//b->a
void merge(int a, int b) {
p[find(a)] = find(b);
}
void init(){
//初始化
for(int i = 0; i < N; i ++) p[i] = i;
}
int main(){
}