数据结构+算法复习

2022-04-19 12-未分类 0 评论字数统计: 8k(字) 阅读时长: 29(分)

南航教材：《数据结构（C语言版）》严蔚敏、吴伟民编著

南大教材：《数据结构》（用面向对象方法与C++语言描述），第2版，殷人昆主编

1 分治算法、动态规划、回溯法、分支定界法、贪心算法

分治算法：将一个大问题，分割成一些规模较小的子问题，这些子问题相互独立且与原问题性质相同，求出子问题的解，就可得到原问题的解。
动态规划：将一个大问题，分割成一些规模较小的子问题，求出子问题的解，就可得到原问题的解。与分治法最大的差别是：适合于用动态规划法求解的问题，经分解后得到的子问题往往不是互相独立的。为减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在数组中。
回溯法：在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果不包含，则逐层向其祖先结点回溯。
分支限界法：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。分支限界法常以广度优先或以最小耗费优先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所求的解或活结点表为空时为止。
贪心算法：在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。贪心策略适用的前提是：局部最优策略能导致产生全局最优解。

2 快速排序的思想、优化方法

快速排序的基本思想：快速排序使用分治的思想，通过一趟排序将待排序列分割成两部分，其中一部分记录的关键字均比另一部分记录的关键字小。之后分别对这两部分记录继续进行排序，以达到整个序列有序的目的。
快速排序的三个步骤：
1. 选择枢纽元：在待排序列中，按照某种方式挑出一个元素，作为 “枢纽元”（pivot）
2. 分割操作：以该枢纽元在序列中的实际位置，把序列分成两个子序列。此时，在枢纽元左边的元素都比该枢纽元小，在枢纽元右边的元素都比枢纽元大
3. 递归地对两个序列进行快速排序，直到序列为空或者只有一个元素。
优化方法
1. 当待排序序列的长度分割到比较小的长度后，使用插入排序。
2. 在每一次分割结束后，可以把与划分元相等的元素聚在一起，继续下次分割时，不用再对与划分元相等元素分割。
3. 最佳划分是将序列划分成等长的两个子序列，因此提出三数取中的思想。取序列中，下标第一位，下标中间一位，下标最后一位的三个数进行排序，取排序结果中排中间的数据作为划分元。
4. 快排函数在函数尾部有两次递归操作，我们可以对其使用尾递归优化。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时，这个递归调用就是尾递归。这样所使用的栈空间就大大缩减了，这使得实际的运行效率会变得更高。

3 各种排序算法的最好、平均、最坏时间复杂度

4 Trie 树

Trie 树，又称单词查找树、字典树，是一种树形结构，是一种哈希树的变种，是一种用于快速检索的多叉树结构。
典型应用：用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。
优点：最大限度地减少无谓的字符串比较，查询效率比哈希表高。
核心思想：空间换时间，利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
对于搜索引擎，一般会保留一个单词查找树的前N个字（全球或最近热门使用的）；
对于每个用户，保持Trie树最近前N个字为该用户使用的结果。
如果用户点击任何搜索结果，Trie树可以非常迅速并异步获取完整的部分／模糊查找，然后预取数据，再用一个Web应用程序可以发送一个较小的一组结果的浏览器。

5 P/NP问题

P问题：即为所有可以由一个确定型图灵机在多项式表达的时间内解决的问题；（矩阵乘法、多项式求值）
NP问题（Nondeterminism Polynomial）：由所有可以在多项式时间内验证它的解是否正确的决定问题组成。（典型的子集求和问题，大数分解问题）
NP-hard问题：任意np问题都可以在多项式时间内归约为该问题。归约的意思是为了解决问题A，先将问题A归约为另一个问题B，解决问题B同时也间接解决了问题A。
NP完全问题(NP-C问题)：既是NP问题，也是NP-hard问题。例如，SAT问题（第一个NPC问题）。该问题的基本意思是，给定一系列布尔变量以及它的约束集，是否存在一个解使得它的输出为真。
相互关系：显然，所有P问题都是NP问题，反之则不一定。npc问题是np问题的子集，也是p问题和np问题的差异所在。如果找到一个多项式内能被解决的npc问题的解决方法，那么P=NP。

Ch2 线性表

线性表的存储方式
- 顺序存储方式 —— 顺序表
  - 特点：存储利用率高，存取速度快
  - 缺点：插入、删除等操作时需要移动大量数据
