一、线性表查找算法

1.顺序查找

　　•顺序查找无视待查表的有序与否。

2.折半查找

　　•折半查找只能用于顺序存储的线性表。
　　•表的各个元素在判定树中所在的树高就是其比较次数。对于失败情况所在的叶节点，其比较次数为其所在树高-1。判定树高度计算式与完全二叉树一致——里上外下。
　　•求ASL：画判定树，然后利用ASL定义计算。
　　•画判定树：别像个乌龟一样脑海中模拟一遍折半查找才画完树，用简便方法——逐个往树上添加结点，若是mid = (l + r)/2，要求使判定树中的每个子树的左子树结点数=右子树结点数，或左子树结点数+1=右子树结点数（因为当l与r之间有奇数个表项，mid算出来就是中间那个，其左右子树结点相等；当l与r之间有偶数个表项，mid的左子树就会比右子树少一个结点）。最后画完时，为树中原有的每个空链域添加一个叶结点表示失败情况。

3.分块查找/索引顺序查找

　　•求ASL：
　　　-通过定义求：每一个表项的查找次数 = 其所在块在索引表的位置 + 其在块中的位置。通过定义求和所有块的所有表项即可（很麻烦）。
　　　-简便方法：ASL = 索引表的ASL + 单个块的ASL。索引表的ASL和单个块的ASL由定义求出。

4.散列表（哈希表）

　　•求ASL：
　　•开放寻址解决冲突的散列表的相邻地址不一定存储同义词，是交错排列的。
　　•链地址法（拉链法）不可能造成聚集现象。（聚集——多个不同初地址关键字抢夺同一个地址进行插入）
　　•散列表的ASL或时间复杂度与装填因子直接相关，与不直接依赖于关键字数或散列表容量。

二、树形查找

1.二叉排序树（BST, Binary Search Tree）

　　1.1 查找：
　　　　——循环实现：使用游离指针T指向根结点，开始循环，当游离指针指向的结点为待找结点（找到）或游离指针指向NULL（没有该结点）时退出循环，否则让T指向该结点的左右孩子结点（待查找值小于T时让T指向T的左孩子，当待查找值大于T时让T指向T的右孩子）。
　　　　——递归实现：递归函数是递归结束函数的条件仍然是找到或当前传入的结点已经为NULL，此时返回T。递归函数是递归中间函数的条件相反，即传入的结点不为空，但又不与待找结点相同，那就分小于与大于，待找结点小于当前传入函数的结点时，返回递归调用左子树的结果，反之递归调用右子树的结果。
　　1.2 插入（递归实现）：递归函数是递归结束函数的条件是找到相同的或当前传入的结点为NULL，相同则返回错误，为NULL则修改该结点为malloc新建结点的返回值。递归函数是递归中间函数的条件相反，即传入的结点不为空，那就分小于，大于与等于，待找结点小于当前传入函数的结点时，返回递归调用左子树的结果，反之则递归调用右子树的结果。
　　1.3 构造：从头遍历关键字序列，对每一个序列调用插入操作。
　　1.4 删除：查找该结点在树中的位置。
　　　　——若该结点是叶节点，则直接删除。
　　　　——若该结点只有左子树或只有右子树，则直接让其子树的根节点代替它。
　　　　——若该结点既有左子树又有右子树，则需要让其直接前驱或直接后继复制给它。找直接前驱：中序遍历其左子树，最后遍历到的即其直接前驱。找直接后继：中序遍历其右子树，最先遍历到的即其直接后继。然后删除其直接前驱或直接后继的所处的结点（该结点肯定是叶节点或只有左子树/右子树）。
　　•中序遍历即可得到一个二叉排序树的有序序列。同一个序列的所有二叉排序树中序序列相同，且这些二叉树的中序序列就是该序列。
　　•卡特兰数 = n个结点构造的不同二叉排序树的个数 = 中序确定，不同先序序列的个数。计算式在王道书p301。

2.平衡二叉树（AVL树，取名为开发者名字首字母）

