注：本帖着重介绍树以后章节知识重点
树：
1.五个性质要熟悉（下文有介绍）
2.满二叉树属于完全二叉树（易忽略知识点）
3.三种遍历序——已知两种遍历序构造二叉树（二叉树的手工构造）
4.线索二叉树——中序、先序、后序线索化剩下几个空指针？ 明确先序、后序线索化剩下的空指针数和树的构造形状（只有左子树，只有右子树）有关系
5.树和森林的定义，与二叉树的相互转化（树和森林的先序遍历与二叉树先序遍历相同，后序遍历与二叉树的中序遍历相同） ；树和森林的存储结构：孩子-兄弟链表（也就是二叉链表了）会结合算法题考察（可能以树和森林的形式考，其实还是基于二叉链表的数据结构）
6.要会手工构造哈夫曼树，知道根节点的权值的计算方法、会计算WPL。哈夫曼编码是前缀码，要知道什么叫前缀码（下文有描述）！哈夫曼树只有2度和0度结点。
1.树的定义（some points）
广义表定义法：可以自下而上去书写
树的度：树内各结点的度的最大值
兄弟结点和堂兄弟结点不一样
2.二叉树——有序树
五个性质:（要熟记）
1）第i层结点数≤ 2^(i-1)
2）全部结点数为2^i - 1
3）n0 = n2 + 1 ( 0 2 “1” 等式)
4）有n个结点的完全二叉树的高度 [log2n]+1
5） 第i个结点的左孩子为2i，右孩子为2i+1，孩子的父节点为 i/2
二叉树有2n个指针 n-1指向结点 n+1指向空
遍历算法——参数为指向结点的指针，函数体内记住要写if(T!=NULL) 或者 i<=T.长度
遍历算法的应用：求度为0、1、2的结点数，插入删除子树、
二叉树的销毁（基于后序遍历）
3.线索二叉树（空的左孩子指针指向前驱结点，空的右孩子指针指向后驱结点）
中序线索化空指针2个
对于先序、后序线索化：左右子树都不为空，肯定只有1个
左子树为空：先序根节点为第一个，空指针+1
右子树为空：后序根节点为最后一个，空指针+1
4.树和森林
树转化为二叉树：基于左孩子-右兄弟思想转化为二叉树，森林无非是把每个树先转化为二叉树，再将每棵树根节点右连接（唯一）
若根节点没有右孩子，则为二叉树转化为树
若根节点有右孩子，则为二叉树转化为森林（先抹线再转化为二叉树转化为树的问题）
二叉树转化为树：右孩子（原本就是右兄弟）和上面双亲结点相连
算法：
求树和森林的高度 static m,;// 高度计数器 void height(csNode* T,int n) //参数列表：指针，高度
基于先序遍历（如果n大于m，则m=n），递归时兄弟的n不必+1；
求树和森林的每个结点的层次数 基于先序遍历，参数为指针和层数n，兄弟的n不必+1。
5.哈夫曼树——压缩编码技术
自下而上建立，WPL等于分支节点权值之和。
前缀码：不等长编码，任一个编码不是另一个编码的前缀。左分支标记为0，右分支标记为1。
哈弗曼编码：
等长码长度，n个不同，长度为log2n取上，乘总次数即可。
前缀码长度=哈夫曼树的WPL
压缩比 = 压缩后 / 压缩前 * 100%
图：
1.图的基本概念知道基本点即可
2.掌握邻接矩阵、邻接表的存储结构（知道如何互化）
3.非常熟悉两种遍历算法（重点掌握联通图的），要会手工去做，熟悉程序的书写（2个算法一定是基于树一题、图一题的遍历算法改造）//今年期末考试考了DFS的非递归算法（借助栈）
4.最小生成树——要会手工去做，选点法，选边法（知道什么情况选择什么算法）
5.*最短路径（Dijkstra重点）——手工去练；Floyd的基本概念（跳点，更新，时间复杂度O（n³））
6.有效无环图：拓扑排序（给个图，要能写出一条拓扑序列）；知道关键路径的概念，什么叫关键路径的几种说法（下文有描述）
1.图的基本概念
简单——不重复
2.图的邻接矩阵
elementType data[MaxVerNum]; 顶点数组
cellType AdjMatrix[MaxVerNum] [MaxVerNum] 邻接矩阵
第i行表示第i个顶点的出度，第j列表示第j个顶点的入度
3.图的邻接链表
先定义边链表（EdgeNode）：int adjVer 邻接顶点信息 struct eNode* next 指向下一个结点
再定义顶点表（VerNode）：EdgeNode* firstEdge 边链表的头指针
最后定义整体结构 顶点表数组 VerNode VerList[MaxVerNum]
图的销毁（只需逐条销毁边链表）
4.DFS
（1）访问顶点v（并标记已访问）
（2）依次DFS顶点v的未被访问的邻接点
两个常用函数：
firstAdj( G, v )：返回图G中顶点v的第一个邻 接点。若不存在邻接点（编号），则返回0；
nextAdj( G, v, w )：返回图G中顶点v的邻接 点中处于w之后的下一个邻接点。若不存在这样的邻接点（编号），则返回0；
邻接矩阵表示，时间复杂度：O(n^2)。 邻接表表示，时间复杂度： O(n+e)。
可以用DFS求边数：因为每个点会且仅会被DFS一次，然后他的邻接点都会被遍历一遍，边数都会++，所以最后的E要/2
5.BFS
初始化队列，访问第一个顶点并标记，将第一个顶点入队
队列不空循环处理顶点：取队头元素u，队头元素出队，循环处理u每个未被访问的邻接点（访问、标记、入队）
邻接矩阵表示，时间复杂度：O(n^2)。 邻接表表示，时间复杂度： O(n+e)。
6.最小生成树
Prim（选点法）
任意取一个点，找连接它最小的一个边，然后融为一个整体往外找
时间复杂度：O(n^2) 求解稠密（边多）图
Kruskal算法 （选边法）
选最小边，且不能构成回路
时间复杂度：O(n^2) 求解稀疏（边少）图
7.最短路径
Dijkstra算法（从一个顶点到其余各个顶点的最短路径）
三行列表 第一行结点序号； 第二行是否最短（T/F）每次挑路径最小的 ； 第三行 路径小的更新大的。
时间复杂度为：O(n^2)
Floyd算法（每一对顶点之间的最短路径）
过程应该不考：初始表P0 然后迭代将1-...结点作为跳点 所在行列对角线元素不变 然后把可变的改了
时间复杂度：O(n^3)
8.有向无环图
拓扑排序
1.找到无入点的顶点
2.任选其中一点写入排序队列，然后擦去该点（如果让某点最快的话，排序尽量优先往前选入队）
① 若采用邻接矩阵存储图，算法的时间复 杂度为O(n^2)
② 若采用邻接表存储图，算法的时间复杂度为O(n+e)
关键路径
三种概念：
1.从源点到汇点的最长的路径。
2.所有最早开始时间和最晚开始时间相同的活动（弧）组成的路径。
3.最早发生时间和最迟发生时间相同的事件（顶点）及相应的活动（弧）组成的路径。
查找:
1.有序顺序表的二分查找（能够画出二分查找树，然后查找长度等就都能去求解了）
2.*树表查找——二叉排序树的构造，删除（顶替法等），查找长度为多少？（看在树的第几层）求平均查找长度 平衡二叉树——bf：1，0，-1；边调整（知道四种调整）边构建平衡二叉树，平衡：中序遍历序列和下标顺序相同
3.散列表的查找——散列函数：留数求余法；处理冲突的方法：线性探测（要会构造线性探测表，然后求平均查找长度），拉链法（也是会求平均查找长度）
1.概述
平均查找长度:
2.顺序表的查找
有序表的二分查找：先画出二分查找判定树；
二分查找判定树结点存储有序表元素的下标，它除了最后一层，就是满二叉树。
画法：先标范围后除2写下标，建立左右子树，循环执行以上操作。
层次数即比较次数即查找长度。
中序遍历序列与数组次序相同，二分查找不适用于链表。
3.索引表的查找
块间有序（可二分查找），块内无序（简单顺序查找）
4.二叉排序树——动态查找表
二叉排序树特点：中序序列是非降序列，其中每个结点的值大于其左子树中所有结点的值， 小于或等于其右子树中所有结点的值，而不仅仅是左孩子和右孩子的值！
插入：递归直到插入的结点为叶子结点
删除：
对于既有左孩子又有右孩子的结点，我们使用顶替法(或重接法)，将该结点的左子树最大值替代该结点或右子树最小值替代该结点
5.平衡二叉树
构建：聚焦于是哪三个结点出了问题，然后把中间数作为根，小的为左子树，大的为右子树，然后再按照之前的连接方式连剩下的结点，最后剩下的结点按照二叉排序树插入结点的方法插进去就行。
一定要从最高层结点开始找是否平衡，从不平衡结点沿着不平衡分支圈3个结点
6.散列表的查找
构造函数：留数求余法 H(k)= k % p k为元素值 p一定要小于等于数组规模 要不然H(kl)可能大于数组闺蜜
处理冲突：
(1)线性探测法：边构造边把查找次数写上去
(2)拉链法：ASL可能较小
排序：
（重点掌握交换排序和选择排序）一定要会如何手工去做。（快速排序要会排两趟，还要会画大根堆、小根堆，希尔排序的手工）
几个小问题： 哪些排序一趟能让至少一个元素在最终位置？时间复杂度，空间复杂度（比如快速排序）？稳定性？ 下面的表格务必记住！
1.插入排序——有序区、无序区（将无序区元素）——一趟不可以
直接插入排序（步长为1）、希尔排序（有步长）
2.交换排序（发现倒序就交换）——一趟可以
冒泡排序、快速排序
3.选择排序（在每一趟排序中，从待排序子表中选出关键字最小或最大的元素）——一趟可以
直接选择排序、堆排序（优先级队列用堆做成的）
4.归并排序(两个或两个以上的有序表合并，可以用来做外排序）——一趟不可以
自底向上
精彩文章
发表评论