导图社区 数据结构
- 33
- 0
- 0
- 举报
数据结构
这是一篇关于数据结构的思维导图，主要内容包括：排序，查找，矩阵、广义表，算法，基本数据结构，线性表，栈和队列，查找，串，树与二叉树，图。
编辑于2025-03-28 11:00:08- 计算机
- 数据结构
- 高中时候的十二月计划（11.29-12.31）
这是一篇关于十二月计划（11.29-12.31）的思维导图，主要内容包括：计划，目标，每日任务，调整。通过系统的学习和积累，提升各科成绩。
- 高中时候十一月计划11.1-11.30
这是一篇关于十一月计划11.1-11.30的思维导图，主要内容包括：计划，目标，每日任务（1 2），调整。通过系统的学习和积累，提升各科成绩，
- 高三的十月计划10.3-10.31
"十月冲刺计划：高效突破薄弱项，稳步提升各科成绩！我的1031031计划围绕三大核心：主科巩固与理科强化。数学主攻函数和不等式英语每天过单词 续写训练，目标120分物理专练步步高十个专题，冲刺75分生物通过试卷打卡突破80分。技术科目保持85分，语文利用零碎时间积累素材。每日固定任务包括国师第二阶段、英语3500词、续写素材收集，同时兼顾语文课、演讲等校园事务。时间管理上注重排队、早饭前等碎片化利用。
数据结构
社区模板帮助中心，点此进入>>
- 高中时候的十二月计划（11.29-12.31）
这是一篇关于十二月计划（11.29-12.31）的思维导图，主要内容包括：计划，目标，每日任务，调整。通过系统的学习和积累，提升各科成绩。
- 高中时候十一月计划11.1-11.30
这是一篇关于十一月计划11.1-11.30的思维导图，主要内容包括：计划，目标，每日任务（1 2），调整。通过系统的学习和积累，提升各科成绩，
- 高三的十月计划10.3-10.31
"十月冲刺计划：高效突破薄弱项，稳步提升各科成绩！我的1031031计划围绕三大核心：主科巩固与理科强化。数学主攻函数和不等式英语每天过单词 续写训练，目标120分物理专练步步高十个专题，冲刺75分生物通过试卷打卡突破80分。技术科目保持85分，语文利用零碎时间积累素材。每日固定任务包括国师第二阶段、英语3500词、续写素材收集，同时兼顾语文课、演讲等校园事务。时间管理上注重排队、早饭前等碎片化利用。
- 相似推荐
- 大纲
数据结构
排序
插入类排序
直接插入排序
时间
最好O(n)最差O(n2)平均O(n2)
空间
O(1)
依次将每个元素插入到前面合适的位置（扑克牌整理）
稳定
折半插入排序（二分法）
时间
O(nlog2n)最差O(n2)平均O(n2)
空间
O(1)
稳定
希尔排序（缩小增量排序）
不断缩小增量去使整个序列更有序最终用直接插入排序
时间
最好O(n)最差O(n2)平均O(n1.3)
空间
O(1)
不稳定
交换类排序
冒泡排序
时间
最好O(n)最差O(n2)平均O(n2)
空间
O(1)
稳定
快速排序
时间
最好O(nlog2n)最差O(n2)平均O(nlog2n)
空间
最好O(nlog2n)最差O(n)平均O(nlog2n)
不稳定
取其中一个数n作为枢轴，将两边数分为一边比n小一边比n大，交换好后再重复此过程
选择类排序
简单选择排序
不断选出最小数填到新序列
时间
O(n2)
空间
O(n1)
堆排序
建堆，从最后一个非叶节点开始依次向下调整。排序，每轮堆顶换到最后，向下调整新的堆顶（n-1）轮
时间
O(nlog2n)
空间
O(1)
不稳定
归并排序
最开始每个元素单独作为一个子序列，每轮对相邻子序列两两归并，直至归并成一个序列
时间
O(nlog2n)
空间
O(n)
稳定
基数排序
逐位进行分配和收集，总共排d轮
时间
O(d×(n+r))
d是最大数的位数，n是要排的总个数，r是基数/桶的个数
空间
O(r)
稳定
外部排序
原理
这里的外存是指磁盘（机械硬盘）。操作系统以“块”为单位对磁盘存储空间进行管理，如：每块大小1KB。各个磁盘块内存放着各种各样的数据。 若想修改磁盘中某个磁盘块的数据，就需要将数据读到内存中，也就是在内存中开辟一块内存空间（缓冲区）用于存放磁盘块的数据（缓冲区的大小和磁盘块的大小可以保持一致）。并将要修改的磁盘块的数据读到内存中相应位置。磁盘的读/写以"块"为单位，数据读入内存后才能被修改，修改完了再写回磁盘中。 简单来说磁盘中存储的数据很多，容量很大，而内存的容量很小，此时用到外部排序（主要用到归并排序）
例子
时间开销
读写外存的时间
读写外存的时间和读写磁盘的次数是成正比的。在进行内部排序时，读/写磁盘的次数分别为16次（总共16个磁盘块），总共32次读写；3趟归并中，每一次都要读/写磁盘16次（读入内存16次，写回磁盘16次）。所以： 读写磁盘的次数=32+32*3=128次。
内部排序的时间（生成初始归并段的时间）
内部归并的时间（对两块有序的"归并段"进行归并的时间）
优化时间
k路归并算法
这里可以k个归并段一起
例子中如果用四路归并，读写次数为32+32*2=96次
采用多路归并可以减少归并趟数，从而减少磁盘I/O(读写)次数。
缺点
① k路归并时，需要开辟k个输入缓冲区，内存开销增加。（典型的空间换时间） ② 每挑选一个关键字需要对比关键字(k-1)次，内部归并所需时间增加。针对这个问题可以使用“败者树”减少关键字比较次数，后面会讲。
减少初始归并段数量
置换-选择排序
减少更多的初始归并段
最佳归并树
构建赫夫曼树来计算最少I/O次数（WPLmin×2），其中Rn里面的数字表示这个归并段里面有多少元素
最佳归并树 WPLmin=(1+2)*4+2*3+5*2+6*1 = 34 读磁盘次数=写磁盘次数=34次；总的磁盘I/O次数=68
多路归并
k叉的最佳归并树一定是一棵严格的 k 叉树,即树中只包含度为k、度为 0 的结点
例子
WPLmin=(2+3+6)*3+(9+12+17+24+18)*2+30*1=223 归并过程中 磁盘I/O总次数=446次
特殊情况
初始归并段的数量无法构成严格的k叉归并树，则需要补充几个长度为 0 的“虚段”
败者树
使k个归并段中挑出最小关键字所需要的关键字对比次数更少
对于k 路归并第一次构造败者树需要对比关键字 k-1次；有了败者树，选出最小元素，只需对比关键字log2k次。
补充
注
这里的空间指的都是辅助空间复杂度
m个初始归并段进行k路归并，归并趟数为 logkm
记不清复杂度看p267乱七八糟口诀
查找
定义
给定一个值k，在含有n个记录的表中找出关键字等于k的记录。若找到，则查找成功，返回该记录的信息或者该记录在表中的位置；否则查找失败，返回相关的提示信息
采用什么方法的影响因素
使用哪种数据结构查找表，即查找表中的记录是按照什么方式组织的
查找表中关键词的次序，即对无序集合查找还是对有序集合查找
最终会影响ASL（平均查找长度）
n是查找表中记录的个数
pi是查找第i个记录的概率
考研题一般取1/n
ci是找到第i个记录所需要进行比较的次数，即查找长度
方法
顺序查找法
按顺序扫描
ASL
(1+n)/2
时间
O(n)
折半查找（二分查找）
条件
必须是数组（顺序表）
必须有序
例子（ASL）
分块查找
ASL
确定查找元素在哪一块，再在块内查找
树形查找
二叉排序树（BST）
定义
二叉排序树或者是一棵空树，或者是具有下列性质的二叉树。 ①若它的左子树非空，则左子树上所有结点的值均小于根节点的值； ②若它的右子树非空，则右子树上所有结点的值均大于根结点的值； ③它的左右子树也分别是二叉排序树。
删除
没有孩子
直接删除
只有左或者右子树
直接代替
左右子树都有
直接后继（或前驱）代替，然后删除（转化为前两种情况）
平衡二叉树（AVL）
失衡
构建和插入时观察是否失衡，若有多处失衡先调整最近的
删除时需要重复调整失衡依次对祖先进行检查
平衡因子
左子树高度减去右子树高度
任一左右子树高度相差绝对值不超过1
查询更高效
红黑树
特点
左根右
前提是二叉搜索树（左<根<右）
根叶黑
根和叶子（NULL）都是黑色
不红红
不存在连续的两个红色节点
黑路同
任一条路径上的黑色节点数相同
任一节点到叶所有路径黑结点数量相同
任一左右子树高度相差不超过两倍
插入和删除更高效
插入
插入节点默认为红色
且只可能违反个根叶黑或者不红红
若插入的节点是根节点
则直接变黑
插入节点的叔叔是红色
叔父爷变色，爷变插入节点，继续判定爷爷是否违反性质
插入节点的叔叔是黑色(注意空节点)
(LL,RR,LR,RL）旋转，然后对旋转点和中心点变色
注意RL和LR变色
删除（复习时候完善）
容易破坏黑路同
没有孩子
红色节点
直接删除
黑色节点
只有左子树/只有右子树
直接代替后变黑
B树
特点
平衡
所有叶节点都在同一层
有序
节点内有序
任意元素的左子树都小于它，右子树都大于它
多路
对于m阶B树的节点
m/2向上取整
例子
5阶B树
所有节点的关键字都有指向对应记录的指针
顺序查找或范围查找只能中序遍历，效率低
插入
先查找到插入的位置进行插入（一定在叶节点插入）
若出现上溢出则需要将中间元素（第m/2个）上移，两边元素分裂，直至无上溢出
删除
删除非叶节点最终都转换成删除叶节点元素
没有下溢出无需调整
下溢出
兄弟够借：借
父下来，兄上去
兄弟不够借：合并
父下移到左，然后右并过来
可能导致父结点下溢出
B+树
特点
元素个数只能等于分支数
叶结点包含全部关键字及指向相应记录的指针，非叶结点只作索引
兼顾顺序查找和随机查找，还可方便地进行范围查找
例子
散列表
特点
可以根据数据元素的关键字计算出它在散列表中的存储地址 散列函数（哈希函数)︰Addr=H(key)建立了“关键字”→“存储地址”的映射关系
相关概念
冲突（碰撞）
在散列表中插入一个数据元素时，需要根据关键字的值确定其存储地址，若该地址已经存储了其他元素，则称这种情况为“冲突(碰撞)”
同义词
若不同的关键字通过散列函数映射到同一个存储地址，则称它们为“同义词”
待解决的问题
如何减少冲突
构造更合适的散列函数
散列函数的构造
除留余数法
H（key）=key%p
p通常是不大于散列列表表长的最大质数
较为通用，关键字是整数即可
直接定址法
H（key）=a*key+b
a和b是常数
关键字分布基本连续
数字分析法
选取数码分布较为均匀的若干位作为散列地址
关键字集合已知，且关键字的某几个数位码分布均匀
平方取中法
计算关键字的平方，取中间几位作为散列地址
关键字的每位取值都不够均匀
注意点
如何处理冲突
拉链法
开放定址法
找个空位置给它
矩阵、广义表
矩阵
特殊矩阵
相同的元素或者零元素在矩阵中的分布存在一定规律的矩阵，反之称为稀疏矩阵
稀疏矩阵
顺序存储
三元组表示法
行下标、列下标、值
若要计算内存，记得加上总元素和总行数列数所占内存
伪地址表示法
链式存储
邻接表表示法
十字链表表示法
广义表
相关概念
表元素可以是原子或者广义表的一种线性表的拓展结构
长度
表中最上层元素个数
深度
表中括号的最大层数
例如((d,e),(b,(c,d)))的深度为3
表头和表尾
当广义表非空时，第一个元素为广义表的表头，其余元素组成的表是广义表的表尾
头尾链表存储结构
原子节点
标记域
数据域
广义表节点
标记域
头指针域
尾指针题
标记域用于区分，0是原子节点，1是广义表节点
头指针域指向原子节点或广义表节点
尾指针域为空或者指向本层中下一个广义表节点
扩展线性表存储结构
原子节点比头尾链表存储结构多了个尾指针域，其他不变
算法
时间复杂度
T(n) = O( f(n) )
把程序化成数学式子，取最高次项
算法中基本操作的执行次数
空间复杂度
存储空间的度量
概念
由基本运算及规定的运算顺序所构成的完整的解题步骤，或者看作按照要求设计好的有限的确切的计算序列
特性
有穷性
确定性
输入
输出
可行性
设计目标
正确性、可读性、健壮性、高效率与低存储量
注
一个算法应该是问题求解步骤的描述
基本数据结构
逻辑结构
线性结构
除第一个元素只有一个“后继”和最后一个元素只有一个“前驱”，其它每个元素只有一个“前驱”元素和一个“后继”元素
非线性结构
树形结构
图形结构
是对数据之间关系的描述，同一种逻辑结构可以有很多存储结构
存储结构（物理结构）
顺序存储方式
数组
顺序表
链式存储方式
链表
索引存储方式
数据库索引
散列存储方式
哈希表
对数据的运算
概念
指互相之间存在一种或多种特定关系的数据元素的集合
注
为什么顺序表不属于逻辑结构？
因为它不仅包含了数据元素之间的逻辑关系，还包含了数据元素在计算机中的存储方式。逻辑结构和存储结构是数据结构设计中的两个不同层次，逻辑结构关注数据元素之间的关系，而存储结构关注数据元素在计算机中的存储方式。顺序表作为一种数据结构，既包含了逻辑结构的特性，也包含了存储结构的特性。
线性表
具有相同特性数据元素的一个有限序列
所含个数叫做线性表的长度
存储结构
顺序表
重点掌握查找、插入、删除
特性
随机访问特性
占用连续的存储空间
做插入操作时要移动多个元素
链表
特性
不支持随机访问
节点存储空间较顺序表稍低一些
支持存储空间动态分配
进行插入操作无需移动元素
类型
单链表
双链表
循环单链表
循环双链表
静态链表
分配一整片连续的内存空间来存储结点
两者的比较
基于空间的比较
存储密度
节点值域所占的存储量/节点结构所占的存储总量
顺序表存储密度=1
链表的存储密度<1（因为节点中有指针域）
存储分配的方式
顺序表的存储空间是一次性分配的，链表的存储空间是多次分配的
基于时间的比较
存取方式
顺序表可以随机存取
链表只能顺序存取
插入/删除时移动元素的个数
顺序表平均需要移动近一半元素
链表不需要移动元素，只需要修改指针
栈和队列
栈
栈是一种只能在一端进行插入或删除操作的线性表
存储结构
顺序栈
链式栈
数学性质
Catalan()
应用
函数调用栈
在程序执行过程中，函数调用是通过栈来实现的。每当一个函数被调用时，它的局部变量、参数和返回地址等信息都会被压入调用栈中。当函数执行完毕后，这些信息会从栈中弹出，控制流回到调用该函数的地方。
表达式求值
在编译器和解释器中，表达式求值通常使用栈来实现。例如，在计算算术表达式时，可以使用栈来保存操作数和操作符，并按照运算的优先级进行求值。
括号匹配
在解析包含括号的字符串（如数学表达式或代码块）时，可以使用栈来检查括号是否匹配。每遇到一个左括号就将其压入栈中，每遇到一个右括号就从栈顶弹出一个元素并检查是否匹配。如果最后栈为空，则说明所有括号都匹配成功。
浏览器的前进后退功能
在浏览器中，用户可以通过点击前进和后退按钮来浏览之前访问过的网页。这些网页实际上被保存在一个栈中，点击前进按钮相当于执行出栈操作，点击后退按钮相当于执行入栈操作。
递归调用的辅助工具
递归是算法中常用的一种技术手段，而栈则是递归实现的幕后英雄。在递归过程中，每一层递归调用都会将当前的状态（如参数、局部变量等）压入调用栈中，待子问题解决后再从栈中弹出状态继续执行。
撤销操作（Undo）
在许多应用程序中，如文本编辑器、图像处理软件等，都提供了撤销操作的功能。栈可以用来实现这个功能。每当用户执行一个操作时，将该操作的信息压入栈中。当用户需要撤销操作时，从栈中弹出一个操作信息，并恢复到该操作之前的状态。
栈在编译器设计中的应用
在编译器设计中，栈被用来实现语法分析、词法分析等功能。例如，在语法分析过程中，栈可以用来存储语法树的节点信息，以便在后续阶段生成目标代码。
栈在操作系统中的应用
在操作系统中，栈被用来实现函数调用、任务调度等功能。例如，在任务调度过程中，操作系统会将每个任务的执行信息（包括任务状态、寄存器值等）存储在栈中。当任务被切换时，这些信息会从栈中弹出并恢复到相应的寄存器中。
队列
可以进行插入的一段叫做队尾，可进行删除的一端叫做队头
存储结构
顺序栈
链式栈
元素个数
(rear-front+maxSize)%maxSize
共享栈和双端队列
共享栈主要是为了提高内存利用率和减少溢出可能性而设计的，两个栈底分别设置在一片连续的存储空间的双端，当两个栈的栈顶相遇时才产生溢出
双端队列
拓展
抽象数据类型（AbstractData Type,ADT）
p76例题
查找
定义
给定一个值k，在含有n个记录的表中找出关键字等于k的记录。若找到，则查找成功，返回该记录的信息或者该记录在表中的位置；否则查找失败，返回相关的提示信息
采用什么方法的影响因素
使用哪种数据结构查找表，即查找表中的记录是按照什么方式组织的
查找表中关键词的次序，即对无序集合查找还是对有序集合查找
最终会影响ASL（平均查找长度）
n是查找表中记录的个数
pi是查找第i个记录的概率
考研题一般取1/n
ci是找到第i个记录所需要进行比较的次数，即查找长度
方法
顺序查找法
按顺序扫描
ASL
(1+n)/2
时间
O(n)
折半查找（二分查找）
条件
必须是数组（顺序表）
必须有序
例子（ASL）
分块查找
ASL
确定查找元素在哪一块，再在块内查找
树形查找
二叉排序树（BST）
定义
二叉排序树或者是一棵空树，或者是具有下列性质的二叉树。 ①若它的左子树非空，则左子树上所有结点的值均小于根节点的值； ②若它的右子树非空，则右子树上所有结点的值均大于根结点的值； ③它的左右子树也分别是二叉排序树。
删除
没有孩子
直接删除
只有左或者右子树
直接代替
左右子树都有
直接后继（或前驱）代替，然后删除（转化为前两种情况）
平衡二叉树（AVL）
失衡
构建和插入时观察是否失衡，若有多处失衡先调整最近的
删除时需要重复调整失衡依次对祖先进行检查
平衡因子
左子树高度减去右子树高度
任一左右子树高度相差绝对值不超过1
查询更高效
红黑树
特点
左根右
前提是二叉搜索树（左<根<右）
根叶黑
根和叶子（NULL）都是黑色
不红红
不存在连续的两个红色节点
黑路同
任一条路径上的黑色节点数相同
任一节点到叶所有路径黑结点数量相同
任一左右子树高度相差不超过两倍
插入和删除更高效
插入
插入节点默认为红色
且只可能违反个根叶黑或者不红红
若插入的节点是根节点
则直接变黑
插入节点的叔叔是红色
叔父爷变色，爷变插入节点，继续判定爷爷是否违反性质
插入节点的叔叔是黑色(注意空节点)
(LL,RR,LR,RL）旋转，然后对旋转点和中心点变色
注意RL和LR变色
删除（复习时候完善）
容易破坏黑路同
没有孩子
红色节点
直接删除
黑色节点
只有左子树/只有右子树
直接代替后变黑
B树
特点
平衡
所有叶节点都在同一层
有序
节点内有序
任意元素的左子树都小于它，右子树都大于它
多路
对于m阶B树的节点
m/2向上取整
例子
5阶B树
所有节点的关键字都有指向对应记录的指针
顺序查找或范围查找只能中序遍历，效率低
插入
先查找到插入的位置进行插入（一定在叶节点插入）
若出现上溢出则需要将中间元素（第m/2个）上移，两边元素分裂，直至无上溢出
删除
删除非叶节点最终都转换成删除叶节点元素
没有下溢出无需调整
下溢出
兄弟够借：借
父下来，兄上去
兄弟不够借：合并
父下移到左，然后右并过来
可能导致父结点下溢出
B+树
特点
元素个数只能等于分支数
叶结点包含全部关键字及指向相应记录的指针，非叶结点只作索引
兼顾顺序查找和随机查找，还可方便地进行范围查找
例子
散列表
特点
可以根据数据元素的关键字计算出它在散列表中的存储地址 散列函数（哈希函数)︰Addr=H(key)建立了“关键字”→“存储地址”的映射关系
相关概念
冲突（碰撞）
在散列表中插入一个数据元素时，需要根据关键字的值确定其存储地址，若该地址已经存储了其他元素，则称这种情况为“冲突(碰撞)”
同义词
若不同的关键字通过散列函数映射到同一个存储地址，则称它们为“同义词”
待解决的问题
如何减少冲突
构造更合适的散列函数
散列函数的构造
除留余数法
H（key）=key%p
p通常是不大于散列列表表长的最大质数
较为通用，关键字是整数即可
直接定址法
H（key）=a*key+b
a和b是常数
关键字分布基本连续
数字分析法
选取数码分布较为均匀的若干位作为散列地址
关键字集合已知，且关键字的某几个数位码分布均匀
平方取中法
计算关键字的平方，取中间几位作为散列地址
关键字的每位取值都不够均匀
注意点
如何处理冲突
拉链法
开放定址法
找个空位置给它
串
注意
str="abcd"实际上有"/0"作结束的标记，所以此数组str的长度为5，串str长度为4
空格串不是空串
概念
串是由零个或多个字符组成的有限序列。
子串
串中任意连续的字符组成的子序列
主串
包含子串的串
基本操作
赋值
取串长度
串比较
串连接
求子串
串清空
串的模式匹配算法
对一个串中某子串的定位操作称为串的模式匹配，其中待定位的子串称为模式串
简单模式匹配算法
KMP算法
难点需再仔细看一遍
树与二叉树
树
树的基本术语
节点
节点的度
节点拥有的子树个数或者分支的个数
树的度
树中各节点度的最大值
叶子节点
终端节点
度为0的节点
非终端节点
分支节点
度不为0的节点
孩子
双亲
兄弟
祖先
从根到某节点的路径上的所有节点，都是这个节点的祖先
子孙
以某节点为根的子树的所有节点
层次
从根开始，根为第一层
树的高度
树的深度
总共多少层
节点的深度（高度）
堂兄弟
双亲在同一层的节点
有序树
树中节点的子树从左到右有次序不能交换
无序树
树中节点的子树无顺序，可任意交换
丰满树
理想平衡树
要求除最底层外，其它层都是满的
森林
若干棵互不相交的树的集合
树的存储结构
顺序存储结构
最适合完全二叉树
链式存储结构
二叉树
主要性质
非空二叉树上的叶子节点数为双分支节点数加1
n0=n2+1
Catalan()
通过节点数n可知能构成多少种二叉树
总边数=总结点数-1
e=N−1
根据这个可以求不同度的个数
例子
遍历算法
先序遍历
中序遍历
后序遍历
逆后续遍历是先序遍历中对左右子树遍历顺序交换所得到的结果p156
层次遍历
线索二叉树
特殊情况
完美二叉树(Perfect Binary Tree)
一个深度为k(>=-1)且有2^(k+1) - 1个结点的二叉树称为完美二叉树。 (注： 国内的数据结构教材大多翻译为"满二叉树")。
完全二叉树(Complete Binary Tree)
完全二叉树从根结点到倒数第二层满足完美二叉树，最后一层可以不完全填充，其叶子结点都靠左对齐。
完满二叉树(Full Binary Tree)
所有非叶子结点的度都是2。（只要你有孩子，你就必然是有两个孩子。）
转换
树转换为二叉树
兄弟连线，只留左孩线，去掉右孩线（父子线）
二叉树转换为树
左孩右右连双亲，去掉原来右孩线。
若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子....沿分支找到的所有右孩子，都与p的双亲用线连起来
森林转化为二叉树
先将森林中的树转化为二叉树，再把它们的根连接
森林的先序遍历对应二叉树的先序遍历
森林的后序遍历对应二叉树的中序遍历
森林的遍历都是从第一棵树开始，先把第一棵树遍历完再进行下一棵树
二叉树转化为森林
断开根的所有右子树，再将其化为树
应用
二叉排序树与平衡二叉树
详见排序
赫夫曼树与赫夫曼编码
赫夫曼树（最优二叉树）
特点
带权路径最短
权值越大的节点离根节点越近
树中没有度为1的节点称之为正则（严格）二叉树
相关概念
路径
从树中一个结点到另一个节点的分支所构成的路线
路径长度
路径上的分支数目
树的路径长度
根到每个节点的路径长度之和
带权路径长度
节点具有权值，从该节点到根之间的路径长度乘以节点的权值，就是该节点的带权路径长度
树的带权路径长度（WPL）
树中所有叶子节点的带权路径长度之和
构造方法
输入：n 和n 个权值 {w1 , w2 , …, wn } 输出：赫夫曼树 步骤： 1.根据给定的 n 个权值 {w1 , w2 , …, wn }，构造 n 棵二叉树的集合 F = {T1 , T2 , … , Tn }，其中每棵二叉树中均只含一个带权 值为 wi 的根结点，其左、右子树为空树 2.在F 中选取其根结点的权值为最小和次小的两棵二叉树， 分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和 3.从F中删去这两棵树，同时加入刚生成的新树 4.重复 2 和 3 两步，直至 F 中只含一棵树为止
例子
输入：已知n=5，权值集合 W={ 5, 6, 2, 9, 7 }。
赫夫曼编码
一种前缀码（没有任何码字是其他码字的前缀）
赫夫曼二叉树
特点
每片叶子结点都包含⼀个字符
从结点到其左孩子的路径上标记0
从结点到其右孩子的路径上标记1
为了节省空间，越常用的字符离根越近
从根结点到包含字符的叶⼦结点的路径上获得的叶结点的编码 编码均具有前缀属性
例子
赫夫曼n叉树
赫夫曼二叉树是赫夫曼n叉树的一种特例， 对于结点数目大于等于2的待处理序列，都可以构造赫夫曼二叉树，但却不一定能构造赫夫曼n叉树。当发现无法构造时，需要补上权值为0的结点让整个序列凑成可以构造赫夫曼n叉树的序列。
每次挑选权值最小的三个节点构造一棵三叉树
节点数公式
m=2n−1，其中m m为总的节点数，n为叶子节点数。
图
图的基本概念
图
由节点的有穷集合V和边的集合E组成。
为了和树区分，在图中经常把结点称之为顶点，边是顶点的有序偶对。若两个顶点存在一条边，则表示这两个顶点存在相邻关系
有向图和无向图
弧
在有向图中把边称为弧，含箭头的一端称为弧头，另一端称为弧尾，记作<vi，vj>，它表示从顶点vi到定点vj有一条边
顶点的度、入度和出度
在无向图中，边记为（vi，vj），它等价于在有向图中存在<vi，vj>和<vj，vi>两条弧。与顶点v相关的边的条数称为定点v的度。如上图定点D的度为2.在有向图中，指向顶点v的弧的条数称为定点v的入度，由定点v发出的弧的条数称为顶点v的出度。上图顶点C的入度为0，出度为2
有向完全图和无向完全图
有向完全图：边的数目为n(n-1)
无向完全图：边的数目为n(n-1)/2
n为顶点数
路径
相邻顶点序偶所构成的序列
路径长度
一条路径上边或弧的数量
简单路径
序列中顶点不重复出现的路径
回路
若一条路径中第一个顶点和最后一个顶点相同，则这条路径是一条回路
连通
如果vi到vj有路径，则称vi和vj两顶点连通
连通图和连通分量
图中任意两个顶点都连通的称为连通图
连通分量
图无向图中的极大连通子图。（子图必须是连通的且含有极大顶点数）。图1有两个连通分量
强连通图和强连通分量
在有向图中，若从vi到vj有路径，则称从vi到vj是连通的。如果对于每一对顶点vi和vj，从vi到vj和从vj到vi都有路径，则称为该图为强连通图，否则就将其中的极大强连通子图称为强连通分量
权
图中每条边都可以附有一个对应的数，这种和边相关的数称为权。
网（带权图）
边上带有权的图
存储结构
有多种但考研只用到以下两种
邻接矩阵（顺序存储结构）
性质
对于一个含有n个顶点，m条边的无向图，其邻接矩阵中元素为零的个数为n*n-2m
无向图的邻接矩阵一定是对称矩阵，关于对角线对称，且主对角线一定为零（只针对简单图），而有向图的邻接矩阵不一定是对称矩阵；另外，0若一个图的邻接矩阵是对称的，则它可以是无向图或有向图。
由于无向图的邻接矩阵存在对称关系，其上三角和下三角的相同的，所以当在存储邻接矩阵时，除了对角线都为0以外，其实只需要存储上三角或下三角的数据，故只需要n(n-1)/2个存储空间。 只存储上三角或下三角的数据，即1+2+3+……+(n-1)=n(n-1)/2。
vi的度
有向图中
出度
邻接矩阵的第i行非零元素个数
入度
邻接矩阵的第i列非零元素个数
无向图中
顶点vi的度为其邻接矩阵中第i行和第i列的非零元素的个数之和
若邻接矩阵为对称矩阵，当图为有向图时，图的弧的数目等于邻接矩阵中非零元素的个数；当为无向图，则图的边数等于邻接矩阵中非零元素的一半。
表示
邻接表（链式存储结构）
表示
邻接多重表
图的遍历算法操作
深度优先搜索遍历（DFS）
从图中一个未访问的顶点V开始，沿着一条路一直走到底，如果到达这条路尽头的节点 ，则回退到上一个节点，再从另一条路开始走到底…，不断递归重复此过程，直到所有的顶点都遍历完成。
广度优先搜索（BFS）
从某个顶点V出发，访问该顶点的所有邻接点V1，V2..VN，从邻接点V1，V2...VN出发，再访问他们各自的所有邻接点，重复上述步骤，直到所有的顶点都被访问过
最小（代价）生成树
普里姆算法
从已知顶点找附近最小权值的边
O(n2)
克鲁斯卡尔算法
通过权值排序边，不断选择权值最小的边（不构成环的情况下）
所有边权值都不相等时，有唯一最小生成树
最短路径
迪杰斯特拉算法
每次选距离a最近的点，然后更新
求一个点到其他点的最短路径
O(n2)
弗洛依德算法
求任意两点间的最短路径
O(n3)
拓扑排序
AOV网
以顶点表示活动、以弧表示活动的先后次序且没有回路的有向图
如果有回路的话就会卡住
关键路径
AOE网
和AOV网一样都是有向无环图
AOE的边表示活动，弧有权值，边表示活动持续时间；顶点表示事件，事件是图中新活动开始或者旧活动结束的标志。AOE网的顶点表示活动，边无权值，边表示活动之间的先后关系
对于一个表示工程的AOE网，只存在一个入度为0的顶点，称为源点，表示整个工程的开始；也只存在一个出度为0的顶点，称为汇点，表示整个工程的结束