　　•平衡二叉树用于二叉排序树，使得查找时间为O(logn)，更快。
　　2.1 插入与删除：
　　　（1）直接插入，删除。
　　　（2）从插入/删除的点向上找最小不平衡树的根结点r。
　　　（3）找到该根结点r的高度最高的儿子结点x，结点x高度最高的儿子结点y。
　　　（4）分以下四种情况：
　　　　a.x,y都是左孩子——r相对x右（下）旋
　　　　b.x,y都是右孩子——r相对x左（下）旋
　　　　c.x左y右——x相对y左（下）旋，然后r相对y右（下）旋
　　　　a.x右y左——x相对y右（下）旋，然后r相对y左（下）旋
　　•ab情况是x成为最终根结点，cd情况是y成为最终根结点。
　　　（5）若是删除操作，则需要继续向上找有没有不平衡的结点。
　　•因为插入操作的插入操作本身及其后的四种平衡处理最终不会影响最小不平衡树的树高，而删除操作的删除操作本身及其后的四种平衡处理可能会使最小不平衡树的树高 - 1导致其祖先结点不平衡。
　　2.2 结点数分析
　　•平衡二叉树达到树高h的最少结点数：n(h) = n(h-2) + n(h-1) + 1，即树高为h所需的最少结点为将树高为h-1与树高为h-2的结点用一个根结点相连即可。
　　•平衡二叉树不超过树高h的最多结点数：满二叉树。
　　•平衡二叉树给定结点数的树高最低为里上外下，但可以更高。不同于完全二叉树给定结点数它就是一定是里上外下的树高。但是若从空树开始，插入序列是升序的，则产生的平衡二叉树的高度就是结点数对应的完全二叉树高度。
　　•平衡二叉树的一个结点的两个孩子平衡因子都为0，该结点平衡因子不一定为0。

3.红黑树（RBT）

　　3.1 原则：左根右，不红红，根叶黑，黑路同。
　　3.2 树形/时间复杂度分析：
　　结点黑高——结点到任意叶节点的路径上的黑结点数（不计该结点）。
　　树的黑高——根结点到任意叶节点的路径上的黑结点数（不计根结点）。
　　•树高（不算叶节点）最少为树黑高（全黑），最多为树黑高的两倍（黑红相间）——这是红黑树较平衡二叉树放宽松的地方。
　　•一个红黑树的黑高为bh，则该二叉树结点最少的情况为该树是高度为bh的满二叉树且全为黑结点，最多为该满二叉树两两黑结点之间添加红结点成为高度为2bh的满二叉树。
　　•n个结点可以生成的红黑树的最大高度为2log(n+1) （记住即可）（尝试解释：对于一颗全黑满树，挑一条路径，两两黑结点之间插入红结点以增加树高，最后得到的树就是达到该树高对结点量需求最少的树。此时树高为h，黑结点数为2^(h/2)-1，红结点数为h，该结点需求最少的树拥有2^(h/2)-1+h个结点。）
　　•AVL树与红黑树的查找，删除，插入的时间复杂度都为O(logn)。
　　3.3 插入：（直接插入+维护不红红条件）
　　a.插入结点。若插入结点将作为根结点，设为黑色，结束，否则设为红色（维护“黑路同”条件）。
　　b.看父结点是否是黑色，黑色表明不与“不红红”冲突，结束，否则进行接下来的维护操作。
　　c.看叔结点的颜色决定维护操作：
　　　c.1 叔结点为红色：叔父爷变色，将爷视为插入结点重复a步骤。
　　　c.2 叔结点为黑色或不存在：旋转+染色。旋转同AVL树，将其爷节点视为“最小不平衡子树根结点”r，将其父结点视为r的“最高子树”。染色时LL与RR旋，则父爷换色，LR与RL旋，则爷与插入结点换色。
　　•红黑树的任意子树不一定为红黑树，因为不一定满足根结点必黑的条件。
　　•红黑树的删除操作的旋转次数可能超过两次，插入操作最多两次旋转。

4.B树

