企业官网建设流程全解析

注：本文为博主学习408相关知识所撰写的学习笔记内容，如有雷同，纯属巧合。

考点1 树形推断

①N =+++...+= 0*+1*+2*+...+n*+1（节点点数N = 度之和 + 1）

②非空二叉树满足=+ 1

③度为m的树第i层上最多个节点

④高度为h的满m叉树一共有个节点

⑤具有n个结点的完全二叉树的高度为或

⑥对完全二叉树按照层序进行编号，i=1,2...，n:

• i为偶数时，父节点为i/2，i是父节点的左孩子，i为奇数时，父节点为(i-1)/2，i是父节点的右孩子
• i的左孩子为2i或不存在，i的右孩子为2i+1或不存在
• i≤时，i为分支节点；i>时，i为叶子节点
• 若n为奇数，则每个分支节点都有左右孩子；若n为偶数，则i=n/2(最后一个分支节点)只有左孩子

⑦完全二叉树中度为1的节点（）只可能有1个或者0个

⑧树越高越细（每层节点数量少），越矮越胖（每层节点数量多）

⑨完全二叉树只有最后两层可能出现叶节点

典型真题

2010年真题

该题需要用到第①个公式，即N =++++= 0*+1*+2*+3*+4*+1，得到公式=1*10+2*1+10*3+20*4+1-(10+1+10+20)=82，选择选项B

2016年真题

该题，我们分析树的节点结构可以知道，树的总结点个数等于分支数加一，即N=分支数+1，在一颗树里面，除了根节点以外其他节点都有分支，则我们可以知道，有多少个分支(边)就有多少个非根节点，又因为题目给出有25个节点，则根节点有25-15=10个，解得森林F包含树的个数为10个，选择选项C。

2009年真题

该题给出树形结构为完全二叉树，则只会出现两种树形结构，又因为题目给出完全二叉树的第6层有8个节点，则该完全二叉树不为满二叉树，且该完全二叉树有7层，因此我们可以知道前6层共有

=63个节点，又因为第6层有8个节点，则在第六层中有个节点生出了最后一层的叶子节点，得到第七层有24*2=48个节点，所以该完全二叉树一共有63+48=111个节点数。

2011年真题

该题一共有768个节点，位于<768<之间，由此可以判断该二叉树有十层，在前9层中有511个结点，得到第十层的叶节点有768-511=257个，由此可以得到第九层有=129个节点有子节点，则其余节点为叶节点有256-129=127个节点，所以得到该二叉树中叶节点的个数为127+257=384选择选项C。

2018年真题

该题，给出所有叶节点均位于同一层，且每个非叶节点都有2个子节点，则可以知道该完全二叉树为满二叉树，整颗树中只有度为2和度为0的节点，假设有h层，则叶节点总数为=k得到h=，由于题目求T的节点总数，即=得到节点总数为2k-1。

2022年真题

该题问T的高度至少是多少，即需要得到的是一个满三叉树的树形结构，由于高度为h的m叉树一共有个节点，则可以得到244个节点位于=121<244<=364之间，则可以知道该三叉树前5层为满三叉树，可以得到该三叉树高度至少为5+1层即选择选项C。

2016年大题

该题，先提取题目中的信息，我们可以知道树中只有度为0的节点和度为k的节点。

第一问中，T有m个非叶节点，我们可以知道树中只有度为0和度为k的节点，根据总结的公式可以得到等式N=+=k*+1,因为非叶节点即度为k的节点，所以得到叶节点=(k-1)*m+1。

第二问中，节点数最多，即求满二叉树的情况，则可以用到满m叉树的公式，可以得到最多节点树为，节点数最少中，因为每个非叶节点都有k个孩子，则根结点最少需要有k个节点，根节点以下的某一个节点的孩子必须有k个孩子才能得到节点数最少的情况，则可以得到，除第一层有一个节点外，其他每层都有k个节点，得到最少的情况为1+(h-1)*k。

考点2 树的存储

①二叉树的两种存储方式

顺序存储方式

注：k个结点的n叉树中，根结点有n*k个链域，非根结点有k-1个链域

链式存储方式

②树的三种存储方式

典型真题

2020年真题

该题，给出采用顺序存储结构保存，顺序存储结构，空结点也需要分配存储单元， 题目给出对于任意一颗高度为5的二叉树，即最后一个结点的位置可以在第五层的任意位置，题目需要求至少需要的存储单元，即最后一个结点落在第五层的最后的位置上，则需要=31个存储单元，选择A选项。

