注本文为博主学习408相关知识所撰写的学习笔记内容如有雷同纯属巧合。考点1 树形推断①N ... 0*1*2*...n*1节点点数N 度之和 1②非空二叉树满足 1③度为m的树第i层上最多个节点④高度为h的满m叉树一共有个节点⑤具有n个结点的完全二叉树的高度为或⑥对完全二叉树按照层序进行编号i1,2...n:i为偶数时父节点为i/2i是父节点的左孩子i为奇数时父节点为(i-1)/2i是父节点的右孩子i的左孩子为2i或不存在i的右孩子为2i1或不存在i≤时i为分支节点i时i为叶子节点若n为奇数则每个分支节点都有左右孩子若n为偶数则in/2(最后一个分支节点)只有左孩子⑦完全二叉树中度为1的节点只可能有1个或者0个⑧树越高越细每层节点数量少越矮越胖每层节点数量多⑨完全二叉树只有最后两层可能出现叶节点典型真题2010年真题该题需要用到第①个公式即N 0*1*2*3*4*1得到公式1*102*110*320*41-(1011020)82选择选项B2016年真题该题我们分析树的节点结构可以知道树的总结点个数等于分支数加一即N分支数1在一颗树里面除了根节点以外其他节点都有分支则我们可以知道有多少个分支(边)就有多少个非根节点又因为题目给出有25个节点则根节点有25-1510个解得森林F包含树的个数为10个选择选项C。2009年真题该题给出树形结构为完全二叉树则只会出现两种树形结构又因为题目给出完全二叉树的第6层有8个节点则该完全二叉树不为满二叉树且该完全二叉树有7层因此我们可以知道前6层共有63个节点又因为第6层有8个节点则在第六层中有个节点生出了最后一层的叶子节点得到第七层有24*248个节点所以该完全二叉树一共有6348111个节点数。2011年真题该题一共有768个节点位于768之间由此可以判断该二叉树有十层在前9层中有511个结点得到第十层的叶节点有768-511257个由此可以得到第九层有129个节点有子节点则其余节点为叶节点有256-129127个节点所以得到该二叉树中叶节点的个数为127257384选择选项C。2018年真题该题给出所有叶节点均位于同一层且每个非叶节点都有2个子节点则可以知道该完全二叉树为满二叉树整颗树中只有度为2和度为0的节点假设有h层则叶节点总数为k得到h由于题目求T的节点总数即得到节点总数为2k-1。2022年真题该题问T的高度至少是多少即需要得到的是一个满三叉树的树形结构由于高度为h的m叉树一共有个节点则可以得到244个节点位于121244364之间则可以知道该三叉树前5层为满三叉树可以得到该三叉树高度至少为51层即选择选项C。2016年大题该题先提取题目中的信息我们可以知道树中只有度为0的节点和度为k的节点。第一问中T有m个非叶节点我们可以知道树中只有度为0和度为k的节点根据总结的公式可以得到等式Nk*1,因为非叶节点即度为k的节点所以得到叶节点(k-1)*m1。第二问中节点数最多即求满二叉树的情况则可以用到满m叉树的公式可以得到最多节点树为节点数最少中因为每个非叶节点都有k个孩子则根结点最少需要有k个节点根节点以下的某一个节点的孩子必须有k个孩子才能得到节点数最少的情况则可以得到除第一层有一个节点外其他每层都有k个节点得到最少的情况为1(h-1)*k。考点2 树的存储①二叉树的两种存储方式顺序存储方式注k个结点的n叉树中根结点有n*k个链域非根结点有k-1个链域链式存储方式②树的三种存储方式双亲表示法孩子表示法孩子兄弟表示法特点以一组连续的存储单元存储树的结点的双亲将每个结点的孩子视为以单链表存储的线性表n个结点又组成另一个基于顺序表的线性表对树的每个结点按照“左孩子右兄弟”的原则转换为二叉树并用二叉链表存储优点寻找双亲方便寻找孩子方便寻找孩子方便缺点寻找孩子需要遍历整个结构寻找双亲需要遍历整个结构寻找双亲需要遍历整个结构典型真题2020年真题该题给出采用顺序存储结构保存顺序存储结构空结点也需要分配存储单元 题目给出对于任意一颗高度为5的二叉树即最后一个结点的位置可以在第五层的任意位置题目需要求至少需要的存储单元即最后一个结点落在第五层的最后的位置上则需要31个存储单元选择A选项。考点3 唯一确定一颗二叉树中序任意一种遍历序列一颗确定的二叉树典型真题2011年真题该题我们可以通过中序前序的方式得到每一个选项的树形结构由于前序序列为:1234若中序序列为C选项的3241则可以得到的树形结构的后序序列为3421与题干不符所以选择选项C。2012年真题考点4 遍历一个线索二叉树①二叉树的四种遍历先序遍历void PreOrderTraverse(BiTree T) { if(T) { cout T-data; PreOrderTraverse(T-lchild); PreOrderTraverse(T-rchild); } }遍历过程中每个结点都会经过3次第一次经过时访问并输出它然后开始遍历左子树第二次经过是因为它的左子树已遍历完毕第三次经过是因为它的右子树已遍历完毕。中序遍历void InOrderTraverse(BiTree T) { if(T){ InOrderTraverse(T-lchild); coutT-data; InOrderTraverse(T-rchild);} }遍历过程中每个结点都会经过3次第一次经过是为了能访问到它的左子树第二次经过是因为左子树已遍历完毕此时访问并输出它然后开始遍历右子树第三次经过是因为它的右子树已遍历完成。后序遍历void PostOrderTraverse(BiTree T) { if(T){ PostOrderTraverse(T-lchild); PostOrderTraverse(T-rchild); coutT-data;} }遍历过程中每个结点都会经过3次第一次经过是为了能访问到它的左子树第二次经过是为了能访问它的右子树第三次经过是因为左右子树已遍历完毕此时访问并输出它。层序遍历//借助队列的层序遍历 void LeavelOrder(BiTree T){ InitQueue(Q); BiTree p; EnQueue(Q,T); while(!IsEmpty(Q)){ DeQueue(Q,p); coutp-data; if(p-lchild ! NULL) EnQueue(Q,p-lchild); if(p-rchild ! NULL) EnQueue(Q,p-rchild); } }实际上是利用了BFS的思想当队列不空时就出队队头元素并访问输出然后将队头元素所有的领接点左右孩子入队不断重复这个过程直到队列为空。②非递归遍历先序序列void PreOrderTraverse(BiTree T) { InitStack(S); BiTree p T; BiTree q; while(p || !StackEmpty(S)) { if(p) { coutp-data; Push(S,p); pp-lchild; } else { Pop(S,q); p-q-rchild; } } }此时使用栈的方式得到的入栈序列为树的先序序列出栈序列为树的中序序列中序序列void InOrderTraverse(BiTree T) { InitStack(S); BiTree p T; BiTree q; while(p || !StackEmpty(S)) { if(p) { Push(S,p); pp-lchild; } else { Pop(S,q); coutq-data; pq-rchild; } } }后序序列void PostOrederTraverse(BiTree T) { InitStack(S); BiTree p T,r NULL; while(p || !StackEmpty(S)) { if(P) { Push(S,p); pp-lchild; } else { GetTop(S,q); if(q-rchild q-rchild ! r) pq-rchild; else { Pop(S,q); coutq-data; rq; p-NULL; } } }r手动记录“右子树是否访问过”取栈顶元素q如果【q的右孩子非空】且【不是上一个访问输出的结点】就说明q的右子树还没遍历过此时不能输出q而是先去遍历q的右子树如果【q的右孩子为空】或【q的右孩子刚被访问过】说明此时可以正常访问输出q并用r手动记录刚访问过的结点q③线索化线索化在遍历过程中不断地去检查每一个结点的左孩子指针跟右孩子指针有没有指向他的孩子如果没有则可以用这个指针去改为指向它的前驱和后继注使用结点中的空链域作为线索化指向中序线索树中若某结点有右孩子则它的后继结点是它右子树中最左下的结点中序线索树种若某结点有左孩子则它的前驱结点是它左子树中最右下的结点典型真题2009年真题该题给出遍历后结点序列3175624则我们可以根据树形结构知道其是先遍历右子树即R开头排除AB选项又因为3遍历之后为11位于二叉树的根即可以判断出是RNL的遍历方式选择选项D。2017年真题该题我们可以知道先序序列的遍历方式为NLR中序序列的遍历方式为LNR要使得序列相同只有两种情况即左右子树都没有或没有左子树即为NR方式则我们可以知道要使得非叶结点叶满足的情况只有B选项。2022年真题该题结点p与q在中序序列中相邻且p在q前我们可以很明显地知道的一种情况是若q是p的右兄弟的时候在中序序列中必有一个结点在二者中间无法达到相邻所以Ⅲ错误又因为中序遍历方式为LNR的方式当q是p的右孩子的时候能够满足条件所以选择选项B。2010年真题该题需要得出符合后序线索树的线索二叉树因为后序二叉树的序列方式为LRN则序列为dbca因为b的左孩子为空则b的直接前驱应该为d即b的前驱会指向d则可以排除A,B,C选择选项D考点5 树、森林、二叉树树和二叉树二叉树和森林树-二叉树左孩子右兄弟二叉树-森林二叉树的根根的右孩子根的右孩子的右孩子...均为森林中树的根结点其余按照左孩子右兄弟转换森林-二叉树森林中所有树的根结点组成二叉树的根根的右孩子根的右孩子的右孩子...其余按照左孩子右兄弟转换注二叉树中没有右孩子的结点是森林中最后一颗树里面包含根结点所有非终端结点的最后一个孩子注二叉树中没有右孩子的结点是原本树里面包含根结点所有非终端结点的最后一个孩子树二叉树森林的遍历树二叉树森林先根遍历先序遍历先序遍历后根遍历中序遍历中后序遍历如果不知道如何对树和森林进行遍历可先转化为二叉树再对二叉树进行相应的遍历典型真题2009年真题该题如上给出的4中树形结构的方式即为结点u是结点v的父节点的父节点的所有情况则在二叉树转为森林当中1中v转为u的右孩子得出u和v可能具有Ⅰ的关系2的转换不变3的转换中u成为v的父节点的父节点的左孩子在4中若u有父节点则u和v的关系变为兄弟关系由此得出只有Ⅰ和Ⅱ的关系选择选项B。2011年真题该题我们可以知道在树转二叉树中树种只有根结点和最右的叶节点转换的二叉树无右孩子则我们可以知道该树的结构如下图所示因为有116个叶节点所以有2011-11611896个这样的结点数选择选项D。2014年真题该题根据前面总结的结论树里面或者是森林里面所有的叶子节点对应了转换为二叉树里面所有没有左孩子的结点选择选项C。考点6 哈夫曼树和哈夫曼编码定长哈夫曼编码所有字符都位于哈夫曼树的同一层哈夫曼编码长度相同变长哈夫曼编码字符都位于哈夫曼树的不同层哈夫曼编码长度不同哈夫曼编码规律①若有n个结点则在哈夫曼树的构造过程中新建了n-1个结点最终一共2n-1个结点②哈夫曼树只有度为0和2的结点不存在度为1的结点即③非空二叉树满足故哈夫曼树④权值频度越小的结点一般离根结点越远利用这条性质保证出现最多的字符拥有最短的编码⑤同一组权值构造出的哈夫曼树可能不唯一⑥m叉哈夫曼树1.定义只有度为0和m的结点的哈夫曼树2.构造过程初始结点有个首先计算如果k!0则需要补充m-1-k个权为0的结点3.仿造二叉哈夫曼树的构造过程每次结合m个权值最小的结点重复该过程WPL的计算结点的带权路径长度从该结点到根之间的路径长度与结点上权值的乘积树的带权路径长度WPL树中所有叶子结点的带权路径长度之和典型真题2010年真题该题我们可以很明显地知道A选项是错误的因为在哈夫曼树当中没有严格地要求树形哈夫曼树的树形非常多变所以选择选项A。2019年真题该题我们可以用总结出的规律来解答在哈夫曼树中只有度为0和2的结点所以可以列出等式和则得出解得n的值为58选择选项C。2022年真题该题定长编码集所有字符都在树里位于同一层变长编码集所有字符位于树的不同层 则我们可以知道哈夫曼编码集得到的二叉树出现不同频次的字符在中有可能处于相同的层而对于定长的哈夫曼编码集中不同频次的字符都位于同一层即在中处于相同层。注哈夫曼编码加权平均值为每个字符对应的哈夫曼编码的长度为每个字符的权值考点7 并查集的基本操作数组下标代表的是该结点对应的值存储数据对应的是该结点的父节点根结点存储的是结点数注并查集是基于双亲表示法①初始化#define MAXSIZE 10 void Initial(int S[]) { for(int i 0;i MAXSIZE;i) s[i] -1; }②查找int Find(int S[],int x) { while(S[x] 0) x S[x]; return x; }一直往上沿着父节点的方向查找直到找到对应数据的值查找优化路径压缩int FindWithPathCompression(int S[],int x) { int root x; while(S[root] 0) root S[root];//这个while是在找集合的根 while(x ! root) { int t S[x];//t是为了标记x的父节点 S[x] root;//把x挂在root下 x t;//接下来一直往上处理x父节点全部挂到root下 } return root; }将同一条链路上的值挂载在根结点上实现路径压缩③合并void Union(int S[],int root1,int root2) { if(root1 root2) return ; S[root1] S[root2]; S[root2] root1; }合并传入的两个参数必须是要合并的两个结合的根结点优化合并操作(规模合并)void UnionBySize(int S[],int root1,int root2) { if(root1 root2) return ; if(S[root1] S[root2]) { S[root1] S[root2]; S[root2] root1; } else S[root2] S[root1]; S[root1] root2; }优化后的Union可以将集合树的高度控制在O()以内规模小的挂在规模大的集合当中使用并查集的基本操作就是先Find在Union即Union(Find(x),Find(y))优化后的FindUnionOa(n)④并查集的应用1.检测图中是否有环2.实现Kruskal算法(判断最小生成树)3.判断无向图的连通性考点8 图的概念和性质①假设有两个图G(V,E)和G‘(V,E)如果VVEE则称G为G的子图一定要确保V和E是可以扯上关系的②无向完全图有条边有向完全图有n(n-1)条弧完全图一定是连通/强连通的并且完全图的边数是给定顶点数量时最多的所有顶点都有边③连通分量 无向图中的极大连通子图 强连通分量 有向图中的极大强连通子图极大表示边数达到顶点能承受的最大数量即原图中和某顶点相关的边都需要出现对于一个连通图来说它的一个极大连通图就是它自己一个连通图只有一个连通分量 一个强连通的有向图只有一个强连通分量④生成树 无向连通图中一个包含图中所有顶点的极小连通子图a.极小表示保证连通的前提下边数要达到最小再减一条边就不连通b.极小连通子图本身不要求必须包含图中的所有顶点c.最小生成树MST是所有生成树中边的权值之和最小的生成树⑤对于无向图来说最少需要n-1条边才能连通边数大于n-1时必有环对于有向图来说最少需要n条弧才能保证强连通形成一个环⑥无向图中所有顶点的度之和等于边数的2倍有向图所有顶点的入度之和出度之和弧数⑦n个顶点的无向图最少有1个连通分量最多有n个连通分量最少情况下n个顶点两两之间都有路径所以无向图本身就是自己唯一的连通分量最多情况下不存在边每个顶点独立并自成一个连通分量⑧【保证连通】和【可以实现连通】的驱避恶a.保证连通是指无论边怎么换位置图都是连通的b.可以实现连通是指边在某些位置中可以构造出连通图但如果换位置可能就无法确保依旧连通【问法1】让n个顶点的无向图实现连通至少需要几条边【答】n-1【问法2】让n个顶点的无向图保证连通至少需要几条边【答】典型真题2009年真题该题根据前面总结的规律可以知道对于无向连通图所有顶点的度数之和等于边数的2倍即证明无向连通图的所有顶点的度之和为偶数Ⅰ正确对于无向连通图当边数等于n-1时就可以实现连通所以Ⅱ错误Ⅲ中对于无向连通图如有三个顶点的无向连通图其顶点的度全为2即证Ⅲ错误所以选择选项A。2010年真题该题问的是要【保证能够构成连通图】即至少应该需要条边即16选择选项C。2017年真题该题无向图中度之和等于所有边数的2倍由因为要达到顶点个数最少即需要其他顶点的度为2即可我们可以得出等式323*44*3x*2解出x4所以顶点个数为43411选择选项B。2022年真题该题我们需要知道V是代表顶点E代表的是边我们可以知道连通无向图中可以连通的情况是边数顶点数-1则可以知道选项B错误对于选项A当边数顶点数-1时由前面总结的规律可以知道不一定保证无向图的连通的所以A选项错误同理我们可以知道选项D是正确。考点9 邻接矩阵和邻接表邻接矩阵①无向图a.顶点的度 第i行元素之和 第i列元素之和b.邻接矩阵是对称的可以压缩存储上/下三角即需要个单元来存储边②有向图a.顶点的出度 第i行元素之和b.顶点的入度 第i列元素之和c.n个顶点的图需要个单元来存储边邻接表①无向图a.顶点的度 第i个边表中的结点个数b.n个顶点表结构 2e个边表结点边表结点一定是偶数个②有向图a.顶点的出度 第i个边表中的结点个数b.顶点的入度需要遍历各顶点的边表才能得出即顶点的入度就是在边表中出现的次数c.n个顶点表结点 e个边表结点注在邻接矩阵中表示从顶点i到顶点j之间长度为k的路径条数典型真题2015年真题考点10 十字链表和邻接多重表①结点结构十字链表十字链表的构造邻接多重表无向图中的邻接多重表会有多种形式②优势十字链表结合了邻接表和逆邻接表可以方便地计算顶点的入度和出度/寻找依附于某一结点的所有弧邻接多重表中每条边只会被存储一次且所有依附于同一结点的边都被串联在一个链表中便于计算结点的度/寻找依附于某一结点的所有边考点11 DFS和BFS①DFS思想及在不同存储结构上的实现bool visited[MVNum]; void DFS(Graph G,int v) { count v; visited[v] true; for(int w FirstAdjVex(G,v); w 0; w NextAdjVex(G,v,w)) { if(!visited[w]) DFS(G,w); } } void DFSTraverse(Graph G) { for(int v 0; v G.vexnum;v) visited[v] false; for(int v 0; v G.vexnum;v} if(!visited[v]) DFS(G,v); }DFS深度优先遍历从一个顶点开始先标记访问并输出它再去检查它的邻接点如果邻接点未被访问过就对邻接点再次调用DFS重复上述操作直到所有顶点都被标记访问DFSTraverse()中调用DFS()的次数连通分量的个数//DFS核心语句 for(int w FirstAdjVex(G,v);w 0; w NextAdjVex(G,v,w)) { if(!visited[w]) DFS(G,w); }邻接矩阵从给定的参数顶点v开始首先遍历邻接矩阵中第v行的所有元素如果第w列的值不为0说明顶点v与顶点w之间存在边若此时顶点w尚未被访问则将w作为参数递归调用DFS继续以同样方式访问w的所有邻接点直到所有可达顶点都被访问为止时间复杂度为O()邻接表从给定的参数顶点v开始先访问v所对应的邻接表获取其第一个邻接点指针p然后沿着邻接表的边表不断向后遍历每次取出当前边所指向的邻接点w如果w尚未被访问就将w作为参数递归调用DFS直到所有可达顶点都被访问为止时间复杂度为O(ne)②BFS思想及在不同存储结构上的实现bool visited[MVNum]; void BFSTraverse(Graph G) { for(v 0; v G.vexnum;v) visited[v] false; for(v 0; v G.vexnum;v) if(!visited[v]) BFS(G,v); } void BFS(Graph G,int v) { cout v; visited[v] true; InitQueue(Q); EnQueue(Q,v); while(!QueueEmpty(Q)) { DeQueue(Q,u); for(w FirstAdjVex(G,u);w 0; w NextAdjVex(G,U,W)) if(!visited[w]) { cout w; visited[w] true; EnQueue(Q,w); } } }从一个顶点开始先标记访问并输出它再将它加入队列然后不断从队列中取出队头顶点检查该顶点的所有邻接点如果某个邻接点未被访问过就标记访问、输出并加入队列重复上述过程直到队列为空为止邻接矩阵从给定的参数顶点v开始首先输出顶点v并将其标记为已访问将顶点v入队当队列不为空时循环执行以下操作1.从队列中取出队头顶点u遍历邻接矩阵第u行的所有元素依次检查每个顶点w2.如果G.arcs[u][w]不为0说明u与w之间存在边3.如果顶点w尚未被访问则输出w标记访问并将w入队继续检查u行中剩下的所有列直到扫描完整行时间复杂度O()邻接表从给定的参数顶点v开始首先输出顶点v并将其标记为已访问将顶点v入队当队列不为空时循环执行以下操作1.从队列中取出队头顶点u访问顶点u所对应的邻接表获取第一个邻接点指针p2.沿着邻接表不断向后遍历每次取出当前边指向的邻接点w3.如果w尚未被访问则输出w并标记访问并将w入队4.继续遍历邻接表的下一项直到p为NULL时间复杂度为O(ne)③图与树的遍历关系图的DFS类似于树的先序遍历图的BFS类似于树的层序遍历④DFS和BFS的应用DFSBFS判断环路权值相同的有权图/无权图拓扑排序单源最短路径判断图是否连通通过对代码进行修改BFS实际上也可以用于判断环路或实现拓扑排序但DFS的思路更符合这两个应用场景所以更常用注图是连通的 从任意一个顶点出发可以访问到所有其他顶点
【408学习】数据结构——非线性结构
注本文为博主学习408相关知识所撰写的学习笔记内容如有雷同纯属巧合。考点1 树形推断①N ... 0*1*2*...n*1节点点数N 度之和 1②非空二叉树满足 1③度为m的树第i层上最多个节点④高度为h的满m叉树一共有个节点⑤具有n个结点的完全二叉树的高度为或⑥对完全二叉树按照层序进行编号i1,2...n:i为偶数时父节点为i/2i是父节点的左孩子i为奇数时父节点为(i-1)/2i是父节点的右孩子i的左孩子为2i或不存在i的右孩子为2i1或不存在i≤时i为分支节点i时i为叶子节点若n为奇数则每个分支节点都有左右孩子若n为偶数则in/2(最后一个分支节点)只有左孩子⑦完全二叉树中度为1的节点只可能有1个或者0个⑧树越高越细每层节点数量少越矮越胖每层节点数量多⑨完全二叉树只有最后两层可能出现叶节点典型真题2010年真题该题需要用到第①个公式即N 0*1*2*3*4*1得到公式1*102*110*320*41-(1011020)82选择选项B2016年真题该题我们分析树的节点结构可以知道树的总结点个数等于分支数加一即N分支数1在一颗树里面除了根节点以外其他节点都有分支则我们可以知道有多少个分支(边)就有多少个非根节点又因为题目给出有25个节点则根节点有25-1510个解得森林F包含树的个数为10个选择选项C。2009年真题该题给出树形结构为完全二叉树则只会出现两种树形结构又因为题目给出完全二叉树的第6层有8个节点则该完全二叉树不为满二叉树且该完全二叉树有7层因此我们可以知道前6层共有63个节点又因为第6层有8个节点则在第六层中有个节点生出了最后一层的叶子节点得到第七层有24*248个节点所以该完全二叉树一共有6348111个节点数。2011年真题该题一共有768个节点位于768之间由此可以判断该二叉树有十层在前9层中有511个结点得到第十层的叶节点有768-511257个由此可以得到第九层有129个节点有子节点则其余节点为叶节点有256-129127个节点所以得到该二叉树中叶节点的个数为127257384选择选项C。2018年真题该题给出所有叶节点均位于同一层且每个非叶节点都有2个子节点则可以知道该完全二叉树为满二叉树整颗树中只有度为2和度为0的节点假设有h层则叶节点总数为k得到h由于题目求T的节点总数即得到节点总数为2k-1。2022年真题该题问T的高度至少是多少即需要得到的是一个满三叉树的树形结构由于高度为h的m叉树一共有个节点则可以得到244个节点位于121244364之间则可以知道该三叉树前5层为满三叉树可以得到该三叉树高度至少为51层即选择选项C。2016年大题该题先提取题目中的信息我们可以知道树中只有度为0的节点和度为k的节点。第一问中T有m个非叶节点我们可以知道树中只有度为0和度为k的节点根据总结的公式可以得到等式Nk*1,因为非叶节点即度为k的节点所以得到叶节点(k-1)*m1。第二问中节点数最多即求满二叉树的情况则可以用到满m叉树的公式可以得到最多节点树为节点数最少中因为每个非叶节点都有k个孩子则根结点最少需要有k个节点根节点以下的某一个节点的孩子必须有k个孩子才能得到节点数最少的情况则可以得到除第一层有一个节点外其他每层都有k个节点得到最少的情况为1(h-1)*k。考点2 树的存储①二叉树的两种存储方式顺序存储方式注k个结点的n叉树中根结点有n*k个链域非根结点有k-1个链域链式存储方式②树的三种存储方式双亲表示法孩子表示法孩子兄弟表示法特点以一组连续的存储单元存储树的结点的双亲将每个结点的孩子视为以单链表存储的线性表n个结点又组成另一个基于顺序表的线性表对树的每个结点按照“左孩子右兄弟”的原则转换为二叉树并用二叉链表存储优点寻找双亲方便寻找孩子方便寻找孩子方便缺点寻找孩子需要遍历整个结构寻找双亲需要遍历整个结构寻找双亲需要遍历整个结构典型真题2020年真题该题给出采用顺序存储结构保存顺序存储结构空结点也需要分配存储单元 题目给出对于任意一颗高度为5的二叉树即最后一个结点的位置可以在第五层的任意位置题目需要求至少需要的存储单元即最后一个结点落在第五层的最后的位置上则需要31个存储单元选择A选项。考点3 唯一确定一颗二叉树中序任意一种遍历序列一颗确定的二叉树典型真题2011年真题该题我们可以通过中序前序的方式得到每一个选项的树形结构由于前序序列为:1234若中序序列为C选项的3241则可以得到的树形结构的后序序列为3421与题干不符所以选择选项C。2012年真题考点4 遍历一个线索二叉树①二叉树的四种遍历先序遍历void PreOrderTraverse(BiTree T) { if(T) { cout T-data; PreOrderTraverse(T-lchild); PreOrderTraverse(T-rchild); } }遍历过程中每个结点都会经过3次第一次经过时访问并输出它然后开始遍历左子树第二次经过是因为它的左子树已遍历完毕第三次经过是因为它的右子树已遍历完毕。中序遍历void InOrderTraverse(BiTree T) { if(T){ InOrderTraverse(T-lchild); coutT-data; InOrderTraverse(T-rchild);} }遍历过程中每个结点都会经过3次第一次经过是为了能访问到它的左子树第二次经过是因为左子树已遍历完毕此时访问并输出它然后开始遍历右子树第三次经过是因为它的右子树已遍历完成。后序遍历void PostOrderTraverse(BiTree T) { if(T){ PostOrderTraverse(T-lchild); PostOrderTraverse(T-rchild); coutT-data;} }遍历过程中每个结点都会经过3次第一次经过是为了能访问到它的左子树第二次经过是为了能访问它的右子树第三次经过是因为左右子树已遍历完毕此时访问并输出它。层序遍历//借助队列的层序遍历 void LeavelOrder(BiTree T){ InitQueue(Q); BiTree p; EnQueue(Q,T); while(!IsEmpty(Q)){ DeQueue(Q,p); coutp-data; if(p-lchild ! NULL) EnQueue(Q,p-lchild); if(p-rchild ! NULL) EnQueue(Q,p-rchild); } }实际上是利用了BFS的思想当队列不空时就出队队头元素并访问输出然后将队头元素所有的领接点左右孩子入队不断重复这个过程直到队列为空。②非递归遍历先序序列void PreOrderTraverse(BiTree T) { InitStack(S); BiTree p T; BiTree q; while(p || !StackEmpty(S)) { if(p) { coutp-data; Push(S,p); pp-lchild; } else { Pop(S,q); p-q-rchild; } } }此时使用栈的方式得到的入栈序列为树的先序序列出栈序列为树的中序序列中序序列void InOrderTraverse(BiTree T) { InitStack(S); BiTree p T; BiTree q; while(p || !StackEmpty(S)) { if(p) { Push(S,p); pp-lchild; } else { Pop(S,q); coutq-data; pq-rchild; } } }后序序列void PostOrederTraverse(BiTree T) { InitStack(S); BiTree p T,r NULL; while(p || !StackEmpty(S)) { if(P) { Push(S,p); pp-lchild; } else { GetTop(S,q); if(q-rchild q-rchild ! r) pq-rchild; else { Pop(S,q); coutq-data; rq; p-NULL; } } }r手动记录“右子树是否访问过”取栈顶元素q如果【q的右孩子非空】且【不是上一个访问输出的结点】就说明q的右子树还没遍历过此时不能输出q而是先去遍历q的右子树如果【q的右孩子为空】或【q的右孩子刚被访问过】说明此时可以正常访问输出q并用r手动记录刚访问过的结点q③线索化线索化在遍历过程中不断地去检查每一个结点的左孩子指针跟右孩子指针有没有指向他的孩子如果没有则可以用这个指针去改为指向它的前驱和后继注使用结点中的空链域作为线索化指向中序线索树中若某结点有右孩子则它的后继结点是它右子树中最左下的结点中序线索树种若某结点有左孩子则它的前驱结点是它左子树中最右下的结点典型真题2009年真题该题给出遍历后结点序列3175624则我们可以根据树形结构知道其是先遍历右子树即R开头排除AB选项又因为3遍历之后为11位于二叉树的根即可以判断出是RNL的遍历方式选择选项D。2017年真题该题我们可以知道先序序列的遍历方式为NLR中序序列的遍历方式为LNR要使得序列相同只有两种情况即左右子树都没有或没有左子树即为NR方式则我们可以知道要使得非叶结点叶满足的情况只有B选项。2022年真题该题结点p与q在中序序列中相邻且p在q前我们可以很明显地知道的一种情况是若q是p的右兄弟的时候在中序序列中必有一个结点在二者中间无法达到相邻所以Ⅲ错误又因为中序遍历方式为LNR的方式当q是p的右孩子的时候能够满足条件所以选择选项B。2010年真题该题需要得出符合后序线索树的线索二叉树因为后序二叉树的序列方式为LRN则序列为dbca因为b的左孩子为空则b的直接前驱应该为d即b的前驱会指向d则可以排除A,B,C选择选项D考点5 树、森林、二叉树树和二叉树二叉树和森林树-二叉树左孩子右兄弟二叉树-森林二叉树的根根的右孩子根的右孩子的右孩子...均为森林中树的根结点其余按照左孩子右兄弟转换森林-二叉树森林中所有树的根结点组成二叉树的根根的右孩子根的右孩子的右孩子...其余按照左孩子右兄弟转换注二叉树中没有右孩子的结点是森林中最后一颗树里面包含根结点所有非终端结点的最后一个孩子注二叉树中没有右孩子的结点是原本树里面包含根结点所有非终端结点的最后一个孩子树二叉树森林的遍历树二叉树森林先根遍历先序遍历先序遍历后根遍历中序遍历中后序遍历如果不知道如何对树和森林进行遍历可先转化为二叉树再对二叉树进行相应的遍历典型真题2009年真题该题如上给出的4中树形结构的方式即为结点u是结点v的父节点的父节点的所有情况则在二叉树转为森林当中1中v转为u的右孩子得出u和v可能具有Ⅰ的关系2的转换不变3的转换中u成为v的父节点的父节点的左孩子在4中若u有父节点则u和v的关系变为兄弟关系由此得出只有Ⅰ和Ⅱ的关系选择选项B。2011年真题该题我们可以知道在树转二叉树中树种只有根结点和最右的叶节点转换的二叉树无右孩子则我们可以知道该树的结构如下图所示因为有116个叶节点所以有2011-11611896个这样的结点数选择选项D。2014年真题该题根据前面总结的结论树里面或者是森林里面所有的叶子节点对应了转换为二叉树里面所有没有左孩子的结点选择选项C。考点6 哈夫曼树和哈夫曼编码定长哈夫曼编码所有字符都位于哈夫曼树的同一层哈夫曼编码长度相同变长哈夫曼编码字符都位于哈夫曼树的不同层哈夫曼编码长度不同哈夫曼编码规律①若有n个结点则在哈夫曼树的构造过程中新建了n-1个结点最终一共2n-1个结点②哈夫曼树只有度为0和2的结点不存在度为1的结点即③非空二叉树满足故哈夫曼树④权值频度越小的结点一般离根结点越远利用这条性质保证出现最多的字符拥有最短的编码⑤同一组权值构造出的哈夫曼树可能不唯一⑥m叉哈夫曼树1.定义只有度为0和m的结点的哈夫曼树2.构造过程初始结点有个首先计算如果k!0则需要补充m-1-k个权为0的结点3.仿造二叉哈夫曼树的构造过程每次结合m个权值最小的结点重复该过程WPL的计算结点的带权路径长度从该结点到根之间的路径长度与结点上权值的乘积树的带权路径长度WPL树中所有叶子结点的带权路径长度之和典型真题2010年真题该题我们可以很明显地知道A选项是错误的因为在哈夫曼树当中没有严格地要求树形哈夫曼树的树形非常多变所以选择选项A。2019年真题该题我们可以用总结出的规律来解答在哈夫曼树中只有度为0和2的结点所以可以列出等式和则得出解得n的值为58选择选项C。2022年真题该题定长编码集所有字符都在树里位于同一层变长编码集所有字符位于树的不同层 则我们可以知道哈夫曼编码集得到的二叉树出现不同频次的字符在中有可能处于相同的层而对于定长的哈夫曼编码集中不同频次的字符都位于同一层即在中处于相同层。注哈夫曼编码加权平均值为每个字符对应的哈夫曼编码的长度为每个字符的权值考点7 并查集的基本操作数组下标代表的是该结点对应的值存储数据对应的是该结点的父节点根结点存储的是结点数注并查集是基于双亲表示法①初始化#define MAXSIZE 10 void Initial(int S[]) { for(int i 0;i MAXSIZE;i) s[i] -1; }②查找int Find(int S[],int x) { while(S[x] 0) x S[x]; return x; }一直往上沿着父节点的方向查找直到找到对应数据的值查找优化路径压缩int FindWithPathCompression(int S[],int x) { int root x; while(S[root] 0) root S[root];//这个while是在找集合的根 while(x ! root) { int t S[x];//t是为了标记x的父节点 S[x] root;//把x挂在root下 x t;//接下来一直往上处理x父节点全部挂到root下 } return root; }将同一条链路上的值挂载在根结点上实现路径压缩③合并void Union(int S[],int root1,int root2) { if(root1 root2) return ; S[root1] S[root2]; S[root2] root1; }合并传入的两个参数必须是要合并的两个结合的根结点优化合并操作(规模合并)void UnionBySize(int S[],int root1,int root2) { if(root1 root2) return ; if(S[root1] S[root2]) { S[root1] S[root2]; S[root2] root1; } else S[root2] S[root1]; S[root1] root2; }优化后的Union可以将集合树的高度控制在O()以内规模小的挂在规模大的集合当中使用并查集的基本操作就是先Find在Union即Union(Find(x),Find(y))优化后的FindUnionOa(n)④并查集的应用1.检测图中是否有环2.实现Kruskal算法(判断最小生成树)3.判断无向图的连通性考点8 图的概念和性质①假设有两个图G(V,E)和G‘(V,E)如果VVEE则称G为G的子图一定要确保V和E是可以扯上关系的②无向完全图有条边有向完全图有n(n-1)条弧完全图一定是连通/强连通的并且完全图的边数是给定顶点数量时最多的所有顶点都有边③连通分量 无向图中的极大连通子图 强连通分量 有向图中的极大强连通子图极大表示边数达到顶点能承受的最大数量即原图中和某顶点相关的边都需要出现对于一个连通图来说它的一个极大连通图就是它自己一个连通图只有一个连通分量 一个强连通的有向图只有一个强连通分量④生成树 无向连通图中一个包含图中所有顶点的极小连通子图a.极小表示保证连通的前提下边数要达到最小再减一条边就不连通b.极小连通子图本身不要求必须包含图中的所有顶点c.最小生成树MST是所有生成树中边的权值之和最小的生成树⑤对于无向图来说最少需要n-1条边才能连通边数大于n-1时必有环对于有向图来说最少需要n条弧才能保证强连通形成一个环⑥无向图中所有顶点的度之和等于边数的2倍有向图所有顶点的入度之和出度之和弧数⑦n个顶点的无向图最少有1个连通分量最多有n个连通分量最少情况下n个顶点两两之间都有路径所以无向图本身就是自己唯一的连通分量最多情况下不存在边每个顶点独立并自成一个连通分量⑧【保证连通】和【可以实现连通】的驱避恶a.保证连通是指无论边怎么换位置图都是连通的b.可以实现连通是指边在某些位置中可以构造出连通图但如果换位置可能就无法确保依旧连通【问法1】让n个顶点的无向图实现连通至少需要几条边【答】n-1【问法2】让n个顶点的无向图保证连通至少需要几条边【答】典型真题2009年真题该题根据前面总结的规律可以知道对于无向连通图所有顶点的度数之和等于边数的2倍即证明无向连通图的所有顶点的度之和为偶数Ⅰ正确对于无向连通图当边数等于n-1时就可以实现连通所以Ⅱ错误Ⅲ中对于无向连通图如有三个顶点的无向连通图其顶点的度全为2即证Ⅲ错误所以选择选项A。2010年真题该题问的是要【保证能够构成连通图】即至少应该需要条边即16选择选项C。2017年真题该题无向图中度之和等于所有边数的2倍由因为要达到顶点个数最少即需要其他顶点的度为2即可我们可以得出等式323*44*3x*2解出x4所以顶点个数为43411选择选项B。2022年真题该题我们需要知道V是代表顶点E代表的是边我们可以知道连通无向图中可以连通的情况是边数顶点数-1则可以知道选项B错误对于选项A当边数顶点数-1时由前面总结的规律可以知道不一定保证无向图的连通的所以A选项错误同理我们可以知道选项D是正确。考点9 邻接矩阵和邻接表邻接矩阵①无向图a.顶点的度 第i行元素之和 第i列元素之和b.邻接矩阵是对称的可以压缩存储上/下三角即需要个单元来存储边②有向图a.顶点的出度 第i行元素之和b.顶点的入度 第i列元素之和c.n个顶点的图需要个单元来存储边邻接表①无向图a.顶点的度 第i个边表中的结点个数b.n个顶点表结构 2e个边表结点边表结点一定是偶数个②有向图a.顶点的出度 第i个边表中的结点个数b.顶点的入度需要遍历各顶点的边表才能得出即顶点的入度就是在边表中出现的次数c.n个顶点表结点 e个边表结点注在邻接矩阵中表示从顶点i到顶点j之间长度为k的路径条数典型真题2015年真题考点10 十字链表和邻接多重表①结点结构十字链表十字链表的构造邻接多重表无向图中的邻接多重表会有多种形式②优势十字链表结合了邻接表和逆邻接表可以方便地计算顶点的入度和出度/寻找依附于某一结点的所有弧邻接多重表中每条边只会被存储一次且所有依附于同一结点的边都被串联在一个链表中便于计算结点的度/寻找依附于某一结点的所有边考点11 DFS和BFS①DFS思想及在不同存储结构上的实现bool visited[MVNum]; void DFS(Graph G,int v) { count v; visited[v] true; for(int w FirstAdjVex(G,v); w 0; w NextAdjVex(G,v,w)) { if(!visited[w]) DFS(G,w); } } void DFSTraverse(Graph G) { for(int v 0; v G.vexnum;v) visited[v] false; for(int v 0; v G.vexnum;v} if(!visited[v]) DFS(G,v); }DFS深度优先遍历从一个顶点开始先标记访问并输出它再去检查它的邻接点如果邻接点未被访问过就对邻接点再次调用DFS重复上述操作直到所有顶点都被标记访问DFSTraverse()中调用DFS()的次数连通分量的个数//DFS核心语句 for(int w FirstAdjVex(G,v);w 0; w NextAdjVex(G,v,w)) { if(!visited[w]) DFS(G,w); }邻接矩阵从给定的参数顶点v开始首先遍历邻接矩阵中第v行的所有元素如果第w列的值不为0说明顶点v与顶点w之间存在边若此时顶点w尚未被访问则将w作为参数递归调用DFS继续以同样方式访问w的所有邻接点直到所有可达顶点都被访问为止时间复杂度为O()邻接表从给定的参数顶点v开始先访问v所对应的邻接表获取其第一个邻接点指针p然后沿着邻接表的边表不断向后遍历每次取出当前边所指向的邻接点w如果w尚未被访问就将w作为参数递归调用DFS直到所有可达顶点都被访问为止时间复杂度为O(ne)②BFS思想及在不同存储结构上的实现bool visited[MVNum]; void BFSTraverse(Graph G) { for(v 0; v G.vexnum;v) visited[v] false; for(v 0; v G.vexnum;v) if(!visited[v]) BFS(G,v); } void BFS(Graph G,int v) { cout v; visited[v] true; InitQueue(Q); EnQueue(Q,v); while(!QueueEmpty(Q)) { DeQueue(Q,u); for(w FirstAdjVex(G,u);w 0; w NextAdjVex(G,U,W)) if(!visited[w]) { cout w; visited[w] true; EnQueue(Q,w); } } }从一个顶点开始先标记访问并输出它再将它加入队列然后不断从队列中取出队头顶点检查该顶点的所有邻接点如果某个邻接点未被访问过就标记访问、输出并加入队列重复上述过程直到队列为空为止邻接矩阵从给定的参数顶点v开始首先输出顶点v并将其标记为已访问将顶点v入队当队列不为空时循环执行以下操作1.从队列中取出队头顶点u遍历邻接矩阵第u行的所有元素依次检查每个顶点w2.如果G.arcs[u][w]不为0说明u与w之间存在边3.如果顶点w尚未被访问则输出w标记访问并将w入队继续检查u行中剩下的所有列直到扫描完整行时间复杂度O()邻接表从给定的参数顶点v开始首先输出顶点v并将其标记为已访问将顶点v入队当队列不为空时循环执行以下操作1.从队列中取出队头顶点u访问顶点u所对应的邻接表获取第一个邻接点指针p2.沿着邻接表不断向后遍历每次取出当前边指向的邻接点w3.如果w尚未被访问则输出w并标记访问并将w入队4.继续遍历邻接表的下一项直到p为NULL时间复杂度为O(ne)③图与树的遍历关系图的DFS类似于树的先序遍历图的BFS类似于树的层序遍历④DFS和BFS的应用DFSBFS判断环路权值相同的有权图/无权图拓扑排序单源最短路径判断图是否连通通过对代码进行修改BFS实际上也可以用于判断环路或实现拓扑排序但DFS的思路更符合这两个应用场景所以更常用注图是连通的 从任意一个顶点出发可以访问到所有其他顶点