　　4.1 树形/时间复杂度分析
　　给定关键字数n，树的阶数m。
　　•为了树尽量矮，规定每个非根结点至少有⌈m/2⌉个子树，至少包含⌈m/2⌉-1个关键字。根结点若不为叶节点至少有一个关键字即两个子树。
　　•树的高度最大时，根结点仅包含一个关键字，每个非根结点仅包含(⌈m/2⌉-1)个关键字，射出⌈m/2⌉条边（即充分伸高），关键字数为n = f(h) = 1+(⌈m/2⌉-1)（2+2⌈m/2⌉+2⌈m/2⌉^2+2⌈m/2⌉^3...+2⌈m/2⌉^(h-2))。那么可以求得不同h下所需要的最少关键字。题目给你关键字数numkey，仅需列出不同h需要的最少关键字数，当列出f(h0)<numkey而f(h0+1)>numkey时，numkey才够组成h0高度的B树，h0就是给定关键字下最高树高。
　　•树的高度最小时，每个结点包括根结点都有(m-1)个关键字，射出m条边（即充分长胖），关键字数n = f(h) = (m-1)(1+m+m^2+m^(h-1))，那么可以求得不同h下可容纳的最多关键字。题目给你关键字数numkey，仅需列出不同h支持的最多关键字数，当列出f(h0-1)<numkey而f(h0)>numkey时，h0才能容纳这么多的关键字，那么h0就是给定关键字下最低树高。
　　•实际做题时上述求最高最低树高的，现推太慢，太耗时间，现在花时间背公式考场少花时间。
　　•n个关键字的B数必定具有n-1个叶节点。因为n个关键字将(-∞,+∞)分为n+1个区间，落在这些区间上都是失败，落在分割点上都是成功的，失败结点即叶结点。
　　•408的叶节点指的是终端结点而非虚构NULL失败结点。

　　4.2 插入
　　将待插入关键字插入底部的终端结点，若插入后该终端结点的关键字超出m-1，即该结点目前拥有m个关键字。
　　若m为偶数，前m/2-1个留在结点，m/2号关键字插入到父结点，后面剩下的m/2个关键字新分配一个兄弟结点存储。
　　若m是奇数，则取中间的关键字插入到父结点，其左右各成一个结点。父结点若超了，则进行同样的操作。
　　ps:只要记住谁给父结点就行，m为偶数是刚好一半，m为奇数是刚好中间。

　　4.3删除
　　a.将待删除关键字直接删除。
　　b.被删关键字不在终端结点。用其直接前驱或后继代替它在该结点的位置即可。以c方式删除在终端结点中的直接前驱或后继。
　　c.被删关键字在终端结点。
　　　c.1 此时终端结点关键字数量满足最低要求⌈m/2⌉-1个，则无需任何操作。
　　　c.2 此时终端结点关键字数量低于最低要求⌈m/2⌉-1个，则需要看左右兄弟。若右兄弟够借，则父给它，兄给父。若左右兄弟都不够借，则父给它，它与一个兄弟合并。
　　d.最后若父结点是根结点且为空，抹去；不是根结点但关键字数低于限制，将该结点视为被删关键字的结点从b操作开始。

5.B+树

　　•广泛用于磁盘文件系统，磁盘的一个块即B+树的一个结点。所有记录指针都存在终端结点上，其余非终端结点存储的都是索引指针。这样使得一个磁盘块能够存更多的关键字索引，使B+树的阶达到最大。从而使B+树的高度最小，磁头在块之间转换的次数非常稳定，且最少。（B树也有概率很少，即待查关键字在树的前几行，但是由于B树每个关键字都附带一个很大的记录指针，树的阶明显小，树高明显更大，导致性能很多情况下是很差的。）

数据结构——图

一、图的性质

