哈夫曼树左边比右边小吗_二叉树根节点高度是1还是0

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

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

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

忘了是哪的图了 　　数据规模小时选择：
　　数据规模大时选择：
　　1.插入 　　①直接插入 　　a.待排序的素看作一个有序表和无序表; 　　b.适合初始序列大部分有序的（有序时相当于分界线一位一位相后移）；适合素较少的序列； 　　c.空间为
，稳定； 　　②希尔排序 　　a.依次序列间隔分组排序 　　b.增量： 　　eg：增量为2，abcdefg→ aceg排序；bdf排序。 　　（一般增量为：长度/2） 　　c.按趟来，每趟增量可以不一样； 　　d.组内排序是按直接插入排序； 　　2.交换 　　①冒泡（气泡） 　　②快速排序 　　a.选基准素，左边比他大，右边比它小，再对左、右边进行快排； 　　b.适合初始序列基本无序；适合素较多的序列； 　　c.空间
、不稳定； 　　d.一趟能确定一个素最终位置；（所以问第几趟素位置时，把序列自己排序去比） 　　3.选择 　　选择排序的比较次数与初始序列无关 　　①简单选择： 　　选最值放在第一个（二者交换）； 　　②堆排序： 　　a.与简单选择一样，都是选最值，这个用堆排； 　　b.数据存储方式只能用顺序存储； 　　c.建堆：找完全二叉树中的最后一个非叶结点，即
（n为总结点个数）；指针往上移。 　　d.插入:先放在n+1的位置（也就是序列n的位置）；往上找他的所有根结点，按气泡排序调整； 　　e.删除：删除位置用最后一位补上，重新建堆； 　　（调整时，子树，先比左右孩子，再将那个突出的孩子与父亲比） 　　f.一趟能确定一个素最终位置 　　4.基数排序（桶排序） 　　a.对个位数排，再对十位数排…； 　　b.基数排序的移动次数与初始排序无关 　　（2）外部排序 　　数据规模达到内存无法放下需选择； 　　1.归并选择 　　多个组排序；归并排序的比较次数与初始排序无关 　　（3）存储类型 　　顺序存储还是链式存储，看算法需不需要随机存取特性（就是“忽然”调用某个数据素） 　　希尔、堆需要考虑 　　四、矩阵 　　（1）压缩稀疏矩阵 　　1.存储结构： 　　①三组 　　a.M行数、M列数、非0个数 　　b.存储行、列、值 　　②十字链表 　　a.按“按行查找矩阵点”和“按列查找矩阵点”的结合； 　　b.三组进化版 　　（2）邻接矩阵 　　①构建
表，存储数据，二阶数组; 　　②如果它为非对称矩阵，说明图是有向图； 　　③空间
　　④邻接表 空间：
; 　　⑤稀疏矩阵选邻接表比邻接矩阵好 　　（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长度 　　①判队空 　　考虑只有一个素的情况，也是腾出一个素位置的原因 　　队头=队尾 　　九、折半查找 　　折半查找成功/不成功关键字比较次数最多为
　　偶数时，选左选右都行 　　九、其他 　　1.不要命题老头问什么，你就只往哪方面想； 　　2.验证答案思想，ABCD一个个验证，从答案出发（问题→选项→问题→答案） 　　3.赋值验证答案（问题→对选项赋值→答案） 　　4.题目强调C语言中的xxx，回忆自己敲代码怎么写这个的（eg：C语言中的数组→下标从0开始） 　　5.当题目问到数学规律那种题时，问第n种情况，从1、2、3….开始看 　　十、大题 　　写思路、写代码、写复杂度、写结构体 　　结构体： 　　步长一致、 　　快排、 　　①左小右大；②每一趟确定一个素位置。 　　原地逆置链表——头插法