二叉排序树怎样得到递增序列_邻接表的深度优先遍历

数据结构（应试）　　一、树　　1.共性　　（1）树、二叉树、森林互转　　①遍历树的先遍=森林的先遍=二叉的先遍；　　树的后遍=森林的中遍=二叉的中遍　　（三个的先（前）遍一致，森林和二叉树的遍历顺序相同）　　2.只有先序和中序能确定一棵树　　3.前序序列和中序序列关系：以前序序列入栈，那么中序序列就是出栈序列　　（n个素进栈，出栈序列个数为
$\frac{1}{1+n}C_{2n}^{n}$ ）　　②怎么转二叉　　1.一句话：左孩子，右兄弟　　2.森林/树叶子结点没有孩子，意味着：二叉左孩子为空的结点数=森林/树的叶结点个数　　二叉右孩子为空的结点数=树的子结点中最右的结点数+根结点（森林就没有根结点）=分支结点+根结点　　3.二叉链表存放树/森林，又名左孩子右兄弟表示法　　（2）易错点　　1.叶结点可不是最下面一层的结点（爱与完全二叉树考）；　　2.树的边界值/极值问题，题给条件“任意一棵二叉树”，要考虑“最坏情况”；　　3.混淆堆和BST的大小判定；　　4.注意”分支结点“这个说法，排除了叶子结点；　　2.个性　　①二叉树　　1.度的关系：
$N_{0}=N_{2}+1$ ,
$N_{1}=1 或 0$ 　　2.左右孩子数学表达式：
（0开始）；
（1开始）　　②满二叉树　　1.叶结点=非叶+1 　　2.满足：完全二叉树+所有叶结点都在最后一层+非叶结点都有2个结点　　③二叉排序树（BST）　　1.又叫二叉搜索树　　2.左子树<根<右子树（但是
Min 结点不一定是左孩子，可能压根没有左子树）　　3.中序遍历是升序（用来判定是否为BST）　　④平衡二叉树（AVL）　　1.平衡因子：-1,0,1 　　2.一般理解为高度平衡的BST，但是！如果说他中序遍历是降序，那么有左>根>右，则不是BST 　　3.调整(这个B站搜个视频学)；插入一个素时，先放在”叶结点对的位置“ 　　⑤折半查找判定树　　1.关键字比较序列：下一个关键字会提示你上一在往哪个方向走　　（eg：23、54、44 　　54：往比23大的方向走；44：往比54小的方向走）　　2.给出序列怎么画？　　如果结点个数为奇数：取正中间结点
n/2 ；　　为偶数，取
$[n/2]_{取上}$ 或者
$[n/2]_{取下}$ 都行，但是！由于用的是同一个算法，要么都左，要么都右。（上取整突出来的是右边，向下取整突出的左边）　　⑥最佳归并树　　1.严格n叉树，属于哈夫曼树，要么度为0，要么度为n 　　2.求补充虚段个数题。一般题会告诉几路归并，多少归并段。　　eg：12路归并，120归并段　　解：设
$N_{12}$ =n，虚数段=x 　　∵度和=结点数-1，∴12n=120+n+x-1→n=(119+x)/11 　　x取最小整数2 　　（虚段：值为0的叶子结点）　　⑦B树　　

B树见图理解　　1.又叫多路平衡查找树　　2.阶：B树所允许
MAX 孩子个数称为B树的阶　　3.“上限”：每个结点至多有M棵子树/M-1个关键字　　“下限”：Ⅰ根结点下限为1关键字；Ⅱ其他所有非叶结点至少有
$\left[ M/2\right]_{取上}$ -1关键字　　4.特点：叶结点无关键字；叶结点代表的是查找失败结点（与B+区分）　　⑧B+树　　

B+树见图理解　　1.B+树的产生来源于OS的文件索引和数据库索引　　2.B+关键字和分支对应关系不同于B树：B+树叶结点包含了所有关键字，并且相连，可以顺序比较　　3.特点：Ⅰ叶结点之间通过指针链接；Ⅱ查找某关键字总是要查到叶；Ⅲ插入新关键字最终位于叶结点中　　⑨哈夫曼树　　1.哈夫曼树及其子树不一定都遵守左0右1规定，甚至在不同子树可以左右横跳；　　2.WPL=该树所有非叶结点的权值和=
$\sum_{}^{}{}$ 每个叶结点的权值*该叶节点到根结点的距离；　　3.编码　　Ⅰ哈夫曼编码集、定长编码集

