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

哈夫曼树左边比右边小吗_二叉树根节点高度是1还是0数据结构(应试)一、树1.共性(1)树、二叉树、森林互转①遍历树的先遍=森林的先遍=二叉的先遍;树的后遍=森林的中遍=二叉的中遍(三个的先(前)遍一致,森林和二叉树的遍历顺序相同)2.只有先序和中序能确定一棵树3.前序序列 和 中

数据结构(应试)   一、树   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.左右孩子数学表达式:
i,2i+1,2i+2 (0开始);
i,2i,2i+1 (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树   
哈夫曼树左边比右边小吗_二叉树根节点高度是1还是0
哈夫曼树左边比右边小吗_二叉树根节点高度是1还是0B树 见图理解   1.又叫多路平衡查找树   2.阶:B树所允许
MAX 孩子个数称为B树的阶   3.“上限”:每个结点至多有M棵子树/M-1个关键字   “下限”:Ⅰ根结点下限为1关键字;Ⅱ其他所有非叶结点至少有
\left[ M/2\right]_{取上} -1关键字   4.特点:叶结点无关键字;叶结点代表的是查找失败结点(与B+区分)   ⑧B+树   
哈夫曼树左边比右边小吗_二叉树根节点高度是1还是0
哈夫曼树左边比右边小吗_二叉树根节点高度是1还是0B+树 见图理解   1.B+树的产生来源于OS的文件索引和数据库索引   2.B+关键字和分支对应关系不同于B树:B+树叶结点包含了所有关键字,并且相连,可以顺序比较   3.特点:Ⅰ叶结点之间通过指针链接;Ⅱ查找某关键字总是要查到叶;Ⅲ插入新关键字最终位于叶结点中   ⑨哈夫曼树   1.哈夫曼树及其子树不一定都遵守左0右1规定,甚至在不同子树可以左右横跳;   2.WPL=该树所有非叶结点的权值和=
\sum_{}^{}{} 每个叶结点的权值*该叶节点到根结点的距离;   3.编码   Ⅰ哈夫曼编码集、定长编码集
哈夫曼树左边比右边小吗_二叉树根节点高度是1还是0
哈夫曼树左边比右边小吗_二叉树根节点高度是1还是0哈夫曼
哈夫曼树左边比右边小吗_二叉树根节点高度是1还是0
哈夫曼树左边比右边小吗_二叉树根节点高度是1还是0定长   Ⅱ前缀编码:对字符集进行编码时,要求任一字符的编码都不是其他字符的编码前缀   4.如果是二叉以上,需要添加虚结点(权值为0),变成严格N叉树(不是严格N叉完全树)   5.求带权路径题用   ⑩堆   1.堆是一棵完全二叉树   2.大根堆:根≥孩子;小根堆:根≤孩子   3.采用一维数组存储   并查集   
哈夫曼树左边比右边小吗_二叉树根节点高度是1还是0
哈夫曼树左边比右边小吗_二叉树根节点高度是1还是0   红黑树   左根右,根叶黑,不红红,黑路同   是一棵BST树;   根结点和失败的叶子结点一定是黑结点;   在任何一条查找路径上,不可能出现两个连续的红色结点;   从任何一个结点出发,达到它下面任何一个失败结点,所经过的黑色结点数是相同的;   二、图   (1)AOE网   ①边是活动,点是事件;   ②关键路径:权值之和最大的路径;(边数最长的,不是边数最多的路径,不唯一)   (当所有关键路径的活动同时减少时,才能缩短工时)   ③活动的时间余量:结束顶点最迟的开始时间-开始顶点的最早开始时间-该活动的持续时间;   ④最早开始事件、最迟开始时间   (2)拓扑   1.拓扑序列:每次从图中删去一个入度为0的结点移入拓扑序列中,并将该结点出发的所有边删去,重复这一过程直到所有结点都进入拓扑序列,拓扑序列不一定唯一;   2.拓扑排序:找寻无入度的结点,输出并删除此结点以及所有引出的边。循环以上步骤直到完成   (换个角度看,完成拓扑排序的过程就是删除所有结点及所有边的过程)   (3)最小生成树   ①最小生成树:拥有最小代价   ②最小生成树形不唯一,因为可能存在权值相同的边   1.Kruskal(克鲁斯卡尔)算法   ①不给起始顶点,直接不断寻找最短路径的边,但不产生环;   ②过程中有可能不连通;   2.Prim(普里姆)算法   (4)最短路径   2.Dijkstra算法   ①他要给定一个顶点,然后从该结点开始选最短路径,后面是从点集各点开始选;   ②始终联通   (5)有向图、无向图   1.无向图   ①联通:从任意一顶点都有路径到其他任何顶点(不是闭环之意)   ②完全图:从任何一点都有边到其他任何边   ③简单图:图没有重复的边,也没有起点和终点相同的边。   
哈夫曼树左边比右边小吗_二叉树根节点高度是1还是0
哈夫曼树左边比右边小吗_二叉树根节点高度是1还是0截用出自王道的图   边最多的非联通情况:独立一个点   ④边数*2=各顶点度数之和(边数固定,要度数最大,即要点数最少)   2.有向图   ①强连通:无向图看作有向图
哈夫曼树左边比右边小吗_二叉树根节点高度是1还是0
哈夫曼树左边比右边小吗_二叉树根节点高度是1还是0截用出自王道的图   ②边最多的非强联通情况:其他点能到他,它不能到其他结点   (6)搜索   ①深度搜索;②广度搜索   (搜索就是遍历,每个素都要出现;一次搜索只会有一个搜索序列)   三、排序算法   (1)内部排序   
哈夫曼树左边比右边小吗_二叉树根节点高度是1还是0
哈夫曼树左边比右边小吗_二叉树根节点高度是1还是0忘了是哪的图了   数据规模小时选择:
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)三对角矩阵
哈夫曼树左边比右边小吗_二叉树根节点高度是1还是0
哈夫曼树左边比右边小吗_二叉树根节点高度是1还是0知道长什么样就行   五、散列表(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….开始看   十、大题   写思路、写代码、写复杂度、写结构体   结构体:   步长一致、   快排、   ①左小右大;②每一趟确定一个素位置。   原地逆置链表——头插法

2024最新激活全家桶教程,稳定运行到2099年,请移步至置顶文章:https://sigusoft.com/99576.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请联系我们举报,一经查实,本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处:https://sigusoft.com/47125.html

(0)
上一篇 2024年 9月 4日
下一篇 2024年 9月 4日

相关推荐

关注微信