树与二叉树
1.n-1=Knk 结点数与度数的关系
2.满k树的编号为i的结点的双亲结点编号：j=⌊i-2/k⌋+1;结点i的最后一个孩子编号为(i-1)*k+1，当(i-1)%k != 0时，结点i有右兄弟，编号为i+1。
3.完全二叉树的最后一个非终端结点序号：⌊n/2⌋
4.二叉树前中后序中，左右孩子的相对顺序是一样的，所有叶子结点的访问次序是一样的。
5.二叉树转树：从结点的左孩子开始，一直向右走，这些结点即为结点的孩子们；二叉树转森林：根开始一路向右，断开所有的边。
6.树的后序遍历，访问顺序与其对应的二叉树中序遍历顺序相同；森林的后序遍历是各个树后序遍历的线性相加
7.哈夫曼树的构造：先对元素进行排序，后找最小的两个进行求和产生根，然后删除刚刚取出的两个最小元素并将根插入队列，接着再寻找两个最小的元素求和，如此往复。（按层排好）
树的路径长度PL：从根结点到每个结点的路径长度之和。（∑层数*每层的结点树，根结点是第0层）
树的带权路径长度WPL:树种所有叶子结点的带权路径长度之和。（∑层数*每层叶结点权值之和，根结点是第0层）
哈夫曼编码：从哈夫曼树根结点出发，左走0，右走1
8.二叉排序树构造：底部插入，且左子树L<根P<右子树R，故RPL形式的遍历得到从到大小的序列。
9.查找失败和查找成功：查找失败的分母是空结点的数量，查找成功的分母是实结点的数量。查找失败的分子是比较次数*各层空结点数，查找成功其式子中分子均为各层结点数*查找次数，根结点查找次数为1。
10.二叉树的删除结点：①叶子结点直接删除②只有一棵右子树或者一棵左子树，将其孩子放到现在自己的位置③既有左子树又有右子树，将结点的数据域用其直接前驱数据域覆盖，然后删除直接前驱；直接后继同理
二叉排序树中序遍历下的直接前驱和直接后继：
直接前驱（有的话）：A的左孩子代表的树的最右侧的结点。
直接后继（有的话）：A的右孩子代表的树的最左侧的那个结点
11.平衡二叉树：
LL： RR：取相反转 LR、RL：按从左到右顺序转
图
1.无向图的全部顶点的度之和等于边数的两倍；含有n个顶点的无向完全图有n(n-1)/2条边，最多边数：n个顶点的有向完全图有n(n-1)条有向边。
2.矩阵An的元素An[i][j]等于由顶点i到顶点j的长度为n的路径的数目。
无向图中矩阵中行(列)非零元素的个数就是该点的度
3.图的广度优先生成树就是二叉树的层序遍历：一链一层，一层访问完即回溯（队列）
4.邻接表占用空间较多，适合稀疏图；邻接矩阵与边数少，适合稠密图。
5.Prim和Kruskal最小生成树的方法。
单元最短路径：Dijkstra算法，即表格法按趟数每次最短（贪心 ），每次确定一个点
Flyord：即题目中会出现dist-1,dist0.....（即每一步的结果）。
此方法：①先将主对角线处元素对应顶点画十字，十字所在行列元素不变照抄
②十字区域内有∞的，则该位置的对应的行与列均不变照抄
③主对角线元素全为0，直接照抄
④剩余位置，从该位置做十字。与第①次的红十字相交的值，将两值相加，与原位置值相比，取最小者入原位置。
6.时间允许发生的最早时间和最晚时间：正找、相加，取max；反找、相减，取min。
7.在带权图中，没有边用0和∞表示都可以。
8.AOE网：①画出源点，所有没有先驱工序的边都由源点发出。②所有没有出现在先驱工序里的边都指向最后一个顶点——汇点。
工序是工序，顶点是顶点。工序在边上，顶点为Vi
查找
1.折半查找过程中带外部结点的判定树。
2.为了提高顺序查找的效率，将查找概率高的放在最先被查找的位置（先好后坏）
散列表
1.平均查找长度ASL：查找成功的分母是关键字数，如7；查找失败的分母是散列函数所能映射的地址数最大值。
查找失败的分子是从左边第一个元素开始，当它所遇到的第一个空位置，从该元素出发一共有几个数，依次处理后累加（0~P-1，P为%P的P）
H(key)=(key*3)%7
线性探测法即探测到空位置就停下来了。总共需要探测k(1+k)/2次探测。每次解决冲突均从H1(H0)开始
排序
1.二分法插入排序与记录初始状态无关
2直接插入排序：空间O(1),时间O(n^2)
void InsertSort(Element A[], int n)
{
int i, j;
for(i = 2;i <= n; i++){
if(A[i] < A[i-1])
A[0] = A[i];
for(j = i-1; A[j] > A[0]; --j)
A[j+1] = A[j];
A[j+1] = A[0];
}
}
2.3倍移动次数是冒泡排序的考法：比较次序=交换次序=n(n-1)/2,移动次序=3n(n-1)/2.
冒泡排序空间O(1)，时间O(n^2)
3.稳定性：插冒归，统计基
4.快排的一些细节 在P135 第4题，请自行查看
5.得到一个序列中前k个最小元素的部分排列序列，首选堆排序。堆排序是顺序存储的，因为涉及到随机访问。
归并排序代码
