哈夫曼树平均编码长度怎么求_哈夫曼树编码平均码长

数据结构（应试）
　　一、树

　　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….开始看

　　十、大题

　　写思路、写代码、写复杂度、写结构体

　　结构体：

　　步长一致、

　　快排、

　　①左小右大；②每一趟确定一个元素位置。

　　原地逆置链表——头插法