- 链表存储方式 —— 链表(单链表、循环链表、双向链表)
  - 特点：适应表的动态增长和删除
  - 缺点：需要额外的指针存储空间
单链表操作
- 插入
  - 在链表的最前端插入
  - 在链表中间插入
  - 在链表末尾插入
- 删除
  - 删除表中第一个元素
  - 删除表中或表尾元素
- 带附加头结点（表头结点）的单链表：
  - 表头结点位于表的最前端，本身不带数据，仅标志表头。
  - 设置表头结点的目的是统一空表与非空表的操作，简化链表操作的实现。
循环链表操作：插入、删除
双向链表操作：插入、删除
双向循环链表操作：插入、删除
（算法）多项式及其运算
- 多项式顺序存储表示的缺点
  - 插入和删除时项数可能有较大变化，因此要移动大量数据
  - 不利于多个多项式的同时处理
- 多项式链表存储表示的优点
  - 多项式的项数可以动态地增长，不存在存储溢出问题。
  - 插入、删除方便，不移动元素
静态链表
- 为数组中每一个元素附加一个链接指针，就形成静态链表结构。
- 静态链表每个结点由两个数据成员构成：data域存储数据，link域存放链接指针。

Ch3 栈与队列

栈：后进先出（LIFO）
- 如何合理进行栈空间分配，以避免栈溢出或空间的浪费？
  - 双栈共享一个栈空间（多栈共享栈空间）
  - 栈的链接存储方式—— 链式栈
- 栈的应用–表达式的计算（中缀、前缀、后缀）
- （算法）应用后缀表示计算表达式的值：
  1. 从左向右顺序地扫描表达式，并用一个栈暂存扫描到的操作数或计算结果。
  2. 扫描中遇操作数则压栈；遇操作符则从栈中退出两个操作数，计算后将结果压入栈
  3. 最后计算结果在栈顶