　　•图的路径的定义是边序列，也可是点边序列（正规定义）：以下默认路径是简单路径（点边序列中边不重合的路径）。
　　•一个图有n个结点，若边数大于n-1条，则一定有环（首尾结点相同的路径）（记住即可）。
　　•生成子图是一个包含原图所有结点的子图。
　　•无向图的连通：
　　　两结点连通，即两结点之间有路径。
　　　一个图是连通图，即任意两个结点有路径。
　　　连通分量 = 极大连通子图 = 包含尽可能多的结点与边的连通子图。
　　　无向图成为连通图所需边最少：构成一条线或一个生成树——n-1条。
　　　无向图成为连通图所需边最多：成为完全图——n(n-1)/2条。
　　•有向图的强连通：
　　　两结点强连通，即两结点可相互到达。
　　　一个图是强连通图，即任意两个结点可以相互到达。
　　　强连通分量 = 极大强连通子图 = 包含尽可能多的顶点与边的强连通子图。
　　　有向图成为强连通图所需边最少：构成一个环——n条。
　　　有向图成为强连通图所需边最多：成为完全图——n(n-1)条。
　　•对于连通图，有生成树，该生成树是包含其所有结点的极小连通子图（极小是边极少但仍保持连通）。非连通图有生成森林。
　　•连通分量只能少结点，生成树只能少边。而“极大”、“极小”是描述边的，因此极大连通子图指连通分量，包含全部顶点的极小连通子图指生成树。

二、图的存储

　　图的存储分为四种方法。
1.邻接矩阵存储
　　•矩阵元素为边，要么为1或0，要么为无穷（也可以为0）或一个数。
　　•矩阵元素（i,j)为1则表明结点i与结点j之间有边（无向图）或从结点i到结点j有弧（有向图）：
　　　因此一个顶点的入度（有向图）为j作为其自身而固定，i从1到|V|的元素中1或非0常数的个数——逐行求和。
　　　因此一个顶点的出度（有向图）为i作为其自身而固定，j从1到|V|的元素中1或非0常数的个数——逐列求和。
　　　因此一个顶点的度（有向/无向图）为上述相加——十字求和。
　　　总结：入行出列。
　　•存储的空间复杂度为O(n)。

2.邻接表存储及其改进存储方式
　　•一个图通过邻接表等所有涉及链表的存储方式进行存储的结果都不唯一——链表次序可不同（不用深究矩阵等顺序表为什么不能改变顺序）
　　•无向图的邻接表存储的边冗余了一倍——导致边链表结点的总数必定是偶数。
　　•任何需要遍历整个图的邻接表的操作（删除结点、建立表、有向图记录结点入度）的时间复杂度为O(|V|+2|E|)（无向图）或O(|V|+|E|)（有向图）即结点的个数，包括数组结点与链表节点。
　　•十字链表与邻接多重表是邻接表的变体。十字链表用于有向图，邻接多重表用于无向图。
　　　十字链表解决入度难寻的问题：从结点结构firstout域出发的边链表为其出度链表（一行）；从结点结构firstin域出发的链表为其入度链表（一列）。
　　　邻接多重表解决冗余问题：从结构结构的firstedge出发，每一个边结点都会告诉你下一个下一个边结点的位置，但你需要判断该往ilink走还是该往jlink走。

三、图的遍历

　　•两种方式——BFS、DFS。

1.BFS：Breadth-First-Search。外层函数使用循环从visted数组首结点开始调用BFS主体函数，循环条件是数组项为0（未访问）。BFS主体函数将传入该函数的结点入队，每次出队一个所有其未访问的邻接结点（需要visited数组支持）。入队时访问或出队时访问均可，访问后将结点对应visited项置1。
　　•采用邻接表进行BFS遍历，所有的操作无非就是对图的所有结点与所有边操作一次。时间复杂度为O(|V|+|E|)。
　　•采用邻接矩阵进行BFS遍历，所有的操作无非就是对图的所有结点入队的同时搜索其邻接结点。时间复杂度为O(|V|*|V|)。

2.DFS：Depth-First-Search。外层函数使用循环从visted数组首结点开始调用DFS主体函数，循环条件是数组项为0（未访问）。DFS主体函数先访问该结点，置该结点的visited项为1。然后对其每个visited为0的邻接结点递归调用该DFS主体函数。

