数据结构408

计算机考研必收藏!一张思维导图带你学懂计算机专业重要的专业基础课-数据结构树与二叉树知识点汇总。该导图详细著明了树的基本概念、二叉树、树与二叉树的相互转化、树与二叉树的应用、应用知识点。如果有帮到你，不妨点个赞吧!

数据结构

• 概要
  • 逻辑结构
    • 线性结构
      • 一般线性表
      • 受限线性表
        • 栈
        • 队列
      • 推广线性表
        • 数组
        • 广义表
    • 非线性结构
      • 集合
      • 字典
      • 树形结构
      • 图状结构
  • 存储结构（物理结构）
    • 顺序存储
    • 链式存储
    • 索引存储
    • 散列存储
  • 存取方式
    • 随机存取
    • 顺序存取
  • 数据运算
    • 数据元素
      • 感觉是一个结构
    • 数据项
      • 不可分割的最小单位
    • 数据对象
      • 同一类数据元素的集合
        • 例如整数集合
    • 数据类型
    • 抽象数据类型
• 线性表
  • 顺序存储
  • 链式存储
• 受限线性表
  • 栈
    • 子主题
  • 队列
    • rear进front出
    • 顺序队列
      • 队空：front==rear
      • 队满：|rear-front|==maxsize
    • 循环队列
      • 队空：front==rear
      • 队满
        • 牺牲一个单元法
          • 队满
            • (rear+1)%maxsize==front
          • 队长
            • (rear-front+maxsize)%maxsize
        • 增加长度记录变量
        • 增加插入位标记
      • 入队
        • 顺序法：rear=(rear+1)%maxsize
        • 链表法：s=new LinkNode(data); rear->next=s; rear=s
      • 出队
        • 顺序法：front=(front+1)%maxsize
        • 链表法：front->next = front->next->next
    • 存储方式
      • 顺序存储
      • 带尾指针的带头结点单链表
  • 应用
    • 后缀表达式
    • 矩阵压缩
      • 对称矩阵
      • 三角矩阵（包括对角线）
      • 稀疏矩阵