- （算法）中缀表达式转换为后缀表达式：
  1. 操作符ch ; ( * / % + - )
    
    isp(栈内) 0 1 5 3 6
    
    icp(栈外) 0 6 4 2 1
    
    操作符优先级相等的情况只出现在括号配对或栈底的 “;” 号与输入流最后的 “;” 号配对时
  2. 操作符栈初始化，将结束符 ‘;’ 进栈。然后读入中缀表达式字符流的首字符ch。
  3. 重复执行以下步骤，直到ch = ‘;’，同时栈顶的操作符也是 ‘;’，停止循环。
    1. 若 ch 是操作数直接输出，读入下一个字符 ch
    2. 若ch是操作符，判断ch的优先级icp和位于栈顶的操作符op的优先级isp：
      1. 若 icp(ch) > isp(op)，令ch进栈，读入下一个字符ch。
      2. 若 icp(ch) < isp(op)，退栈并输出。
      3. 若 icp(ch) == isp(op)，退栈但不输出，若退出的是“(”号读入下一个字符ch。
  4. 算法结束，输出序列即为所需的后缀表达式
- （做题）中缀表达式转换为后缀表达式：
  1. 先对中缀表达式按运算优先次序加上括号；
  2. 再把操作符后移到右括号的后面并以就近移动为原则；
  3. 最后将所有括号消去。

操作符ch	;	(	* / %	+ -	)
isp(栈内)	0	1	5	3	6
icp(栈外)	0	6	4	2	1

队列：先进先出（FIFO）

进队：新元素在rear处加入，rear = rear + 1。
出队：取出下标为 front 的元素，front = front + 1
队空时：rear == front
队满时：rear == maxSize （假溢出）
解决假溢出的办法之一：将队列元素存放数组首尾相接，形成循环（环形）队列。

循环队列：

队头指针进1:  front = (front+1) % maxSize;
队尾指针进1:  rear = (rear+1) % maxSize;
队列初始化：front = rear = 0;
队空条件：front == rear;
队满条件：(rear+1) % maxSize == front

链式队列：
- 队头在链头，队尾在链尾。
- 链式队列在进队时无队满问题，但有队空问题。
- 队空条件为 front == NULL

优先级队列：
- 每次从队列中取出的是具有最高优先权(优先级)的元素
- 优先权是根据问题而定的
- 出现相同的优先权的元素时，按FIFO的方式处理

Ch4 数组、串与广义表

二维数组中数组元素的顺序存放：
- 行优先存放：设数组开始存放位置 $LOC(0, 0) = a$ ，每个元素占用 $l 个存储单元，LOC ( j, k ) = a + ( j * m + k ) * l$
- 列优先存放：设数组开始存放位置 $LOC(0, 0) = a$ ，每个元素占用 $l$ 个存储单元， $LOC ( j, k ) = a + ( k * n + j ) * l$
特殊矩阵：非零元素或零元素的分布有一定规律的矩阵
- 对称矩阵：为节约存储，只存对角线及对角线以上的元素，或者只存对角线或对角线以下的元素。前者称为上三角矩阵，后者称为下三角矩阵。按行存放
- 三对角矩阵：除主对角线及在主对角线上下最临近的两条对角线上的元素外，所有其它元素均为0。总共有3n-2个非零元素。按行存放
稀疏矩阵 (Sparse Matrix)
- 每一个三元组 $(i, j, a_{ij})$ 唯一确定了矩阵A的一个非零元素。
- （算法）稀疏矩阵转置：
  1. 设矩阵列数为 Cols，对矩阵三元组表扫描 Cols 次；
  2. 第 k 次扫描找寻所有列号为 k 的项，将其行号变列号、列号变行号，顺次存于转置矩阵三元组表。
  3. 设矩阵三元组表总共有 t 项，上述算法的时间代价为 $O ( n*t )$ 。当非零元素的个数 t 和 $m*n$ 同数量级时，算法Transpose的时间复杂度为 $O(m*n^2)$ 。
- （算法）稀疏矩阵快速转置：
  1. 为加速转置速度，建立辅助数组 rowSize 和 rowStart：
    1. rowSize记录矩阵转置前各列，即转置矩阵各行非零元素个数；
    2. rowStart记录转置矩阵各行非零元素在转置三元组表中开始存放位置。
  2. 扫描矩阵三元组表，根据某项列号，确定它转置后的行号, 查 rowStart 表, 按查到的位置直接将该项存入转置三元组表中。
- 带行指针数组的二元组表
- 正交链表：适应矩阵操作(+、 -、 *)时矩阵非零元素的动态变化
字符串 (String)
- 空串和空白串不同，分别表示长度为1的空白串和长度为0的空串。
- 串中任意个连续字符组成的子序列称为该串的子串，包含子串的串相应地称为主串。
- 特别地，空串是任意串的子串，任意串是其自身的子串。
- 朴素的模式匹配算法：算法的运行时间为 $O(n*m)$ ，低效的原因在于每趟重新比较时，目标串的检测指针要回退。但在一般情况下，实际的执行时间近似于 $O(n+m)$ ，因此至今仍被采用。
- （算法）KMP算法：算法的运行时间为 $O(n+m)$ ，跳转
- KMP最大的特点是指示主串的指针不需回溯，整个匹配过程中，对主串仅需要从头至尾扫描一遍，这对处理从外设输入的庞大文件很有效，可以边读入边匹配，而无需回头重读。
广义表 (General Lists )
- 表元素，可以是表（称为子表），可以是数据元素（称为原子）
- n 为表的长度。 n = 0 的广义表为空表
- n > 0 时，表的第一个表元素称为广义表的表头（ head），除此之外，其它表元素组成的表称为广义表的表尾（ tail）
- n = 0 时，表头表尾不存在
- 广义表的表示
- 广义表结点定义：
  - 结点类型 utype： = 0, 表头； = 1, 原子数据；= 2, 子表
  - 信息 info： utype = 0 时, 存放引用计数(ref)；utype = 1时, 存放数据值(value)； utype = 2时, 存放指向子表表头的指针(hlink)
  - 尾指针tlink： utype = 0时, 指向该表第一个结点； utype != 0 时, 指向同一层下一个结点
- 广义表的递归算法
- 广义表的复制算法
- 求广义表深度的算法
- 广义表的删除算法

KMP算法跳转

Ch5 树与二叉树

树和森林的概念
- 有根树
  - 一棵有根树T，简称为树，它是n (n ≥ 0) 个结点的有限集合。当n = 0时，T 称为空树；否则，T 是非空树。记作 $T=\left\{\begin{array}{ll} \Phi, & n=0 \\ \left\{r, T_{1}, T_{2}, \ldots, T_{m}\right\}, & n>0 \end{array}\right.$
  - r 是一个特定的称为根 (root) 的结点，它只有直接后继，没有直接前驱
  - 根以外的其他结点划分为 m (m>=0) 个互不相交的有限集合T_1, T_2, …, T_m，每个集合又是一棵树，并且称为根的子树
  - 每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继
- 树的基本术语
  - 子女：若结点的子树非空，结点子树的根即为该结点的子女。
  - 双亲（父亲）：若结点有子女，该结点是子女的双亲（父亲）。
  - 兄弟：同一结点的子女互称为兄弟。
  - 度：结点的子女个数即为该结点的度；树中各个结点的度的最大值称为树的度。
  - 分支结点：度不为0的结点即为分支结点，亦称为非终端结点。
  - 叶结点：度为0的结点即为叶结点，亦称为终端结点。
  - 祖先：根结点到该结点的路径上的各个结点都是该结点的祖先。
  - 子孙：某结点的所有下属结点，都是该结点的子孙。
  - 结点的层次：规定根结点在第一层，其子女结点的层次等于它的层次加一。以下类推。
  - 结点的深度：结点的深度即为结点的层次；离根最远结点的层次即为树的深度。
  - 结点的高度：规定叶结点的高度为1，其双亲结点的高度等于它的高度加一。
  - 树的高度：等于根结点的高度，即根结点所有子女高度的最大值加一。
  - 有序树：树中结点的各棵子树 T1, T2, …是有次序的，即为有序树。
  - 无序树：树中结点的各棵子树之间的次序是不重要的，可以互相交换位置。
  - 森林：森林是m（m≥0）棵树的集合。
- 树的抽象数据类型
二叉树
- 二叉树的定义：一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。
- 二叉树的性质：
  - 性质1 若二叉树结点的层次从 1 开始, 则在二叉树的第 i 层最多有 $2^{i-1}$ 个结点。( i≥1)
    
    用数学归纳法证明
    
    证明：
    
    归纳基础：i=1时，有 $2^{i-1}=2^0=1$ 。因为第1层上只有一个根结点，所以命题成立。
    　归纳假设：假设对所有的j(1≤j<i)命题成立，即第j层上至多有 $2^{j-1}$ 个结点，证明j=i时命题亦成立。
    　归纳步骤：根据归纳假设，第i-1层上至多有 $2^{i-2}$ 个结点。由于二叉树的每个结点至多有两个孩子，故第i层上的结点数至多是第i-1层上的最大结点数的2倍。即j=i时，该层上至多有2×2^{i-2}=2^{i-1}个结点，故命题成立。
  - 性质2 深度为 k 的二叉树最少有 k 个结点，最多有 $2^k-1$ 个结点。( k≥1 )
    
    因为每一层最少要有1个结点，因此，最少结点数为 k。最多结点个数借助性质1：用求等比级数前k项和的公式：2^0 +2^1 +2^2 + …+2^{k-1} = 2^k-1
  - 性质3 对任何一棵二叉树，如果其叶结点有 $n_0$ 个，度为 2 的非叶结点有 $n_2$ 个, 则有 n_0＝n_2＋1
    
    若设度为 1 的结点有 $n_1$ 个，总结点数为n，总边数为e，则根据二叉树的定义，
    n = n_0+n_1+n_2，e = 2n_2+n_1 = n-1
    
    因此，有
    $n_2 = n_0-1 $， $n_0 = n_2+1$
  - 性质4 具有 n (n≥0) 个结点的完全二叉树的深度为 $\left\lceil\log _{2}(n+1)\right\rceil$
    
    设完全二叉树的深度为k，则有 $2^{k-1}-1<n \leqslant 2^{k}-1$ （上面k-1层结点数；包括第k层的最大结点数）
    
    变形 $2^{k-1}<n+1 \leqslant 2^{k}$
    
    取对数 $k-1<\log _{2}(n+1) \leqslant k$
    
    得到 $\left\lceil\log _{2}(n+1)\right\rceil=k$
  - 性质5 如将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号1, 2, …, n，则有以下关系：
    - 若i = 1, 则 i 无双亲
    - 若i > 1, 则 i 的双亲为 $\lfloor i / 2\rfloor$
    - 若 $2*i <= n$ , 则 i 的左子女为 $2* i$
    - 若 $2*i+1 <= n$ , 则 i 的右子女为 $2*i+1$
    - 若 i 为奇数, 且i != 1，则其左兄弟为i-1
    - 若 i 为偶数, 且i != n，则其右兄弟为i+1
- 满二叉树 (Full Binary Tree)：深度为 k 的满二叉树是有 $2^{k}-1$ 个结点的二叉树。
- 完全二叉树 (Complete Binary Tree)：若设二叉树的深度为 k，则共有 k 层。除第 k 层外，其它各层 (1～k-1) 的结点数都达到最大个数，第k层从右向左连续缺若干结点，这就是完全二叉树。
- 二叉树的抽象数据类型
- 二叉树的顺序表示
- 二叉树的链表表示（二叉链表）
  - 二叉树结点定义：每个结点有3个成员，data域存储结点数据，leftChild 和 rightChild 分别存放指向左子女和右子女的指针。
- 二叉树的链表表示（三叉链表）
  - 每个结点增加一个指向双亲的指针parent，使得查找双亲也很方便
  - 三叉链表的静态结构
二叉树遍历
- 二叉树的遍历就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。
- （算法）中序遍历 (Inorder Traversal)
  - 若二叉树为空，则直接返回；
  - 否则：
    - 中序遍历左子树 (L)；
    - 访问根结点 (V)；
    - 中序遍历右子树 ®
- （算法）前序遍历 (Preorder Traversal)
  - 若二叉树为空，则直接返回；
  - 否则：
    - 访问根结点 (V)；
    - 前序遍历左子树 (L)；
    - 前序遍历右子树 ®。
- （算法）后序遍历 (Postorder Traversal)
  - 若二叉树为空，则直接返回；
  - 否则
    - 后序遍历左子树 (L)；
    - 后序遍历右子树 ®；
    - 访问根结点 (V)。
- （算法）利用二叉树前序遍历建立二叉树
- （算法）层次遍历二叉树的算法
  - 层次遍历二叉树就是从根结点开始，按层次逐层遍历
  - 这种遍历需要使用一个先进先出队列，在处理上一层时，将其下一层的结点直接进到队列（的队尾）。在上一层结点遍历完后，下一层结点正好处于队列的队头，可以继续访问它们。
  - 算法是非递归的。
- 由给定的前序序列和中序序列能够唯一地确定一棵二叉树（或者后序遍历和中序遍历）
  
  证明：通过先序序列找到根结点和末尾元素，因为先序和后续最后遍历的都是右子树，所以末尾相同元素即为根节点的右子树，不断对比，每找到一棵子树的根结点就用斜线将其左右与其他元素断开分成一颗颗子树。
- 由给定的前序序列和后序序列不能唯一地确定一棵二叉树
线索化二叉树
- 又称为穿线树。
- 通过二叉树的遍历，可将二叉树中所有结点的数据排列在一个线性序列中，可以找到某数据在这种排列下它的前驱和后继。
- 希望不必每次都通过遍历找出这样的线性序列。只要事先做预处理，将某种遍历顺序下的前驱、后继关系记在树的存储结构中，以后就可以高效地找出某结点的前驱、后继。
- 方法一：增加 Pred 指针和 Succ 指针的二叉树
  - 这种设计的缺点是每个结点增加两个指针，当结点数很大时存储消耗较大。
  - 对于原来的二叉链表结构，一棵n个结点的二叉树共有2n个指针域，而非空的指针域为n-1个，因此，仍有n+1个指针域没有利用起来。
- 方法二：增加左右线索标志的二叉树
  - 改造树结点，将 pred 指针和 succ 指针压缩到 leftChild 和 rightChild 的空闲指针中，并增设两个标志 ltag 和 rtag，指明指针是指示子女还是前驱／后继。后者称为线索。
  - ltag (或rtag) = 0，表示相应指针指示左子女（或右子女结点）；当ltag (或rtag) = 1, 表示相应指针为前驱（或后继）线索。
- 线索化二叉树及其链表表示
- 前序线索化二叉树
- 后序线索化二叉树
树与森林
- 树(一般的树)的存储表示
  - 广义表表示
  - 双亲表示
    - 树中结点的存放顺序一般不做特殊要求，但为了操作实现的方便，有时也会规定结点的存放顺序。例如，可以规定按树的前序次序存放树中的各个结点，或规定按树的层次次序安排所有结点。
  - 子女链表表示
  - 子女指针表示
    - 一个合理的想法是在结点中存放指向每一个子女结点的指针。但由于各个结点的子女数不同，每个结点设置数目不等的指针，将很难管理。
    - 为此，设置等长的结点，每个结点包含的指针个数相等，等于树的度（degree）。
    - 这保证结点有足够的指针指向它的所有子女结点。但可能产生很多空闲指针，造成存储浪费。
  - 子女-兄弟表示
    - firstChild 指向该结点的第一个子女结点。无序树时，可任意指定一个结点为第一个子女。
    - nextSibling 指向该结点的下一个兄弟。任一结点在存储时总是有顺序的。
    - 若想找某结点的所有子女，可先找firstChild,再反复用 nextSibling 沿链扫描。
- 树的遍历
  - 深度优先遍历
    - 先根次序遍历
      - 当树非空时：访问根结点；依次先根遍历根的各棵子树
      - 树的先根遍历结果与其对应二叉树表示的前序遍历结果相同
      - 树的先根遍历可以借助对应二叉树的前序遍历算法实现
    - 后根次序遍历
      - 当树非空时，依次后根遍历根的各棵子树；访问根结点
      - 树的后根遍历结果与其对应二叉树表示的中序遍历结果相同
      - 树的后根遍历可以借助对应二叉树的中序遍历算法实现
  - 广度优先（层次次序）遍历
    - 若树非空，则根结点入队
    - 若队列非空，队头元素出队并访问，同时将该元素的孩子依次入队
- 树与二叉树的转换：孩子兄弟表示法
- 森林与二叉树的转换
  - 将一般树化为二叉树表示就是用树的子女-兄弟表示来存储树的结构。
  - 森林与二叉树表示的转换可以借助树的二叉树表示来实现。
- 森林转化成二叉树的规则
  - 若 F 为空，即 n = 0，则对应的二叉树 B 为空树。
  - 若 F 不空，则
    - 二叉树 B 的根是 F 第一棵树 T1 的根；
    - 其左子树为B (T_{11}, T_{12}, …, T_{1m})，其中，T_{11}, T_{12}, …, T_{1m }是 $T_1$ 的根的子树；
    - 其右子树为$ B (T_2, T_3, …, T_n)，其中，T_2, T_3, …, T_n$ 是除 $T_1$ 外其它树构成的森林。
- 二叉树转换为森林的规则
  - 如果 B 为空，则对应的森林 F 也为空。
  - 如果 B 非空，则
    - F 中第一棵树$ T_1$ 的根为 B 的根；
    - $T_1$ 的根的子树森林 \{ T_{11}, T_{12}, …, T_{1m} \} 是由 B 的根的左子树 LB 转换而来；
    - F 中除了 $T_1$ 之外其余的树组成的森林$ { T_2, T_3, …, T_n } $是由 B 的根的右子树 RB 转换而成的森林。
- 森林的先序遍历
  - 若森林为非空，则按照如下规则进行遍历：
  - 访问森林中第一棵树的根结点
  - 先序遍历第一棵树中根节点的子树森林
  - 先序遍历除去第一棵树之后剩余的树构成的森林
- 森林的中序遍历（效果等同于依次对二叉树的中序遍历）
  - 若森林为非空，则按照如下规则进行遍历：
  - 中序遍历森林中第一棵树的根节点的子树森林
  - 访问第一棵树的根节点
  - 中序遍历除去第一棵树之后剩余的树构成的森林
堆(Heap) 优先级队列
- 每次出队列的是优先权最高的元素。
- 用堆实现其存储表示，能够高效运作。
- 堆的元素下标计算
  - 由于堆存储在下标从 0 开始计数的一维数组中，因此在堆中给定下标为 i 的结点时
  - 如果 i = 0，结点 i 是根结点，无双亲；否则结点 i 的父结点为结点 $\lfloor(i-1) / 2\rfloor$ ；
  - 如果 2i+1＞n-1，则结点 i 无左子女；否则结点 i 的左子女为结点 2i+1；
  - 如果 2i+2＞n-1，则结点 i 无右子女；否则结点 i 的右子女为结点 2i+2。
- （算法）最小堆的下滑调整算法
- （算法）最小堆的插入：每次插入都加在堆的最后，再自下向上执行调整，使之重新形成堆，时间复杂性 $O(log_2n)$
- （算法）最小堆的向上调整
- （算法）最小堆的删除算法
Huffman树

给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w_1、w_2、…、w_n，则哈夫曼树的构造规则为：
1. 将w_1、w_2、…、w_n看成是有n 棵树的森林(每棵树仅有一个结点)；
2. 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
3. 从森林中删除选取的两棵树，并将新树加入森林；
4. 重复2、3步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。

本文链接： https://dragonliu2021.github.io/2022/04/19/数据结构复习/

版权声明： 本博客所有文章除特别声明外，均采用 CC BY 4.0 CN协议许可协议。转载请注明出处！

Dragon's BlogsAlgorithm

Life is painting a picture, not doing a sum.