　　•不需要visited数组的条件很苛刻。无向图不可能不需要。有向图只有树形才不需要。
　　•深度优先搜索可以判断一个图有没有环。这需要维护一个全局parent数组。考虑一个结点访问完后对其邻居判断是否已被访问，若未访问则访问。现在新增：若已访问，则看该邻接结点是否为其双亲结点（其直接遍历前驱），若不是，那么有环。
　　•BFS生成树的树高为图的两个结点距离的最大值。DFS生成树的树高至少为图的两个结点的最大值。

四、最小（代价）生成树算法

　　•适用：无向连通图
　　•应用：连通各点的道路最短修筑距离

1.prim算法：选一个结点加入树开始，维护各个结点加入树的最小代价数组lowCost与是否已经加入树的状态数组isJoin。对剩下每一个结点，调用两个循环。一个循环用于找到加入树代价最小的结点，然后将该结点加入树，将该结点对应的isJoin表项置1。第二个循环用于更新lowCost数组，具体操作是只要比较每个不在树中的结点到刚刚加入树的结点的距离是否小于现有值，小于就改。因此对于|V|-1个结点，每个结点消耗O(|V|+|V|)，总的时间复杂度就是O(|V|^2)。不依赖边。

2.kruskal算法：先将所有边抹除导致每个结点自成一个集合。每次选一条权值最小的边并将边关联的两个集合合并，且边的两个关联节点调用并查集的查操作证明不属于同一个集合，重复操作直到所有结点都在一个集合中。因此总计外层循环次数与边数|E|正相关，每个外层循环内部需调用并查集的查操作，其循环次数与树高log|E|正相关，故总的时间复杂度为O(|E|log|E|)。

　　•两个算法每次都不保证每次循环一定会选最短的未选边，prim要求新选结点在树之外，kruskal要求新选边的两边不同属一个集合。

五、最短路径算法

　　•适用：BFS算法适用无权图，Dijkstra算法适用正权图（多为有向图，但可以是无向），Floyd算法适用没有总权值为负的回路的图（多为有向图，但可以是无向）。
　　•应用：BFS与Dijkstra算法用于求单源最短路径；Floyd算法直接给出任意两点的最短路径。

1.BFS算法：只需修改BFS主体函数。函数一开始就初始化路径长度数组dist除了源为0其余为无穷，每个结点i出队后将其所有邻接结点j入队时将每个邻接结点j的路径长度设置为该出队结点i的路径长度+1（dist[j] = dist[i] + 1）。

2.Dijkstra算法：基于贪心算法。使用final数组表明各结点是否已找到最短路径=是否已经走过，使用dist数组存储各结点到源点的最短路径，使用path数组记录每个结点到源点路径的第一前驱。

　　a.首先初始化dist为各结点到源点的边的权值，没有边则为∞。若各结点与源点有边，path为源点所在数组下标，否则为-1。
　　b.然后，挑没走过的（final为0）且距离最短(dist最小)的路走，走完后所处的点到源点的最短路径就定了（不可能绕到其他点再回来会比此路径更短）。将目前所处的点的final置1。
　　c.最后看看从这个点出发到没有走过的邻接点（final为0）是否会更近，更近则更新dist数组与path数组中该临界点所在的项。
　　d.重复bc直到走完全部结点或final值都为1。

　　•时间复杂度分析：总共要走|V|-1个结点，每走到一个结点处，要使用循环遍历其射出的弧修改dist数组与path数组，循环次数取决于该结点的射出的弧数|E|（邻接表）或总结点数|V|（邻接矩阵）。接下来还要一个循环遍历dist数组找到没走过的最小项。因此时间复杂度为O((|V|-1)x(|V|+|E|))或O((|V|-1)x(|V|+|V|))，但化简后都是O(|V|x|V|)。

3.Floyd算法：基于动态规划。采用一个方阵A，逐步以各顶点作为中转迭代A。