• 树型结构
  • 基本概念
    • 定义
      • 有且只有一个根
        • 根可以为空，称为空树
      • 除根外其余结点是互不相交有限集合，并且都是树
    • 概念
      • 1. 树度
        • 最大结点度数，最多边数的结点对应的边数，是存在的
      • 2. 树高度/深度
        • 最大结点深度/高度（从1开始计算）
      • 3. 结点
        • 度数
          • 结点子结点的个数
        • 层次/深度
          • [树根,自己]经过的层数
        • 高度
          • [叶子，自己]经过的层数
      • 4. 路径
        • 结点到一个结点的子结构
        • 路径长度
          • 路径上边的个数
        • 整树路径长度
          • 树根到每个结点的路径总和
        • 带权路径长度
          • 从树根到所有叶结点的带权路径长度之和
      • 5. 有序/无序
        • 兄弟结点顺序敏感/不敏感
        • 只有一个孩子时候不区分顺序
    • 性质
      • 结点数 n = ∑结点度数 + 1
        • 记忆n=∑d + 1
      • 第i层结点数 n = d^(i-1)
      • h层结点数 n(h)= (d^h-1)/(d-1)
      • n个结点最低高度 = ⌈log(d, n(d-1)+1)⌉
      • d为树度，h为树层，n为结点数， 在任何非叶子结点度数相同下
    • 存储结构
      • 顺序表
      • 链表
        • 注意：n个结点的二叉链表树含有n+1个空链域
    • 基本操作
      • 1. 建树
        • 由序列求二叉树
          • 仅知道先序后序无法计算
      • 2. 查找
      • 3. 增加
      • 4. 删除
      • 5. 遍历
    • 线索化
      • 前序线索树
      • 中序线索树
      • 后序线索树
    • 应用
      • 二叉查找树
        • ACM
          • 卡特兰数计算
            • 给定n个元素序列的进栈出栈的不同序列数
            • 给定先序序列的二叉树形态数目
            • 给定中序序列的二叉树形态数目
        • 插入
        • 查找
        • 删除
          • 叶子结点
          • 度1结点
          • 度2结点
            • 默认右子树中序第一孩子替补
      • 平衡二叉树
        • 定义
          • 任意结点的左右子树高度差不超过1的二叉查找树
            • 左边高度差为正，右边高度差为负
          • 判断方法
            • 判断左树是否平衡
            • 判断右树是否平衡
            • 判断根节点是否平衡
        • 查找
        • 插入
          • LL右旋
          • RR左旋
          • LR左右旋
          • RL右左旋
          • 正则右旋，负则左旋 复杂先对齐正负
        • 删除
        • 深度h的最少结点数
          • n(0)=0, n(1)=1, n(2)=2 n(h) = 1+ n(h-1) + n(h-2)
      • 哈夫曼树
        • 应用
          • 哈夫曼编码
            • 唯一性
            • 最短性
            • 深度为h的哈夫曼树最大编码长度为h-1
            • 平均长度=总长度/总次数
        • 特性
          • 带权路径长度最短
          • 仅含有最大度的非叶子结点
          • 形态不唯一
  • 二叉树
    • 特点
      • 总分支树= 总结点数-1
      • 有序树
      • 非空二叉树叶子结点数= 双分支结点数+1
      • 树拓展：叶子结点数= 1+n2+2*n3…+ （m-1 ）nm
    • 特殊
      • 满二叉树
        • 完美三角形
      • 完全二叉树
        • 叶子层可以不满
      • 二叉查找树
      • 平衡二叉树
    • 完全二叉树
      • 叶子结点数 = d为2的结点数 + 1
        • 记忆n(d0) = n(d2) + 1
      • 第h层最多有2^(h-1)个结点（h>=1）
        • 记忆n(h) = 2^(h-1)
      • h层最多有2^h - 1个结点(h>=1)
        • 记忆n([0,h]) = 2^h-1
      • 有n结点完全二叉树h = ⌊log(2, n) ⌋+ 1
        • 记忆h = ⌈log(2,n+1)⌉
    • 满二叉树
      • 叶子结点数 = (n+1)/2
        • 记忆n0 = (n+1)/2
      • 第h层必有2^(h-1)个结点（h>=1）
      • h层必有2^h - 1个结点(h>=1)
      • 有n结点满二叉树h = log(2, n+1)
  • 树森林
    • 森林定义
      • 独立的树的集合
    • 树存储结构
      • 双亲表示法
        • 根用-1标记，属于顺序存储
      • 孩子表示法
        • 对比k叉链表，结点使用链表表示孩子，由于使用链式存储， 优点节省空间，缺点访问速度受限
      • 孩子兄弟表示法
        • 顺序+链式存储
      • 2叉链表
        • 空链域个数=树的度数
    • 森林存储结构
      • 二叉链表
    • 森林逻辑结构
      • 一棵棵独立的树
    • 基本操作
      • 转换
        • 普通树->二叉树
          • 记忆兄弟相连留长子
            • 兄弟变右孩
            • 右孩变左孩
        • 二叉树->普通树
          • 记忆右属升级自留级
            • 右孩变兄弟
            • 左孩变右孩
        • 二叉树->森林
          • • 森林入口转换为第一棵树的根， 森林左子树为第一棵树左子树， 右子树相离，独立成林
        • 森林->二叉树
          • • 第一棵树树根为森林入口， 第一棵树左子树为森林入口左子树， 其余的树根相连，右链接到森林入口
      • 遍历
        • 先序遍历森林
        • 中序遍历森林
    • 应用
      • 并查集
• 排序算法
  • 概念
    • 稳定性
      • 键相同元素排序前后顺序是否一样
    • 内部排序
      • 内存上的排序
    • 外部排序
      • 内存外存上的排序
    • 一趟排序
      • 尚未确定最终位置的元素处理一次
  • 冒泡排序
    • 动画展示
    • 如果一趟排序没有发生交换，则表明已经有序，所以最好是O(n)
  • 插入排序
    • 动画展示
    • 折半插入排序
      • 选择插入时候使用二分查找
    • 每次找已排序段找适合的位置插入 着重点是“插”
  • 选择排序
    • 动画展示
    • 特点
      • 复杂度一致
    • 每次在没排序段找到最值放在前面 着重点是“选”
  • 希尔排序
    • 动画展示
  • 归并排序
    • 动画展示
    • 就是空间不太友好
  • 快速排序
    • 动画展示
    • 局部性排序，数据量大下比堆排序和归并排序优秀
  • 堆排序
    • 动画展示
    • 建堆时间复杂度O(n)
    • 插入删除复杂度O(logn)
    • 建堆：从低往上，每次调后都有递归
  • 基数排序
    • 记忆：位数上的排序
  • 外部排序
  • 应用
  • 比较
