根据先序、中序、后序确定二叉树：

#背景：树和二叉树基本上都有先序、中序、后序、按层遍历等遍历顺序，根据先序和后序不一定可以确定一棵二叉树，给定中序和其它一种遍历的序列就可以确定一棵二叉树的结构。

抓住中序特点：已知根节点，向根节点左右各自延申，直到触及之前节点，元素分别包含在左右子树

抓住先序特点：对一棵树的所有节点作包围，包围圈的第一个元素为根节点

抓住后序特点：对一颗树的所有节点作包围，包围圈的最后一个元素为根节点

前缀表达式、中缀表达式和后缀表达式：

1.中缀转前缀、后缀：根据运算优先级将算式提取出来，将运算符提到前面或者后面，然后紧跟两个操作数，对于非元部分继续根据运算优先级提取算式。

2.后缀转中缀：假设一个栈，从左到右将数字和算符压入，当栈顶出现：“操作数操作数符号” 的组合时，弹出，将符号还原后放回栈中，整体作为一个操作数（视情况加括号）

3.前缀转中缀：假设一个队列，从左到右将数字和算符排入，当队尾出现：“符号操作数操作数”的组合时，排出，将符号还原后放回队列中，整体作为一个操作数（视情况加括号）

 

已知入栈序列，求可能出栈序列：

先用公式法求数量，再枚举。

 

 

 

 

 

KMP算法求一般NEXT数组、改进NEXT数组：
因为下标从0开始，因此对一般NEXT数组的求法给出如下方法：首先，出于对主串指针当前所指元素与子串第一个元素相失配则无法回溯配对，因此必须让主串指针前进的考虑，定义NEXT[0]=-1。在此基础上，对于NEXT[i]的元素，考虑：i之前（不包含i）的部分子串的前缀（不包含最后一个元素）和后缀（不包含第一个元素）的同向公共部分（从左到右比较）的长度大小。

改进NEXT数组求法：在一般NEXT数组的基础上，重新考察NEXT[i]的元素（i ! = 0），考虑：如果NEXT[i]对应j，且p[i] = p[j]，则令NEXT[i] = NEXT[p[j]] = NEXT[NEXT[i]]；反之，维持不变。通过确认和设置失配元素和回溯元素不等，这项操作有效地防止了无效回溯。

 

二叉排序树：

画法：按照题目给出的顺序依次插入结点，具体做法是按照结点值的大小插入结点，小于根节点进入左子树；大于根节点进入右子树。

检查措施：将画好的二叉排序树计算中序序列，如果是升序序列，则说明建立成功

 

求折半查找法的等概率查找平均查找长度

先转换成对应的二叉树，再对“深度*个数”求和再除个数。

注意：每个出度不为2的结点都要存在左右的失败结点，查找失败计算的是失败节点的查找长度，但是每一个失败节点的深度需要向上提一层，最后求平均除以的数量也是失败结点的数量

某序线索化的穿线二叉树（又叫线索二叉树）：

画法：首先写出对应序列，返回二叉树，如果某结点出度不为2，则通过连接序列中对应相邻的结点补全，如果没有没有对应相邻结点，则指向NULL

 

森林、树与二叉树之间的转化：

【【数据结构】树、二叉树、森林直接的转换】【数据结构】树、二叉树、森林直接的转换_哔哩哔哩_bilibili

 

求最小生成树：

Prim Algorithm: 纳入顶点。纳入新顶点的代价最小，直到包括所有顶点。

Kruskal Algorithm: 纳入边。纳入新边的权值最小且原本这两个结点无联通关系，直到联通所有顶点。

 

 

AOE网求关键路径：

所有事件最早发生时间（源点为0）：多线模拟中所需最大时间（木桶效应）、所有事件最晚发生时间：最大偷懒时间、所有活动的最早发生时间（事件最早传递）、所有活动的最晚发生时间（最晚时间传递）

关键路径求法：求事件最早发生事件每次求最大值舍弃路径，最后剩下的唯一路径就是关键路径。或者事件最早发生时间和最晚发生 时间相等的事件在路径上。

 

 

最短路径算法（Dijkstra）（一点到任意各点，且各点数均为正数）：