　　a.首先初始化一个nxn的矩阵，每个矩阵元素A(i)(j)为结点i到结点j的距离。
　　b.以k号结点作为中转(k=0,1,2...n-1)，遍历矩阵，若结点i到结点k再到结点j的距离较原A(i)(j)小(A(i)(k)+A(k)(j) < A(i)(j))，则将A(i)(j)置为A(i)(k)+A(k)(j)。

　　•时间复杂度分析：显而易见，O(|V|x|V|x|V|)。

六、AOV网扩扑排序、AOE网关键路径算法

　　•适用：有向无环图。AOV网=有向无环图，AOE网还要求只有一个源点，只有一个汇点。

1.AOV网拓扑排序——标准法：假设已经准备好indegree数组存储每个结点的度
　　a.初始化一个栈或队列，将原所有度为0的结点如栈，初始化已经输出的结点数count为0，初始化print数组记录先后。
　　b.开始循环，循环条件为栈非空。每次循环出栈一个结点并将该结点存储进print数组最前面没被存储的位置。将该结点所有射出的弧指向的结点的度-1，遍历该结点所有射出的弧指向的结点，若发现度为0的结点，压入栈中。
　　c.最后发现count小于图的结点数，则说明有回路（回路导致没有结点度为0），输出失败信息，则输出成功信息。
　　•排序算法若给的是outdegree则得到是逆拓扑序列。
　　•若求一个AOV网的全部拓扑序列，则需要注意的是存储空间（队列或栈或别的）中有多个结点，那么出队的顺序是任意的。做题时牢牢根据算法，每个步骤写成“X出XXX...入”，或“X出”（没有入的）。每次出的时候脑海中把相应边抹除。参考王道课后题p244 16题，慢下心来。
　　•选择题问谁是给定图的拓扑序列直接从选项入手，列出所有扩扑序列需要耗费大量时间。从前至后，删除每个结点与其边，若有个结点删除时发现其前驱没有被删，就错。
　　•一个有向图有拓扑序列与该有向图没有环与该有向图可以作为AOV网三者等价。
　　•有向图有有序扩扑序列可以推出有向图的邻接矩阵为三角阵（因为有序拓扑序列任两个结点排在前面必定编号小，而扩扑序列只有排在前面的指向排在后面的弧，没有排在后面的指向排在前面的弧，则所有弧都是小编号结点指向大编号结点，则该图的邻接矩阵为三角阵）。有向图的邻接矩阵是个三角阵，可以推出该有向图必定无环，拓扑序列必定存在。

2.AOV网拓扑排序——DFS法：假设已经给出一个度为0的点
　　从该度为0的结点开始，调用DFS函数。函数主体先递归访问其所有未被访问的邻接，然后再将其自身添加进一个数组前面。如此，得到的数组的顺序就是先最后的工程，最后才是一开始先完成的工程。最后将数组倒置即为扩扑序列。
　　•若最后不倒置则得到的是逆扩扑序列。

3.AOE网关键路径
　　（结点代表的）事件的最早发生时间：当每个活动能做就做时所有前面发生的最晚结束的活动结束的时候。（不能再早了，不然就抢先了）。
　　（结点代表的）事件的最迟发生时间：当每个活动能拖就拖时所有后面发生的最早开始的活动开始的时候。（不能再晚了，不然就来不及了）。
　　（弧代表的）活动的最早开始事件=弧的源头结点的最早发生时间。
　　（弧代表的）活动的最晚开始事件=弧的指向结点的最晚发生时间-该活动耗时。
　　•关键路径上各个结点发生时间固定。最早发生时间=最晚发生时间。
　　•关键路径算法：
　　　1.先对图进行扩扑排序与逆拓扑排序。
　　　2.利用扩扑序列，从源点开始，求得每个结点的最早发生时间。
　　　3.利用逆拓扑序列，从汇点开始，求得每个结点的最晚发生时间。
　　　4.最早与最晚发生时间相等的结点构成关键路径（可能多条）。
　　•AOE网关键路径算法能判断图是否有回路全依赖扩扑排序的count。
　　•选择题求一个AOV网关键路径时用瞪眼法。

数据结构——树

一、树、二叉树性质