• 查找算
  • 概念
    • ASL平均查找长度
      • ASL= ∑P*C
        • ∑范围是n，即表长
        • Pi是查找第i个元素的概率
        • Ci是找到第i个元素比较次数
  • 线性结构
    • 顺序查找
      • 无序顺序查找
        • ASL= (n+1)/2
      • 有序顺序查找
        • ASL= n/2+n/(n+1)
      • 王道的算法带有哨兵，所以为n+1
    • 折半查找
      • 查找成功ASL=∑n*h
        • 累加n为查找成功结点与深度的乘积/查找成功结点数量
      • 查找失败ASL=∑l*(h-1)
        • 累加n为查找失败结点与深度的乘积/查找失败结点数量
      • 查找判定树
        • 类型：平衡二叉树
        • 条件：中序为有序序列
        • 建立：模拟查找过一遍
        • 树高：h = ⌈log(2,n+1)⌉
  • 树形结构
    • B树
      • 定义
        • 阶数
          • m阶意味所有结点的孩子结点最大值为m
        • m叉树
          • 树中所有叶子结点均不带信息，且在树中同一层次上
          • 仅有根结点或者根结点至少有两棵子树
          • 所有非叶子（不包括根）结点至少含有⌈m/2⌉棵子树（[⌈m/2⌉-1，m-1]个关键字）
          • 根结点可以仅有一个关键字
        • 非叶子结点
          • • P是子树结点指针K是关键字（有序）
      • 示例
        • 结构
        • 磁盘
      • 操作
        • 查找
        • 插入
        • 删除
      • 性质
        • 考前记一记
        • h>=⌈log(m, n+1)⌉
        • h<=log(⌈m/2⌉, (n+1)/2)) + 1
        • n>=2⌈m/2⌉^(h-1) - 1
        • 叶结点数=关键字数+1
    • B+树
      • 与b树区别
        • 每个关键字对应一子树
        • 叶点包含了全部关键字
        • 支持顺序查找
  • 散列结构
    • 概念
      • 用函数解决查找问题
      • 散列函数
        • 关键字与地址的映射:address=f(key)
        • key的定义域应包括关键字所有的可能
        • 值域应该在存储接受范围内
        • 由于不可能精确到所有的关键字，所以肯定存在冲突
    • 散列函数构造法
      • 构造目标是 尽量减少冲突
      • 直接定址法
        • 线性变换法，f(x)=kx+b
        • 优点简单运算少，缺点牺牲空间换取时间和冲突率
      • 除留余数法
        • f(x)=x%p
          • 选择一个接近散列长度的质数p
      • 数字分析法
        • 根据关键字频率构造
          • 优点节省了空间，缺点是函数构建复杂，若关键字有更改，函数也需更改
      • 折叠法
        • 划分关键字，取每部分叠加和作为散列地址
          • 适用于关键字比较长
    • 冲突处理方法
      • 开放地址法
        • 线性探测法
          • 1.是否会循环探测？ 2.当散列表插入过多的数据怎么办？ 也称为“线性探测再散列法”
          • 目标地址已经被合法关键字占据
            • 顺序循环查找下一个空位置放
          • 目标地址已经被非法关键字占据
            • 顺循环序查找下一个空位置放
          • 探测增量di=1,2,3...m-i,-i,-i+1,-i+2,...,i
            • i为发生冲突的位置
          • 合法关键字是该关键字占据的位置 符合它的散列函数给它的安排
        • 平方探测法
          • 探测增量di=1^2,-1^2,2^2,-2^2,...
            • i为发生冲突的位置
        • 再散列法
          • 遇到冲突的时候，再使用新散列函数计算
        • 伪随机序列法
      • 拉链法
        • 发生冲突的关键字放到该位置的链表里
    • 性能分析
      • 查找效率取决因素
        • 散列函数
        • 处理冲突的方法
        • 装填因子
          • a=已使用空间/总空间
      • 常见散列函数查找成功ASL
        • 考前记一记
        • 线性探测
          • S=1/2 * (1+1/(1-a) )
            • ASLs = （∑查找次数*该次数对应关键字个数）/ 关键字个数
            • ASLf = (nf*(nf - 1)]/2+ (N - nf)) / N
              • nf查找失败范围，N可散列长度（mod后面的数字） 即：（nf到1的累加 + 剩余长度）/ 可散列长度 nf = 元素个数+1
        • 随机探测
          • S=-1/a * ln(1-a)
        • 链地址
          • S=1+a/2
  • 串
    • kmp算法