1. 每次从未标记的结点中选择距离出发点最近的结点，标记，收录到最优路径集合中
2. 计算刚加入结点A的临近结点B的距离（不含标记的结点），若（结点A距离+结点A到B的边长）< 结点B的距离，则更新结点B的距离和前面点。

示例：

注意：1.出发点距离出发点为0 2.每次判断完成后，从未标记结点中找距离最小的收入最优路径中，并尝试更新临近结点 3.全部标记完毕，停止，回溯路径

 

Floyd算法（求任意两点间最小距离）

画出有向图的邻接矩阵（此时是邻接关系，不能有中转）。假设有n个节点，则对矩阵进行n次中转迭代。（注意：进行节点n的中转迭代时，n行、n列及对角线元素不参与迭代，可从前一个矩阵直接继承）中转迭代：假设进行节点n的迭代，考察元素ab时，比较当前元素值和an + nb元素值，取较小值。

 

平衡二叉树（有排序的性质）算法：

求法：

术语：

平衡因子：左子树高度-右子树高度，绝对值不超过1

LL LR RL RR：前面的字母代表加入结点处于最低不平衡结点的左右子树，后面的字母代表加入结点是某结点的左右孩子，表征位置，不表征修改方案。

注意：插入顺序也会影响平衡二叉树唯一性，因此只有结点和插入顺序都是固定的情况下，平衡二叉树才是唯一的

 

AOV网络拓扑排序：

图、邻接表、邻接矩阵的DFS、BFS：

访问的优先次序：从小到大

DFS的访问特点：一访问到临近结点就立刻下潜访问下一级临近结点，除非访问失败否则不回退，一旦回退就尝试访问其它临近结点。逻辑结构：栈。

BFS的访问特点：要完全访问当前层级所有的临近结点再从小的结点下潜一级,访问完之后回退到次大结点下潜。逻辑结构：队列。

 

 

邻接表（编号均不是必须）：

 

邻接多重表：

孩子兄弟表示法：左孩子、右兄弟

 

十字链表：

 

 

构造散列表：

先画空间

对每个数据根据散列函数取模

线性探测法：（不给）从正常位置开始向后找（看成循环数组）

二次探测法：（一个函数）向前1、向后1、向前4、向后4....（看成循环数组）

双散列法：（会给两个函数）第一次取模是地址，第二次取模是步长（看成循环数组）

 

一维哈希表的成功查找平均长度：分母是元素数目，分子是对各个元素进行查找时所需要的次数之和（进行元素查找时，不是盲目从第一个空间找，也不是从第一个非空空间找，而是根据哈希函数有判断得开始找）

一维哈希表得失败查找平均长度：分母是由哈希函数决定的：例如字母表数值/2下取整的取值为0-13，则查找失败得起始点为0-13。分子是到空指针或者最后一个元素元素的查找次数。

辨析：成功查找的起始点是可查元素对应的下标，可重复，数量由元素决定；失败查找的起始点是有效下标，不可重复，数量由哈希函数决定。

 

顺序表最后一个元素的地址（a为首元素地址，i为元素个数，m为元素的长度）：

 

循环队列：   

判队满：(r+1)%max == f

求队长：(r-f+max)%max

增数据：r=(r+1)%max

 

二叉树小结论记忆：

（二叉树都满足，关于度的结论）n2-n0=1（记忆：n0大）

（满二叉树的节点个数结论）高度log2(n)的下取整+1、第k层的节点个数pow(2,k-1)、总的节点个数pow(2,h)+1

 

图论小结论记忆：

对于无向图，所有顶点的度数之和等于图的边数的两倍（算两次）

对于有向图，所有顶点的入读之和等于所有顶点的出度之和的2倍（有始有终）

排序：

算法的时间复杂度记忆：

插帽龟很稳，喜欢选帽插，插完就慌了

插帽龟很稳：直接插入，冒泡排序，归并排序很稳定

喜欢选帽插，插完就慌了：直接选择排序，冒泡排序，直接插入排序的时间复杂度为n方

快归队，n佬：快速排序，归并排序，堆排序的时间复杂度是nlog2n