　　一般这种题会问你结点数、高度、空指针域等问题
　　需牢记：
　　　1.二叉树：n0 + n1 + n2 = n1 + 2*n2 + 1 = n
　　　　这个方程最重要！！！可以解决度、边、结点数直接关系的问题。题中出现度、结点直接用此公式就对了
　　　2.二叉树：0 = 2 + 1，即叶节点数 = 度为2的结点数 + 1（由1的前两个组成方程推导出来）
　　　3.二叉树：2n个孩子指针，只有n-1个结点可以作为孩子被指，故有2n-(n-1)=n+1个空指针（空链域）
　　　4.完全/满二叉树：一行的起始结点号 = 该行可容纳的结点数 = 2^(n-1)；一行的末尾结点号 = 整棵树的结点数 = 2^n-1
　　　5.完全二叉树：高度公式里上外下（+1在对数里面就向上取整，外面就向下取整）
　　　6.完全二叉树的叶节点只有可能出现在倒数两行，一个完全二叉树的叶节点要么处于上面那行，要么出现在下面那行

二、二叉树的遍历

　　前序遍历，根左右，对于一个结点而言，先访问它，再访问其左子树，再访问其右子树。最后被访问到的是该结点右子树的最右下的叶节点。最先访问到的是结点本身。
　　中序遍历，左根右，对于一个结点而言，先访问其左子树，再访问它，再访问其右子树。最后被访问到的是该结点右子树的最右下转折处的结点。最先访问到的是其左子树最左下转折处的结点。
　　后序遍历，左右根，对于一个结点而言，先访问其左子树，再访问其右子树，再访问它。最后被访问到的是结点本身。最先访问到的是该结点左子树最左下的叶节点。
　　层次遍历，利用队列，从根节点进入队列开始，每次出一个，并将其孩子添加到队列中知道队列为空。
　　四个遍历一定要烂熟于心。

三、创造线索二叉树

　　介绍：线索二叉树的创造依赖于前、中、后遍历序列。结点的左孩子为空，则设置左孩子指针为其前驱的位置并置ltag = 1；结点的右孩子为空，则设置右孩子指针为其后继的位置并置rtag = 1。ltag与rtag表明了该结点的指针是否为线索。
　　将一棵二叉树改为线索二叉树：需要对二叉树遍历，而遍历分为先序中序与后序。遍历的种类决定了线索二叉树的种类。
　　先序：先设置当前结点的前驱（空左孩子）再设置pre的后继（空右孩子），再递归到左孩子，最后递归到右孩子。
　　中序：先递归到左孩子，再设置当前结点的前驱（空左孩子）再设置pre的后继（空右孩子），最后递归到右孩子。
　　后序：先递归到左孩子，再递归到右孩子，最后设置当前结点的前驱（空左孩子）再设置pre的后继（空右孩子）。
　　特别注意：先序遍历创造线索二叉树中，递归到左孩子小心此时的左孩子指针可能不指向其左孩子而指向其前驱。

四、遍历线索二叉树

　　方法：线索二叉树的遍历需由该线索二叉树的种类决定。但思想是一致的：多米诺骨牌——找到序列的首结点，从序列的首结点出发，想尽办法找到下一个结点。
　　先序：
　　　　找到序列首结点：即一个序列的根节点
　　　　找到下一个结点的办法：后继线索存在则用之。否则（右孩子存在），若左孩子不存 　　　　　　在，则下一个结点为右孩子；若左孩子存在，则下一个结点为左孩子。
　　中序：
　　　　找到序列首结点：最左下转折处的结点
　　　　找到下一个结点的办法：后继线索存在则用之。否则（右孩子存在），找到右子树序　　　
　　　　　　列首结点。
　　后序：
　　　　找到序列首结点：最左下的叶节点
　　　　找到下一个结点的办法：后继线索存在则用之。否则，若其为左孩子且其双亲右孩子
　　　　　　存在，找到其双亲右子树的最左下的叶结点；若其为左孩子且其双亲右孩子不存
　　　　　　在，则其双亲就是后继；若其为双亲的右孩子，则其双亲同样为后继。
　　　　可见后序线索二叉树找后继需要找双亲结点，需要借助三叉链表或栈。

