——本节内容为Bilibili王道考研《数据结构》P46~P48视频内容笔记。目录一、线索二叉树的概念1.引入2.中序线索二叉树3.中序线索二叉树的存储结构 4.先序线索二叉树二、二叉树的线索化1.找中序序列前驱2.中序线索化3.先序线索化4.后序线索化三、线索二叉树找前驱、后继1.中序线索二叉树找中序后继2.中序线索二叉树找中序前驱3.先序线索二叉树找先序后继4.先序线索二叉树找先序前驱5.后序

④如果删除的结点是一棵子树的根结点，那么要将这棵子树的所有结点都删掉；（7）查询：双亲表示法来查指定结点的双亲很方便，但查找孩子结点只能从头到尾遍历依次对比；先将森林的各个树转换为二叉树，再将各个树的根结点视为兄弟关系绑在一起即可；①采用数组的形式，把根结点固定存在数组下标为0的位置，并且用-1表示其没有父结点；最后给结点数n--；左边为孩子，右边为兄弟，最右边一条线上的为各个树的根结点；（1）定

拓扑排序是对有向无环图的顶点的一种排序，它使得若存在一条从顶点A到顶点B的路径，则在排序中顶点B出现在顶点A的后面。（用顶点表示活动的网）用DAG图（有向无环图）表示一个工程，顶点表示活动，有向边表示活动Vi必须先于活动Vj进行；（3）重复（1）和（2）直到当前AOV网为空或当前网中不存在无前驱的顶点为止（如果当前所有顶点入度>0，说明原图存在回路）。（1）从AOV网中选择一个没有前驱（入度为0）

有向无环图：若一个有向图中不存在环，则称为有向无环图，简称DAG图（Directed Acyclic Graph），如下图所示；3.一般会给出一个算术表达式，让我们来求出所需要的最少的顶点个数，下面给出解答步骤；

红黑树是二叉排序树，即左子树结点值

删出边时间复杂度O(1)~O(|V|)；时间复杂度O(1)~O(|V|)。时间复杂度：出度O(1)~O(|V|)；（1）功能：假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点则返回-1。出边时间复杂度O(1)，入边时间复杂度O(1)~O(|E|)。②Set_edge_value(G,x,y,v)：设置图G中边(x,y)或对应的权值为v。①Ge

B树又称多路平衡查找树，B树中所有结点的孩子个数的最大值称为B树的阶，通常用m表示。一棵m阶B树或为空树，或为满足如下特性的m叉树：（1）树中每个结点至多有m棵子树，即至多含有m-1个关键字；（2）若根结点不是终端结点，则至少有两棵子树；（3）除根结点外的所有非叶节点至少有棵子树，即至少含有个关键字；（4）所有的叶结点都出现在同一层次上，并且不带信息（可以视为外部结点或类似于折半查找判定树的查找失

define MaxSize 10//定义栈中元素的最大个数{//静态数组存放栈中元素int top;//栈顶指针，名叫指针，实则只是一个int型整数来反映栈顶元素的数组下标}SqStack;//后续声明一个顺序栈(分配空间)就 SqStack S;补充解释：（1）顺序存储：给各个数据元素分配连续的存储空间，大小为MaxSize*sizeof(ElemType);（2）结构中定义的int top名

——本节内容为Bilibili王道考研《数据结构》P43~P45视频内容笔记。 目录一、二叉树的先中后序遍历1.先中后序遍历2.举例 3.先中后序遍历和前中后缀的关系4.代码实现5.求遍历序列6.应用：求树的深度二、二叉树的层次遍历1.层次遍历2.算法思想：3.算法演示：4.代码实现：三、由遍历序列构造二叉树1.遍历序列构造二叉树2.前序+中序3.后序+中序4.层序+中序（1）二叉树的递归特性：①