• 图结构
  • 概念
    • 顶点集和边集组成，记G(V,E)
      • 图顶点不可以为空，但边集可以为空
    • 术语
      • 有向图
      • 无向图
      • 简单图
        • 不存在重复边
        • 不存在环
      • 多重图
        • 存在重复边
        • 存在环
      • 完全图
        • 完全无向图
          • 与任意点直接连通
          • E=n(n-1)/2
        • 完全有向图
          • 与任意点直接连通
          • E=n(n-1)
      • 子关系
        • 真子图
          • V'⊂V, E'⊂E
        • 子图
          • V'⊆V, E'⊆E
        • 生成子图
          • V'=V,E'⊆E，记忆留顶点
        • 生成树
          • 极小连通子图
          • 极小是指边最少，连通图符合树结构的生成子图，边=结点-1
        • 生成森林
          • 非连通图符合树结构的所有连通分量
        • 有向树
          • 树的有限结构，仅父节点指向子结点
      • 连通
        • 无向图
          • 连通点
            • 两点有路径存在
          • 连通图
            • 任意两点连通
          • 连通分量（环）
            • 极大连通子图
          • n个顶点，不重复边数小于n-1必定非连通，最多n(n-1)/2条边
        • 有向图
          • 强连通点
            • 两点有来回路径
          • 强连通图
            • 任意两点强连通
          • 强连通分量（环）
            • 极大强连通子图，可以理解为自己， 若果非连通，则有多个连通分量
          • 弱连通图
            • 无向时连通，有向存在不连通
          • 单向连通图
            • 任意两点仅有单向路径连通
          • 最多n(n-1)条不重复边，最少n条不重复边
      • 度
        • 点度
          • 记忆TD(V)指顶点v的边数
            • ∑TD(v)=2e
              • 因为树不计算来自父节点的度， 故公式不一样
        • 入度
          • 记忆ID(V)指顶点v的入边数
        • 出度
          • 记忆OD(V)指顶点v的出边数
        • ∑ID(v)=∑OD(v)=e
      • 权和网
        • 边上带值称为权， 这种图则称为带权图或者网
      • 稠密稀疏
        • |E|-|V|log|V|
          • >
            • 稠密图
          • <=
            • 稀疏图
      • 路径
        • 路径
          • 两顶点的一条连通顶点序列
        • 路径长度
          • 两顶点的一条连通顶点序列数量
        • 回路或者环
          • 第一个顶点与最后一个顶点相同
        • 简单路径
          • 不存在重复顶点的路径
        • 简单回路
          • 不存在重复顶点的回路
        • 距离
          • 两点最短路径
        • n个顶点，大于n-1条边，必有环
  • 存储
    • 邻接矩阵
      • 性质
        • 有向图
          • OD(vi)=第i行非0(带权则非∞)个数
          • ID(vi)=第i列非0(带权则非∞)个数
        • 无向图
          • TD(vi)=第i 行(第i列)非0(带权则非∞)个数
        • A^n(i,j)表示i到j距离为n的路径有A^n(i,j)条
        • 空间复杂度
          • O(V^2)
        • 结点对应的横行和纵列非零元素之和
      • 顺序存储结构
    • 邻接表
      • 有向图
        • OD(vi)=顶点对应的边表长度
        • ID(vi)=扫描每个顶点的边表，记录含有vi的边表个数
      • 无向图
        • TD(vi)=顶点对应的边表长度
      • 空间复杂度
        • O(|V|+2|E|)无向图
        • O(|V|+|E|)有向图
      • 链式存储结构
    • 十字链表
      • 适用于有向图
    • 邻接多重表
      • 适用于无向图
  • 操作
    • 查顶点x的边
    • 插入顶点
    • 删除顶点
    • 插入边
    • 删除边
    • 查找x第一个邻接顶点
    • 查找x下一个邻接顶点
  • 遍历
    • DFS
      • 邻接矩阵
        • O(V^2)
      • 邻接表
        • O(V+E)
    • BFS
      • 邻接矩阵
        • O(V^2)
      • 邻接表
        • O(V+E)
          • 现访问一个人结点向周围扩散
  • 应用
    • 最小生成树算法
      • prim
        • 点优先，从已有的点集选最小权值边对应的点， 加入到点集中，重复至没有点可选。
        • 复杂度O(|v|^2),适用于稠密图
      • kruskal
        • 边优先，贪心选最小权值对应的边， 加入到点集中，确保没有环直到没有所有 点连通。
        • 复杂度O(|e|log|e|),适用于稀疏图
      • 两者需要判断新加入元素是否造成环算法： 1.DFS 2.拓扑排序
      • 性质
        • 网权值不唯一的时候，最小生成树唯一
        • 最小生成树的权值唯一
        • 依旧满足树性质：结点数 n = ∑结点度数（即边） + 1
    • 最短路径
      • dijkstra
        • O(v^2)，缺点是顶点不能含有负值
      • floyd
        • O(v^3)，求所有顶点对的最短路径
    • 拓扑排序
      • 首先确保图属于有向无环图DAG
      • 算法描述：从AOV 网中选一个没有前驱的顶点（度=0 ）依次删除度为1 的顶点及其出度
      • 算法复杂度：
        • 邻接矩阵
          • O(v^2)
        • 邻接表
          • O(|V|+|E|)
    • 关键路径
      • 定义：原点到汇点最大路径长度
      • 关键活动：关键路径上的活动
      • 记忆： 最早事件i=MAX{所有入i的顶点+权重}-> 最晚事件i=MIN{所有出i的顶点-权重}<- 最早活动j=最早事件j，最晚活动j=最晚事件j-wj
• 浮动主题