哈夫曼

定长　　Ⅱ前缀编码：对字符集进行编码时，要求任一字符的编码都不是其他字符的编码前缀　　4.如果是二叉以上，需要添加虚结点（权值为0），变成严格N叉树（不是严格N叉完全树）　　5.求带权路径题用　　⑩堆　　1.堆是一棵完全二叉树　　2.大根堆：根≥孩子；小根堆：根≤孩子　　3.采用一维数组存储　　并查集　　

　　红黑树　　左根右，根叶黑，不红红，黑路同　　是一棵BST树；　　根结点和失败的叶子结点一定是黑结点；　　在任何一条查找路径上，不可能出现两个连续的红色结点；　　从任何一个结点出发，达到它下面任何一个失败结点，所经过的黑色结点数是相同的；　　二、图　　（1）AOE网　　①边是活动，点是事件；　　②关键路径：权值之和最大的路径；（边数最长的，不是边数最多的路径，不唯一）　　（当所有关键路径的活动同时减少时，才能缩短工时）　　③活动的时间余量：结束顶点最迟的开始时间-开始顶点的最早开始时间-该活动的持续时间；　　④最早开始事件、最迟开始时间　　（2）拓扑　　1.拓扑序列：每次从图中删去一个入度为0的结点移入拓扑序列中，并将该结点出发的所有边删去，重复这一过程直到所有结点都进入拓扑序列，拓扑序列不一定唯一；　　2.拓扑排序：找寻无入度的结点，输出并删除此结点以及所有引出的边。循环以上步骤直到完成　　（换个角度看，完成拓扑排序的过程就是删除所有结点及所有边的过程）　　（3）最小生成树　　①最小生成树：拥有最小代价　　②最小生成树形不唯一，因为可能存在权值相同的边　　1.Kruskal（克鲁斯卡尔）算法　　①不给起始顶点，直接不断寻找最短路径的边，但不产生环；　　②过程中有可能不连通；　　2.Prim(普里姆)算法　　（4）最短路径　　2.Dijkstra算法　　①他要给定一个顶点，然后从该结点开始选最短路径，后面是从点集各点开始选；　　②始终联通　　（5）有向图、无向图　　1.无向图　　①联通：从任意一顶点都有路径到其他任何顶点（不是闭环之意）　　②完全图：从任何一点都有边到其他任何边　　③简单图：图没有重复的边，也没有起点和终点相同的边。　　

截用出自王道的图　　边最多的非联通情况：独立一个点　　④边数*2＝各顶点度数之和（边数固定，要度数最大，即要点数最少）　　2.有向图　　①强连通：无向图看作有向图

截用出自王道的图　　②边最多的非强联通情况：其他点能到他，它不能到其他结点　　（6）搜索　　①深度搜索；②广度搜索　　（搜索就是遍历，每个素都要出现；一次搜索只会有一个搜索序列）　　三、排序算法　　（1）内部排序　　