五、树、森林转二叉树

　　每个结点的左右指针存储左孩子右兄弟。相当于整个树/森林顺时针旋转了45度。转成后的二叉树左孩子空指针域都是原来树的叶节点才有的；右孩子空指针域每个非叶节点一个（在非叶节点的最后一个孩子处），若是森林最后一棵树的根节点又有一个。

六、哈夫曼树

　　若所有叶节点表示一种信息，叶节点的权为信息使用的频度。整棵树的带权路径长度评价了用二进制对信息进行编码的代价。而哈夫曼树做到了使这种代价最小。
　　构造哈夫曼树（最重要）：若由n个带权结点需要生成哈夫曼树，则将他们所有视为一棵棵单节点树。每次取权值最小的合并，新树权值为合并前两棵树的权值之和。
　　从构造过程可以看出：每次两棵树合并，左右位置可互换，因此每次合并有两种选择。故哈夫曼树不是唯一的。
　　每次合并树的数量都少1，初始n棵，最后1棵，故合并了n-1次，产生了n-1个非叶节点，最后的树总计n-1+n=2n-1个结点。
　　补充1：还可以为三进制、四进制...创造哈夫曼树，此时哈夫曼树就不再是二叉树了。整棵树的度要么为进制数，要么为0。
　　补充2：哈夫曼树的带权路径长度的两种计算方法：①所有叶节点带权路径长度之和（原始定义）；②所有分支结点（非根节点）权值之和（记住即可，没讲为什么）

七、并查集

　　能够合并与查找结点所在集合的数据结构称为并查集。采用顺序存储的双亲表示法表示的森林（不一定是二叉树森林）来实现。森林中每一棵树就代表一个集合。
　　查找：查找一个元素所在的集合，就是查找其所在树的根节点。采用循环访问其双亲结点的索引知道-1（根节点处的索引）即可。另外可以在每次循环结束（找到后）进行一些步骤来优化。具体措施是再走一遍循环，将每一个访问到的结点的索引都改成根节点的索引，即直接称为根节点的孩子，以此减小树高。
　　合并：合并两棵树。可能需要利用查找找到根节点的索引。直接将一个根节点的数组内容（双亲索引）从-1改为另一个根节点的索引即可。更优化的方法是，让所有根节点的数组内容不再存储-1，而是树的结点个数，在合并的时候使用条件语句保证小树合并到大树，以此减小树高。

数据结构——串

本文主要介绍串的核心算法——KMP算法。
前提：假设字符串起始索引为1。主串长度为m，索引为i；模式串长度为n，索引为j。

一、如何计算主体函数（已知next数组）的时间复杂度

KMP算法无非就两个部分：i与j共同增加1；i不动，j减少（即j = next[j]）。
时间复杂度的求解需要知道上述两个运行次数为无穷大的语句相加的结果。

1.i与j共同加1

这种情况是遇到相匹配或模式串第1位于主串第i位不匹配导致的。
i从1增长到主串结尾m，因此该语句最多执行m次。

2.i不动，j减少

这种情况是遇到模式串的第j位与主串的i位不匹配导致的。
j每次减少的量若最少会导致操作步骤的最多。因此j每次减少1，操作步骤会最多。
j的每次减一消耗的是上述的i加一操作。
因此j减1最多的执行次数与操作一一致，m次

总结

因此俩个操作之和就是2m次。时间复杂度为其基本同阶无穷大，即O(m)。

二、next与nextval数组的手算求法

1.next数组

首项与第二项填0与1。后面每一项找到当前项前面的字符串的最长相同前后缀的前缀，该前缀的后面一位的索引即该该项的next值。

2.nextval数组

写出next数组。接下来开始nextval手算。
第一项填0，后面每一项比对该项与next[该项下标]对应的字符是否相等，
若不相等，直接填next；若相等，填nextval[next[该项下标]]