考点3 唯一确定一颗二叉树

中序+任意一种遍历序列=一颗确定的二叉树

典型真题

2011年真题

该题，我们可以通过中序+前序的方式得到每一个选项的树形结构，由于前序序列为:1，2，3，4，若中序序列为C选项的3，2，4，1，则可以得到的树形结构的后序序列为：3，4，2，1，与题干不符，所以选择选项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); cout<<T->data; InOrderTraverse(T->rchild);} }

遍历过程中每个结点都会经过3次，第一次经过是为了能访问到它的左子树，第二次经过是因为左子树已遍历完毕，此时访问并输出它，然后开始遍历右子树，第三次经过是因为它的右子树已遍历完成。

后序遍历

void PostOrderTraverse(BiTree T) { if(T){ PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild); cout<<T->data;} }

遍历过程中每个结点都会经过3次，第一次经过是为了能访问到它的左子树，第二次经过是为了能访问它的右子树，第三次经过是因为左右子树已遍历完毕，此时访问并输出它。

层序遍历

//借助队列的层序遍历 void LeavelOrder(BiTree T){ InitQueue(Q); BiTree p; EnQueue(Q,T); while(!IsEmpty(Q)){ DeQueue(Q,p); cout<<p->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) { cout<<p->data; Push(S,p); p=p->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); p=p->lchild; } else { Pop(S,q); cout<<q->data; p=q->rchild; } } }

后序序列

void PostOrederTraverse(BiTree T) { InitStack(S); BiTree p = T,r = NULL; while(p || !StackEmpty(S)) { if(P) { Push(S,p); p=p->lchild; } else { GetTop(S,q); if(q->rchild && q->rchild != r) p=q->rchild; else { Pop(S,q); cout<<q->data; r=q; p-NULL; } } }

r手动记录“右子树是否访问过”，取栈顶元素q，如果【q的右孩子非空】且【不是上一个访问输出的结点】就说明q的右子树还没遍历过，此时不能输出q，而是先去遍历q的右子树

如果【q的右孩子为空】或【q的右孩子刚被访问过】说明此时可以正常访问输出q，并用r手动记录刚访问过的结点q

③线索化

线索化：在遍历过程中，不断地去检查每一个结点的左孩子指针跟右孩子指针，有没有指向他的孩子，如果没有，则可以用这个指针去改为指向它的前驱和后继

注：使用结点中的空链域作为线索化指向

中序线索树中，若某结点有右孩子，则它的后继结点是它右子树中最左下的结点

中序线索树种，若某结点有左孩子，则它的前驱结点是它左子树中最右下的结点

典型真题

2009年真题

该题给出遍历后结点序列，3175624，则我们可以根据树形结构知道其是先遍历右子树，即R开头，排除AB选项，又因为3遍历之后为1，1位于二叉树的根，即可以判断出是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-116+1=1896个这样的结点数，选择选项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()以内

规模小的挂在规模大的集合当中

④并查集的应用

1.检测图中是否有环

2.实现Kruskal算法(判断最小生成树)

3.判断无向图的连通性

考点8 图的概念和性质

①假设有两个图G=(V,E)和G‘=(V',E')，如果V'V，E'E，则称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即可，我们可以得出等式32=3*4+4*3+x*2，解出x=4，所以顶点个数为4+3+4=11，选择选项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(n+e)

②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行的所有元素，依次检查每个顶点w

2.如果G.arcs[u][w]不为0，说明u与w之间存在边

3.如果顶点w尚未被访问，则输出w，标记访问，并将w入队，继续检查u行中剩下的所有列，直到扫描完整行

时间复杂度O()

邻接表

从给定的参数顶点v开始，首先输出顶点v，并将其标记为已访问，将顶点v入队，当队列不为空时循环执行以下操作：

1.从队列中取出队头顶点u，访问顶点u所对应的邻接表，获取第一个邻接点指针p

2.沿着邻接表不断向后遍历，每次取出当前边指向的邻接点w

3.如果w尚未被访问，则输出w并标记访问，并将w入队

4.继续遍历邻接表的下一项，直到p为NULL

时间复杂度为O(n+e)

③图与树的遍历关系

图的DFS类似于树的先序遍历

图的BFS类似于树的层序遍历

④DFS和BFS的应用

通过对代码进行修改，BFS实际上也可以用于判断环路或实现拓扑排序但DFS的思路更符合这两个应用场景，所以更常用

注：图是连通的 <=>从任意一个顶点出发可以访问到所有其他顶点