忘了是哪的图了　　数据规模小时选择：
$O(n^{2})$ 　　数据规模大时选择：
$O(nlog_{2}^{n})$ 　　1.插入　　①直接插入　　a.待排序的素看作一个有序表和无序表; 　　b.适合初始序列大部分有序的（有序时相当于分界线一位一位相后移）；适合素较少的序列；　　c.空间为
O(1) ，稳定；　　②希尔排序　　a.依次序列间隔分组排序　　b.增量：　　eg：增量为2，abcdefg→ aceg排序；bdf排序。　　（一般增量为：长度/2）　　c.按趟来，每趟增量可以不一样；　　d.组内排序是按直接插入排序；　　2.交换　　①冒泡（气泡）　　②快速排序　　a.选基准素，左边比他大，右边比它小，再对左、右边进行快排；　　b.适合初始序列基本无序；适合素较多的序列；　　c.空间
$O(log_{2}^{n})$ 、不稳定；　　d.一趟能确定一个素最终位置；（所以问第几趟素位置时，把序列自己排序去比）　　3.选择　　选择排序的比较次数与初始序列无关　　①简单选择：　　选最值放在第一个（二者交换）；　　②堆排序：　　a.与简单选择一样，都是选最值，这个用堆排；　　b.数据存储方式只能用顺序存储；　　c.建堆：找完全二叉树中的最后一个非叶结点，即
$[n/2]_{取下}-1$ （n为总结点个数）；指针往上移。　　d.插入:先放在n+1的位置（也就是序列n的位置）；往上找他的所有根结点，按气泡排序调整；　　e.删除：删除位置用最后一位补上，重新建堆；　　（调整时，子树，先比左右孩子，再将那个突出的孩子与父亲比）　　f.一趟能确定一个素最终位置　　4.基数排序（桶排序）　　a.对个位数排，再对十位数排…；　　b.基数排序的移动次数与初始排序无关　　（2）外部排序　　数据规模达到内存无法放下需选择；　　1.归并选择　　多个组排序；归并排序的比较次数与初始排序无关　　（3）存储类型　　顺序存储还是链式存储，看算法需不需要随机存取特性（就是“忽然”调用某个数据素）　　希尔、堆需要考虑　　四、矩阵　　（1）压缩稀疏矩阵　　1.存储结构：　　①三组　　a.M行数、M列数、非0个数　　b.存储行、列、值　　②十字链表　　a.按“按行查找矩阵点”和“按列查找矩阵点”的结合；　　b.三组进化版　　（2）邻接矩阵　　①构建
$n\times m$ 表，存储数据，二阶数组; 　　②如果它为非对称矩阵，说明图是有向图；　　③空间
$O(n^{2})$ 　　④邻接表空间：
O(n+e) ; 　　⑤稀疏矩阵选邻接表比邻接矩阵好　　（3）三对角矩阵

知道长什么样就行　　五、散列表（Hash）　　1.影响散列（哈希）方法平均查找长度　　①装填因子；②散列函数；③冲突解决策略。　　2.题型H(key)=Key%m，表长为n，已存关键字数为k 　　①查找失败平均查找长度：映射到数组的所有可能位置%m 　　②查找成功平均查找长度：查找到每个关键字要的次数求和/k（每次从key%m的位置开始找）　　（无论成功失败表达式都与表长无关）　　3.散列法解决冲突（删除中）　　①开发地址法；　　②不能直接物理删除，而是对它做一个标记，记录他发生过删除，即查找到该位置还好继续查找；　　4.堆积（聚集）现象：大量连续数据背井离乡，久居人下；　　5.填的越满越容易发生冲突。　　七、KMP算法　　1.生成NEXT数组　　无脑写双0+自己理解+“右移一位”+“整体+1” 　　2.失配后：j=next[j] 　　八、堆栈　　（1）中缀/后缀表达式　　1.怎么转　　①中缀就是正常的表达式；　　②中缀转后缀要分析符号位置：(表达式)（表达式）符号；　　表达式里面再分：((表达式)（表达式）符号)（表达式）符号。　　2.中缀转后缀中的栈的使用　　①由于后缀是先数字后符合，中序正常，所以转时栈用来存运算符；　　②如果表达式有括号，根据正常括号在哪两个符号之间就放在栈里那两个符号之间位置；　　（2）循环队列　　1.一般就是要判空判满：　　告诉我们当两端都可以出入队时，　　这种题我们画图不要画一个环，而是要画一个数组（心里知道它是环，头尾相接）；　　①判队满　　画一个数组，不要把队头放在第一个位置：r队尾队头　　如果题暗示队尾与队头不是邻在一起：eg：A[M]只能放M-1个素队尾队头　　堆满一般要mod长度　　①判队空　　考虑只有一个素的情况，也是腾出一个素位置的原因　　队头=队尾　　九、折半查找　　折半查找成功/不成功关键字比较次数最多为
$[log_{2}^{n}]_{取下}+1$ 　　偶数时，选左选右都行　　九、其他　　1.不要命题老头问什么，你就只往哪方面想；　　2.验证答案思想，ABCD一个个验证，从答案出发（问题→选项→问题→答案）　　3.赋值验证答案（问题→对选项赋值→答案）　　4.题目强调C语言中的xxx，回忆自己敲代码怎么写这个的（eg：C语言中的数组→下标从0开始）　　5.当题目问到数学规律那种题时，问第n种情况，从1、2、3….开始看　　十、大题　　写思路、写代码、写复杂度、写结构体　　结构体：　　步长一致、　　快排、　　①左小右大；②每一趟确定一个素位置。　　原地逆置链表——头插法

二叉排序树怎样得到递增序列_邻接表的深度优先遍历

相关推荐