数据结构——系列思维导图
2024-06-27 16:02:33 1 举报AI智能生成
登录查看完整内容
计算机科学与技术408系列之数据结构
作者其他创作
大纲/内容
数据的基本单位（整体）（行）-由若干数据项组成
数据元素
数据的最小单位（列）
数据项
性质相同的数据元素的集合——字符型变量
数据对象
有说数据间的关系就是数据结构
数据结构是带结构（关系）的数据元素集合
数据元素的前后关系——逻辑结构
数据元素在计算机中的存储方式——物理结构
元素间关系
数据结构包括
数据结构
与数据元素本身的形式、内容、相对位置、个数、存储无关
独立于计算机，抽象出来的，从逻辑关系上描述数据的一种数学模型。
线性表、栈、队列
线性结构
集合、树、图
非线性结构
关系
包含两个要素
数据的逻辑结构
存数据对象时，既要存储各数据元素数据。也要存储数据元素之间的逻辑关系
数据对象在计算机中的存储表示
需要一块连续的存储区域，方式：逻辑上相邻的结点存储在物理位置相邻的存储单元中，结点间的逻辑关系由存储单元的邻接关系体系
顺序存储结构
不需要所有结点占用一片连续的存储空间，结点间的逻辑关系由附加的引用字段（指针）来表示
链式存储结构
存储方式：采用附加的索引表方式存储结点信息，索引表由若干索引项（关键字、地址）组成
索引存储结构
存储方式：根据结点的关键字直接算出该结点的存储地址（通过散列函数，哈希函数）
散列存储结构
数据物理结构（四种基本存储结构）
无论顺序存储还是链式存储，每个结点都要占用一片连续的存储区域
同一逻辑结构采用不同的存储方法可以得到不同的存储结构
数据的物理结构
运算的定义：是针对数据逻辑结构的，即针对这种逻辑结构需要进行什么运算。比如队列中的入队，出队。
运算的实现：是针对数据存储结构的，即针对逻辑结构会有不同的存储结构。比如实现的运算相同，但不同的存储结构其实现方式不同。
数据的运算
数据结构的三要素：逻辑结构，物理结构，运算。
选择什么样的数据的存储结构会影响存储空间分配的方便程度，会影响数据运算的速度。
注意⚠️
即若定义一个具体的结构类型，根据这个类型具体的业务需求可确定值的范围 以及 可进行的操作。
数据类型是一个值的集合 和 定义在这个值集上的一组操作的总称
数据类型
数据对象间的关系
数据对象的基本操作
是指由用户定义的，表示应用问题的数学模型以及定义在这个模型上的一组操作的总称（结构体）
当定义一个抽象数据类型时，其实我们是用数学化的语言定义数据的逻辑结构和数据的运算。而与使用哪种物理结构无关。而只有当我们需要用计算机去实现此数据结构时才需要考虑存储结构。
ADT是抽象数据组织 及 与之相关的操作。
抽象数据类型ADT
构成一个完整的数据结构定义。
定义了一个ADT，就是定义了数据的逻辑结构和运算，也就是定义了一个数据结构。
确定一种存储结构，就意味着要在计算机中表示出数据的逻辑结构。存储结构不同，运算的具体实现不同。
确定了存储结构，才能实现数据结构。
总结：
数据结构的基本概念
定义：是对特定问题求解步骤的一种描述，是指令的有限序列。其中每条指令表示一个或多个操作。
所以算法必须有穷，但程序可以无穷无尽的进行下去，比如微信。还有死循环也不具备有穷性，因为有限步后结束不了。。。
有穷性：一个算法总是在执行有限步后结束，且每一步都是在有穷时间内完成。
不是一次输入得这个，一次输入得那个。
任何条件下算法只有唯一的执行路径，即1：1，相同输入得相同输出
确定性：算法的每一条语句指令都必须由确定的含义，别人理解时候不产生二义性。
即可由代码实现。
可行性：算法可行，即算法中描述的操作均可由有限次已成型的基本运算实现。
输 入：可以有0个 或 多个输入。
输 出：可以有1个 或 多个输出。
算法的五个特性：
算法应能正确的解决问题。
正确性：
代码可读，可让人们理解。
可读性：
当输入非法数据时，算法能适当地作出反应并进行处理，而不会产生莫名其妙的结果。
健壮性：
速度快，内存小。时间复杂度低，空间复杂度低。
高效率和低存储量：
一个好的算法包括四个方面：
算法执行的效率与数据的逻辑结构，物理结构，程序的控制结构，输入的数据量 问题规模n，语句频度（T与n关系），解决问题的策略等有关。
❌
算法最终必须由计算机程序实现
同一个算法，实现语言的等级越低，执行效率越高，越快
算法
算法的时间复杂度与选择的程序设计语言无关
执行算法的语句次数/语句频度
T与n的关系
关注基本操作执行的次数
现实中常讨论最坏情况下的时间复杂度，所以，所谓时间复杂度是指最坏情况下估算算法执行时间的一个上界。
问题的规模
不考虑与空间复杂度的关系
（如某些算法受数据初始状态杂乱程度的影响）
待处理数据的状态
算法时间复杂度 / 时间开销 取决于
强调相同规模n下的情况下，O(n)才总比O(n²)快。否则不一定
算法时间复杂度并不是指算法执行时所用的具体时间，时间复杂度是一个函数（定量的描述了算法的运行时间）
T(n) = O(f(n))
n是指问题规模；即输入的数据量；数据的个数；数据的规模
O(1)算法运行时间与数据量大小无关。
O(n)算法运行时间与数据量大小呈线性关系，即数据量增大n倍，算法运行时间增大n倍。
O(n²)算法运行时间与数据量大小呈线性关系，即数据量增大n倍，算法运行时间增大n²倍。
要循环次数最多的那段代码
循环次数最多原则
要量级最大的代码块代码
加法原则
内外嵌套且无关：内外乘积
乘法原则
计算原则
①找出循环条件；②设循环次数a，③找a与i关系；④代入条件；⑤出结果
分单层循环①②③④⑤步
②若内外无关，就各算各的，相当于两次单层循环任何乘起来
②若内外有关，则列累加求和式，由右向左算，最后再当单层循环算①②③④⑤步
①看内外是否无关
和多层循环①②步
计算方法
时间复杂度
执行当前算法需要占用多少辅助空间
算法所需存储空间的量度
S(n) = O(f(n))
含义：原地工作是指不需要任何额外的辅助空间
算法所需要的辅助空间（临时空间）不随问题规模n而变化，即辅助空间与n无关
则此算法的空间复杂度为一个常量。记作O(1)
原地工作：
空间复杂度
评价算法的优劣：事前估计算法时间开销T(n)与问题规模n的关系T表示Time时间算法空间开销(内存)与问题规模n之间的关系S表示Space空间
算法效率的度量
算法和算法分析
1绪论
栈是操作受限的线性表，仅允许在表尾（栈顶）进行插入和删除操作栈的表头称作栈底，栈的表尾称作栈顶。
特点：后进先出：LIFO 先进后出：FILO
定义
定义：栈由两个指针组成，栈底指针指向栈底，栈顶指针初值指向栈顶，插入top+1，删除top-1，所以栈顶指针总是指向栈顶元素的下一个位置
所以top指针就表示新的栈顶。（数据可能残留在内存中，只是逻辑上被删除）
top指向当前栈顶元素的位置。
栈的顺序存储结构：顺序栈
单链表——头插法
实现：采用不带头结点的单链表实现。规定栈的所有操作都只在此单链表表头进行。
优点：不存在栈满溢出的情况
栈的链式存储结构： 链栈
存储
顺序栈结构体：typedef struct{ SElemType *base; //栈构造之前和销毁之后，base=NULL SElemType *top; int stacksize; //表示当前已分配的存储空间}Sqstack
初始化：Status InitStack(SqStack &S){ S.base = (SElemType *)malloc (STACK_INIT_SIZE * sizeof(SELemType)); if(!S.base) exit(OVERFLOW); S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK;}
销毁：Status DestroyStack_Sq(Sqstack &S) {}
栈空：S.top = S.base;
栈满：S.top == MaxSize-1
顺序栈操作
初始化：Status InitStack(LinkStack &S){ s = NULL; return OK;}
链栈的进栈相当于单链表的头插法
取栈顶元素：Status GetTop(LinkStack s){ if(s != NULL) return s->data;}
链栈操作
初始化：S.top = -1; //top现在指向栈顶元素
栈顶元素：S.top[S.top]
S.data[++S.top] = x;
进栈：栈不满时，栈顶指针先+1，再赋值值到栈顶元素
x = S.data[S.top--]
出栈：栈非空时，先存栈顶元素，再将栈顶指针-1
栈空：S.top == -1;
栈满：S.top == MaxSize-1;
栈长：S.top + 1;
顺序栈的操作（2）
初始化：S.top = 0; //top指针指向栈顶元素的下一个位置
栈顶元素：S.top[S.top-1];
进栈：S.data[S.top++] = x;
出栈：x = S.data[--S.top];
栈空：S.top == 0;
栈满：S.top == MaxSize;
栈长：S.top;
外框
改变栈顶指针，改变top指针
若需要用到两个相同类型的栈，可用一个数组data[0...maxSize-1]来实现这两个栈，称为共享栈（共享一个一维数组）。数组的左右两个端点分别是两个栈的栈底，一个栈的栈底为数组始端0，另一个栈道栈底为数组末端MaxSize-1当元素进栈时，栈顶向共享空间的中间延伸。
定义：
存取数据的时间复杂度是O(1)
可以更新有效的利用存储空间，节省存储空间，两个栈的空间可以相互调节，只有在整个存储空间被两个栈占满（即两个栈栈顶相遇）时，才发生上溢（降低上溢发生的几率）。
优点：
栈空：top1 = -1 top2 = MaxSize
top2-top1 = 1;
栈满：top1 + 1 == top2;
进栈：top1++; data[top1] = x; top2--; data[top2] = x; S.data[++top1] = x; S.data[--top2] = x;
出栈：x = data[top1]; top1--; x = data[top2]; top2++; x = S.data[top1--]; x = S.data[top2++];
操作：
栈空：top1 = 0; top2 = MaxSize-1;
栈满：top1 == top2; ?
入栈：S.data[top1++] = x; S.data[top2--] = x;
出栈：x = S.data[--top1]; x = S.data[++top2];
改变top指针
为了便于管理，可以将共享栈设计为一个结构体类型。
设计：
共享栈（双端栈）
逐步法：逐步根据 原中缀表达式优先级，并按照“左优先”原则，做变换（符号移至操作数末尾）。
暴力法：1️⃣将每 两个操作数 用括号括起来，2️⃣将操作符提出至括号后，3️⃣去掉括号。
二叉法：将表达式画成二叉树，再根据后序遍历得后缀表达式
中缀转后缀的三种方式：
表达式求值：
栈与递归有着紧密的联系。递归模型包括递归出口和递归体两个方面，递归出口是递归算法的出口 即递归终止的条件；递归体是递推的关系式。
即某个函数的执行次序 等于 其在递归调用树的 层次遍历 次序。
若题目问某个递归函数 执行次序/次数，可以画出对应递归调用树。
对于一个问题的递归算法求解和其相对应的非递归算法求解相比：非递归算法效率更高一些。反而递归算法有一些冗余的重复的计算。
使用栈可以模拟递归的过程，以此来消除递归。
但对于单向递归或尾递归来说，可以用迭代的方式（非递归）来消除递归。
消除递归 不一定需要使用栈。
递归函数：
递归函数判断：
括号匹配的校验
数制转换
行编辑程序的输入缓冲区
迷宫求解
车辆调度中求出栈车厢序列，
栈的应用题型
内存缓存区
打印机打印序列
FIFO页面替换算法
队列的应用题型
递归的时候用栈。程序调用是一个递归过程，用栈实现，首先从main函数进入，即栈的进栈过程。函数调用是一个递归的过程。
这个入栈出栈序列可以相同，可以互为逆序。
由于栈具有后进先出的特性，所以根据入栈（出栈）序列能判断出出栈（入栈）序列。
因为不知其中元素的出栈时间。
即使确定了入栈次序，也不能就此来确确定定出栈序列。
n个元素进栈，出栈元素的不同排列个数为：卡特兰数 C2n的n / n+1
考点
写出出入栈序列
判断可能取值的个数
共享栈判初始，栈空，满
向一个栈顶指针为top的链栈，插入一个x结点：先将x的next指针域指向top，再将栈顶指针指向xx->next = top; top = x;
通常情况下，递归算法在计算机中的执行过程中会有很多重复的计算或是验证步骤，所以递归算法比非递归算法效率低。
调用函数时，系统将会为调用者构造一个由参数表和返回地址组成的活动记录，并将记录和函数的局部变量压入系统提供的栈中。
即在不带头结点的链表首部插入一个元素。
向栈顶指针为top的链栈（不带头结点）中插入一个x结点：x->next = top; top = x;
因为i不确定，所以没有i-j，j-i+1 这种出栈规律。
若已知栈的输入序列12345....n，若问输出第一个元素为i，那么第j个输出的元素是？
题型
栈
队列queue，是一种限制存取位置的线性表，它只允许在表的一端（表尾，队尾）进行插入，另一端（表头，队头）进行删除。
队列的插入和删除操作分别在各自一端进行，每个元素按照进入的次序出队。即先进先出 FIFO。
特点
1️⃣少用一个队列空间，即队列空间大小为m时，认为有m-1个元素时队满。队空：q->front == q->rear;队满：(q->rear+1)%MaxSize == q->front; （约定以“队列头指针front在队尾指针rear的下一个位置上”作为队列“满”状态的标志）队列长度：(rear - front + m) % m;
2️⃣增设表示队列元素个数的数据成员size。队空：size == 0 && front == rear;队满：size == MaxSize && front == rear;
3️⃣增设tag标签 数据成员以区分队满与空 （队空队满代码一样，那就再设一个变量记录此时队列状态）队空：tag == 0；因删除导致front = rear队满：tag != 0；因插入导致front = rear
+1的原因是下标默认值为-1
循环队列：【0， m-1】front指向队头元素前一个位置，rear指向队尾元素。<=>front指向队头元素，rear指向队尾元素的下一个位置一样 入队时队尾指针前进1：(rear + 1) % QueueSize（QueueSize循环队列的最大长度）出队时队头指针前进1：(front + 1) % QueueSize队空：q.rear = q.front队满：(rear+1) % m == front循环队列的元素个数 / 队列长度：(rear - front + QueueSize) % QueueSize
循环队列：【0， m-1】front指向队头元素，rear指向队尾元素队空：q.rear = q.front队满：队列长度（队列中元素个数）： 当rear>front时，当前队列的元素个数是：rear - front + 1 当rear<front时，当前队列的元素个数是：rear - front + m + 1综合上述两种情况： 当前队列的元素个数是：(rear - front + m + 1) MOD m
循环队列：【0， m-1】默认front，rear队空：队满：当前队列中元素个数是：(rear - front + m) % m
将顺序队列臆想为一个环状的空间——循环队列（插入队尾指针增1，通过模来运算）
顺序队列满了怎么办？又不能像顺序栈一样进行数组再分配扩大数组空间。
front队头指针指向队列 队头元素位置，rear队尾指针指向队列 队尾元素的下一个位置。
操作：队空（初始化）：q->front == q->rear;队满：q->rear == MaxSize;进队：data[rear] = x; rear++; q->data[q->rear] = x; q->rear++;出队：x = data[rear]; front++; x = q->data[q->front]; q->front++;
队列的顺序存储结构：顺序队列
实现：采用单链表来实现队列，在单链表表头删除，表尾插入。
是一个同时带有 队头指针（指队头结点） 和 队尾指针（指队尾结点） 的 单链表
本质：
链队列在做删除运算时，看成单链表的删除操作：当队列有多个元素时，只需修改头指针即可。当队列只有一个元素时，该结点既是头又是为尾，则需要修改尾指针置空。
特点：同链栈一样，不存在队满溢出的情况
用单链表表示的链队列适合于数据元素变动较大的情形，且不存在队列满产生溢出的问题
适合：
LinkQueue结构体声明：typedef struct qnode{ QElemType data; struct qnode *next;}DataNode;typedef struct{ DataNode *front; DataNpde *rear;}LinkQuNode;
front == rear q==null
带头结点
front+1 == rear q->next=null
不带头结点
链队列的判空条件
操作：队空：q->front = q->rear;队满：不考虑入队：插入到单链表表尾出队：删除单链表表首结点(q->front ==NULL; 且 q->rear == NULL;)
队列的链式存储结构：链队列
定义：是指队列的两端都可以进行进队和出队操作，不受限制，其元素的逻辑关系仍为线性关系。
问：既然队列前后端都可以出入队，那是不是可以想得到什么序列就得到什么序列？例如dcab这个序列，可以ab后端进，cd前端进，最后都从前端出。但是abcd入队，出队dacb是不无论如何也出不来的。因为c不论是前端进出还是后端进出，都无法在ab之间。
特点：双端队列中，元素从前端进后段出 或 从后段进前端出，都体现了队列先进先出的特性。 而元素从前端进前端出 或 从后端进后段出，则体现了栈的后进先出的特性。
若只能从左进（限制入队），左右都能出，则说明已知入队序列，想要得到目标序列就看左右两边怎么出队了。
若只能从右出（限制出队），两边都能进，则说明目标序列只能从右边出来，看左右两边怎么进能得到目标序列。
实际使用中，可以自定义双端队列的两端进出规则。若再次限定双端队列中从某端进队的元素只能从某端出队，则该双端队列即变为了两个栈底相邻的栈。
双端队列
队列的应用
F1：自己按逻辑排一下，顺一下。
F2：以第一个入队元素A为中心，在队列中向左向右看都是顺序，没有逆序，则可实现。
F3：以ab或是其他挨着的序列看，无论ab是从一端进还是两端进，只要已知入队顺序，则在队列中，ab必相挨。
做自定义双端队列出入时，已知入队顺序，判不可能的出队顺序。
rear = (rear+1) % MaxSize
front = (front+1) % MaxSize
一旦涉及 顺序队列中判断front，rear指针位置时，注意套公式。
例：n=6，rear 1，front 5，删除一个元素和加入两个元素可得值：3，0
不能说ADT一致：因为ADT包含三项：逻辑结构，存储结构，运算。栈队列运算说不同的。
栈和队列本质都是线性表，线性结构。他俩的本质区别是：插入、删除操作的限定不同。
能根据首尾指针计算出队列长度的 一定是顺序存储时。链式存储计算不出长度。
即找有首尾指针的队列，此时循环没用，人家队列不需要循环，循环画蛇添足。
错因：哪种链表适合队列：一定根据队列的特点去选择链表种类：即 两端操作。
错因：利用两个队列输出序列。
队列
前言：矩阵在计算机图形学、工程计算中占有举足轻重的地位，而在数据结构中，我们的精力重心放在如何让将矩阵更有效地存储在内存中，并能方便地提取矩阵中元素。
每个数据元素称为一个数组元素，每个元素在n个线性关系中的序号称为该元素的下标，下标的取值范围称为数组的维界。
一维数组是由n（n=>1）个相同数据类型元素组成的有限序列
二维数组也叫矩阵，行列相等的叫方阵。
一个二维数组（矩阵）可以看作是每个数据元素都是相同数据类型的一维数组的一维数组。
数组与线性表的关系：数组是线性表的推广
数组一旦被定义，其维数和维界就不再改变。即数据元素数目固定，一旦定义来一个数组，其数据元素的数目不再有增减的变化。
读操作：给定一组下标，读取相应的数据元素。
写操作：给定一组下标，存储或修改相应的数据元素。
数组中通常只有两种操作：不做插入与删除上因为定义好数组后长度就固定了
数组中的数据元素数目固定。一旦定义来一个数组，其数据元素的数目不再有增减的变化。
数组中的数据元素具有相同的数据类型。
数组中的数据元素都和一组唯一的下标一一对应。
数组是一种随机存储结构，具有随机存取的特性，即可随机存取数组中的任意数据元素。
性质
通常将数组的所有元素存储到存储器的一块地址连续的内存单元中，即数组特别适合采用顺序存储结构来存储。
设：每个元素占用k个内存单元LOC(ai) = LOC(a1) + (i-1)*k (1 <= i <= n)
一维数组的存储结构：
二维数组的存储结构：
数组的存储结构
定义：特殊矩阵是指非零元素或零元素分布有一定规律的矩阵。 所以利用此种规律对数组进行压缩存储进而提高存储空间效率。
对称矩阵按主对角元素对称，其上下三角部分对应元素相等，所以存储时可以只存主对角元素+上/下三角元素。(存一半就行)
k = i * (i-1) / 2 + j-1
在以行序为主序的存储方式下，存下三角元素（i => j）至一维数组B：b k = (i+1)*i / 2 + j
k = j * (j-1) / 2 + i-1
在以行序为主序的存储方式下，存上三角元素（i < j） 至一维数组B：b k = (j+1)*j / 2 + i
对称矩阵的存储：
font color=\"#4669ea\
上三角矩阵：上三角矩阵的上三角为正常序列（i<=j），下三角为常数C的n阶方阵。
下三角矩阵：下三角矩阵的下三角为正常序列（i > j），上三角为常数C的n阶方阵。
i => j : k = (i+1) * i / 2 + j
i < j : k = (n+1) * n / 2
下三角( i > j )以行序为主序的方式存储
k = ( n + n-i+2 ) * ( i-1 ) / 2 + j-ik = ( 2n-i+2 ) * (i-1) / 2 + j-i
i <= j : k = ( n + n-i+1 ) * i / 2 + j-i k = ( 2n-i+1 ) * i / 2 + j-i
i > j : k = (n+1)*n/2
上三角( i < j )以行序为主序的方式存储
三角矩阵的压缩存储
1 <=i; j<=n; | i-j |
A中行下标为0的行和行下标为n-1的行都只有两个非零元素，其余各行有三个非零元素。
此时 j = i-1，即k=2i + i-1 = 2i+j
i.1 : k = 2+3(i-1) = 3i-1
此时 j = i，即k=2i + i = 2i+j
i.2 : k = 2+3(i-1) + 1 = 3i
此时 j = i+1，即k=2i + i+1 = 2i+j
i.3 : k = 2+3(i-1) + 2 = 3i+1
在第i行分为三种情况
i【1，n】存 bk【1，n】此时的 k = ( 2i + j - 3 ) + 1
【1，n】此时的 k = 2i + j - 3
前i行存储元素总数2+3(i-1)
例：当k=2时，i=2，j=1，所以存a21
【1-n】，若已知 B[k] ，则有font color=\"#0000ff\
三对角矩阵的压缩存储
特殊矩阵包括：均为方阵，即m=n（行数=列数）
特殊矩阵
⚠️稀疏矩阵压缩存储后便失去了随机存取的特性
稀疏矩阵中的非零元素的个数相较于矩阵元素总个数来说非常小，且分布没有规律。
顺序存储 => 形成三元组顺序表（三元组表）
三元组表示法：稀疏矩阵中的每一个非零元素由一个font color=\"#5b79e8\
采用链式存储结构来表示三元组线性表，链表中的每个非零元素既是某个行链表中的一个结点，又是某个列链表的一个结点。整个矩阵构成十字交叉的链表。
采用两个分别存储 行链表的头指针 和 列链表的头指针 的一维数组来表示。
十字链表表示法：当矩阵的非零元素个数和位置在操作过程中变化较大时，就不宜采用顺序存储来表示三元组的线性表。——>
稀疏矩阵的存储
稀疏矩阵：
对称矩阵中，上三角按列优先 = 下三角按行优先 计算时候：（上列 <=> 下行）（公式中 i 换成 j ）（所求的具体下标中 i，j 也互换）
三角矩阵的计算：首先看需要求的矩阵位置点位于上三角还是下三角，然后对应看题目要求的存储方式，再去对应公式计算。
若矩阵0，1 放到数组B [1，n]，则还按经典公式算，最后 +1 即可
矩阵0，1开始放到数组B [0，n-1] 算经典公式
数组 和 特殊矩阵
对称矩阵上下三角对应元素相等，所以存一半就行
上三角存储：1——n2——n-13——n-2 ......i——n-i+1
补充
树的定义是递归的，所以树是一种递归的数据结构。
树是n（n => 0）个结点的有限集合T，满足：（当n=0时，称为空树）1️⃣有且仅有一个特定的被称为“根”的结点。2️⃣其余结点分为m（m > 0）个互不相交的子集T1、T2、T3，其中每个子集又是一棵树，称为根的子树。
树的定义：
树中每个元素（除根结点外）均有一个直接前驱（辫子），有零个或多个后继。——故n个结点有n-1条边。
树是一种非线性的数据结构，一对多。
树适合表示具有层次结构的数据
特点：
度=m，则为m叉树
度为 k 的树也称 k叉树，其中每个结点最多有k个子树
结点的度：一个结点的子树个数。树的度：该树中结点的最大度数。
度不为零的结点。N1，2
分支结点（非终端结点）：
度为0的结点。N0
叶子结点（终端结点）：
⚠️在树的分支结构中，每个结点的分支数就是该结点的度数。如：对于度为1的结点，其分支数为1，为单分支结点；度为2的结点，其分支数为2.，称为双分支结点。
孩子结点和双亲结点：树中某个结点的子树的根，该结点则为孩子的双亲结点。
堂兄弟结点：双亲结点是兄弟关系的结点（即在同一层）。
兄弟结点：同双亲的孩子结点互称为兄弟。
该结点的祖先是从树的根结点到该结点所经分支上的所有结点。
以某结点为根的子树中的任意结点 称为该结点的子孙。
子孙结点和和祖先结点：
基本结点介绍：
树中结点的最大层数称为树的高度或深度。
树的层次：从根结点开始，根为第1层，其子结点为第2层，以此类推。
树的深度：从根结点开始 自上而下 数。
树的高度：从叶结点开始 自下而上 数
树的层次、深度和高度：
有序树：树中结点的各子树从左到右有次序，位置不可互换；若互换，则称为一棵不同的树。
无序树：树中结点的各子树交换，不影响树的基本排列。
有序树和无序树
路径：树中两个结点的路径是指两个结点之间所经过的 结点 的序列。
路径长度：在此路径上所经过的结点个数。
同一双亲的孩子之间不存在路径。
⚠️树中的分支是有向的，即从双亲指向孩子，所以树中的路径树从上到下的。
树的路径长度是指 树根到每个结点的路径长度的 总和。
路径与路径长度；
若在两棵树中，各结点对应相等，各结点的对应关系也相等，则称这两棵树相等或等价。
若在两棵树中，适当重命名其中一棵树的结点可以使两棵树等价，则称为树的同构。
树的等价和同构：
所以树与森林可以相互转换。
显然，删除一个树的根，就可以得到一个森林；反之加上一个结点作为树根，将这m棵树作为该结点的子树，森林就变为一棵树。
森林是m（m => 0）棵互不相交的树的集合。
森林：
与树有关的术语：
写两个式子：n = n0 + n1 + n2 + n3 （设n0 n1 n2 n3 分别是度为0123的结点个数） 等于各度数的结点数量之和n = 0*n0 + 1*n1 + 2*n2 + 3*n3 + 1
树的结点数 = 所有结点的度数 + 1 = 总度数 + 1 = 分支数 + 1
度为m的树中，第i层上至多有 m的i-1次 个结点。
高度为h的m叉树 至多有( m的h次-1 ) / (m-1)。
具有n个结点的m叉树的最小高度是logm(n*(m-1)+1)。
树的性质：
根到每个结点的路径长度最大值为：h-1。
树有n个结点，度为m，要使此树最高：h = n - (m-1) 【即除最后一层外，每层结点数为1，即只有最后一层为m】。
已知结点总数n，度数m，求树的最小高度，那就是把每一层的每一结点都排满度数 n - (1 + m + m的2次 + m的3次...) 或者套公式：logm(n*(m-1)+1)。
已知树高h，度数m，求结点总数，则n至少为 h + (m-1)； 至多为 1 + m + m 的2次 + ... + m的h-1次 = ( m的h次-1 ) / (m-1)。
若结点数量为n，则边的数量为n-1。
树的题型：
树
二叉树由一个根结点及两棵互不相交的，分别称作该根的左子树和右子树的二叉树组成。（递归定义）
二叉树（Binary Tree）是 n (n=>0)个结点的有限集合。（二叉树可以为空）
二叉树的定义：
度<=2的有序树
每个结点最多只能有两棵子树，度<=2（即二叉树不存在度 > 2的结点），并且这两棵子树有左右顺序之分，其次序不能随意颠倒。
度为2的树最最少 (至少) 有三个结点，但是二叉树是可以为空的。
而二叉树即使只有一个孩子，也要严格区分左右，即左孩子和右孩子。（因为二叉树的孩子左右是确定好的，不是相对于另一个的）
度为2的有序树的孩子虽然有左右之分，但若只有一个孩子，则不分左右。（因为有序树孩子的左右次序是相对于另一个孩子而言的）
总结：由此来看，二叉树与树是两个不同的概念。二叉树既不是树的特殊情况，也不是有序树的特殊情形。
二叉树与度为2的有序树的区别；
二叉树的主要特征：
定义：满二叉树的每一层上的结点数都达到了最大（即给定高度的二叉树中，满二叉树结点数最多）
满二叉树中的每层都含有最多的结点。
满二叉树的深度为k，则有2的k次-1个结点。
满二叉树中不存在度为1的结点（除叶子结点外），每个分支结点的度数都是2。
即满二叉树的叶结点全在最后一层。
满二叉树的每个分支结点均有两棵高度相同的子树，且所有叶结点均在最下面一层。
其双亲为 i-1/2，左孩子为 2i+1，右孩子为 2i+2。
【 若 i 属于[0，n-1] 】
例：i=5 的双亲结点为：⌊5/2⌋=2
对于编号为 i 的结点来说，其双亲为⌊i/2⌋，左孩子为2i，右孩子为2i+1。
可对满二叉树的结点进行连续编号，一般约定，从根结点开始，按“自上而下，自左向右”按层序排序编号。
1️⃣满二叉树：(Full Binary Tree)
即深度为k的满二叉树中编号从1～n的前n个结点构成了一棵深度为k的完全二叉树。【2的k-1次<= n <=2的k次-1】
在完全二叉树中，至多只有最下面两层的结点的度可以小于2，并且最下层的结点都集中在该层的最左边的若干位置。比满二叉树少了最右边的几个叶结点。
定义：若高度为h，结点数为n的二叉树，当且仅当其每一个结点都与高度为h的满二叉树中编号从1-n的结点一一对应。
即高度为h的完全二叉树中，其1～h-1层构成了一个高度为h-1的满二叉树。共有2的h-1次-1个结点。
一棵完全二叉树，前 h-1 层为满二叉树
完全二叉树的高度 是所有 二叉树 中 最小的高度。
具有n个结点的完全二叉树的 深度/高度 为 ⌊log₂ n⌋+1 / ⌈log₂(n+1)⌉ = ⌊log₂ 2n⌋
在完全二叉树中，若有度为 1 的结点，则只有一个结点 且 该结点只有左孩子而无右孩子。
完全二叉树中n1的取值只可能为0或1。
例：完全二叉树最后一个结点为n，其父结点为 s = ⌊n/2⌋，叶结点个数：n0 = n-s
i > ⌊i/2⌋ 为叶子结点。
叶结点只可能在层数最大的两层中出现。
在完全二叉树中，若某一个结点没有左孩子，则其一定没有右孩子，即必定为叶结点。【因为根据定义，完全二叉树必须先有左孩子、再有右孩子】
若已知完全二叉树的第 i 层出现了叶结点，说明此树高h = i 或 i+1
为完全二叉树按层序编号后，一旦出现某个结点( i )为叶结点或 i 只有左孩子，则 > i 的结点全为叶子结点。
完全二叉树叶结点特点
若编号n为奇数，则每个分支结点均有左右孩子；若编号n为偶数，则编号最大的分支结点只有左孩子无右孩子。其余分支结点左右孩子均有。
满二叉树是完全二叉树，但完全二叉树不一定是满二叉树。
空二叉树和只有根结点的二叉树 既是满二叉树，也是完全二叉树。
【找 双亲】 若 i>1 ，i双亲是结点 ⌊i/2⌋（下取整），即：当i为偶数时，则其双亲是 i/2（ i是双亲的左孩子 ）；当i为奇数时，其双亲的编号为(i-1)/2（ i是双亲的右孩子 ）。
故 i > n/2（下取整）必定是叶子
【找 左孩子】若2i <= n，则结点 i 的左孩子编号为 2i，否则无左孩子（即结点i 为叶结点） 。
【找 右孩子】若2i+1 <= n，则结点i 右孩子编号为 2i+1，否则无右孩子。
结点 i 所在的层次 (深度) 为 ⌊log₂ n⌋+1
对于一棵有n个结点的完全二叉树（ 其深度为⌊log₂ n⌋+1 ）的结点按层序编号（ 从第1层到⌊log₂ n⌋+1层 ），每层中从左到右，则对任一结点 i (1 <= i <= n)，i=1为根，有：
2️⃣完全二叉树：(Complete Binary Tree)
定义：在平衡二叉树中，任意一个结点的左子树和右子树深度之差的绝对值不超过 (<=) 1。
平衡二叉树有更高的搜索效率。
平衡二叉树 本质上是 二叉排序树。❓
从平衡因子定义看，完全二叉树任一结点平衡因子绝对值<=1，但完全二叉树不一定是排序树，所以不是平衡二叉树。
3️⃣平衡二叉树：(Balance Binary Tree)
定义：在二叉排序树中，左子树上所有结点的关键字 均小于根结点的关键字，右子树上所有结点的关键字 均大于根结点的关键字。
二叉排序树的左子树，右子树又是一棵二叉排序树。（且是递归定义）
二叉排序树方便关键字的检索，插入操作。
4️⃣二叉排序树：(Sort Binary Tree)
几种特殊的二叉树：
二叉树第 i 层上的结点数为2的i-1次。(i => 1)
三叉树 共有结点数：1/2 * 3的k次-1
深度为 k 的二叉树至多有2的k次-1个结点。(全满)【以2为公比的等比数列求和（0～k-1）】
三叉树 共有结点数：1/2 * 3的h次-1
高度为 h 的二叉树至多有2的h次-1个结点。
n与n0关系：n = 2n0 - 1 +n1
对任何一个二叉树，都有：n0 = n2 + 1。
一般二叉树高度：⌊log₂n⌋+1 ～ n
具有n个结点的二叉树，要求其最小高度：——>当二叉树构成完全二叉树时，高度最小。h = log₂ n + 1 = log₂ 50 + 1 = 5+1 = 6。 所以h=6。
二叉树的性质：
可以问：构造二叉树时：结点最多：——> 满二叉树。若为完全二叉树，则根据前h-1层为满二叉树，数形结合的看。结点最少：——> 1+(h-1)*2。高度最高：——> h = n （ 二叉树高度范围：⌊log₂ n⌋+1 ~ n ）高度最低：——> 完全二叉树 在 二叉树 中 高度最低。（最小深度）
二叉树高度为 h，且只有度为0，2，则结点数 至少( 最少 )有：1 + 2(h-1) = 2h-1 （即第一层一个，其余h-1层均有两个结点）
二叉树的题型：
需要存逻辑，就按满二叉树存。
二叉树的顺序存储就是将所有结点存储到一组连续的存储单元中（数组），并能通过结点间的物理位置关系反映逻辑关系（双亲和孩子关系）。顺序存储时，结点间的次序关系要能反映结点间的逻辑关系。用数组下标（编号）来表示结点之间的父子关系。（根据二叉树的性质）
编号过程：首先把树根结点定为1，然后按照层次从上而下，每层从左至右的顺序，对每一结点进行编号。 即将二叉树上编号为 i 的结点存储在一维数组下标 i-1 的分量中。
顺序存储的随机存取，i，2i-1，2i+1。
便于访问每一结点的 双亲 和 左右孩子。
二叉树的顺序存储结构适用于 完全二叉树 和 满二叉树。这样既能充分利用、节省存储空间，又能利用数组元素的下标值确定结点在二叉树中的位置，以及结点之间的关系。
对退化的二叉树（每个结点都是单分支），或单分支较多的一般二叉树来说不实用，空间浪费较为严重，空间利用率低。
存储一般二叉树的时候，为了能让数组下标反映二叉树中结点的关系，所以添加用0表示的空结点，让其与完全二叉树对照，再存到一维数组的相应分量中。
最坏情况下，高度为 h 的h个结点的单支树，竟然需要2的h次 -1个存储单元。
顺序存储的二叉树 插入、删除等操作不方便。
缺点：
顺序存储结构：
即为二叉链表存储结构——参考双链表：一个data数据结点，两个指针，一个左指针，一个右指针。
若增加父结点的指针，双亲域，即为三叉链表。
一般二叉树 通常采用链式存储结构存储。
利用n+1个空链域存储结点直接前驱与后继，形成线索链表。
特点：对于n个结点，有2n个指针域；n-1个前驱指针 (辫子，非空指针)；n+1个空链域。【2n-(n-1)=总分支-非空指针=空指针】
声明：typedef struct BTNode { ElemType data; struct BTNode *lchild; struct BTNode *rchild;}BTNode
链式存储结构：
静态链表存储：
二叉树的存储结构：
这里的访问是指对结点进行某种处理，包括：读、写、修改和输出结点信息。
定义：二叉树的的遍历( Traversal )是指沿某条搜索路径巡访二叉树，对每个结点访问一次且仅访问一次。
作用：通过一次完整的遍历，可使二叉树的结点信息由非线性排列变为某种意义上的线性序列。
根左右
先序(根)遍历：
void preOrder(BTNode *T) { if (T != NULL) { visit(T->data); preOrder(T->LChild); preOrder(T->RChild); }}
void inOrder(BTNode *T) { if (T != NULL) { preOrder(T->LChild); visit(T->data); preOrder(T->RChild); }}
void preOrder(BTNode *T) { if (T != NULL) { preOrder(T->LChild); preOrder(T->RChild); visit(T->data); }}
递归算法：
左根右
中序(根)遍历：
左右根
后序(根)遍历：
由L D R，分别表示遍历左子树、访问根结点、遍历右子树，则可得到三种递归的遍历方法：
遍历种类：
以上三种遍历方法中，递归遍历左右子树的先后顺序是不变的( 即访问所有叶子结点的先后顺序完全相同 )，都是 先左后右。只是访问根结点的顺序不同，所以“序”指 根结点的访问顺序。
因为每个结点仅访问一次，故 二叉树的遍历时间复杂度都是O(n)。
递归工作栈的深度 即为 树的深度
二叉树递归遍历都需要借助工作栈，其中先序序列为入栈顺序，中序序列为出栈顺序。
递归算法和非递归算法的转换【借助栈】，即二叉树的中序非递归算法借助栈实现。
定义：是指从第一层( 即根 )开始，按从上到下，每层从左到右的顺序对结点逐个进行访问。
层序遍历 借助 队列 实现。
特点：因上下层结点之间具有父子关系，所以在层序遍历中必然是先访问的结点，其孩子也先访问。
遍历过程：设置一个队列（初始化为空）来保存待访问的结点( 已访问结点的孩子 )，首先将二叉树的根结点A入队，然后出队，visit访问出队结点（此时可对结点加操作），根A出完后，将其所有孩子入队BC；队头B出队，访问B，将B的所有孩子入队；C出队，访问C，将C的所有孩子入队。
层序遍历：
由二叉树的 先序遍历 和 中序遍历 可以唯一地确定一棵二叉树。
由二叉树的 后序遍历 和 中序遍历 可以唯一地确定一棵二叉树。
由二叉树的 层序遍历 和 中序遍历 可以唯一地确定一棵二叉树。
当两个结点的前序序列为XY，而后序序列为YX时候，则X为Y的祖先
例：前序ae bdc 后序bcd ea，所以a为根结点，e为a的孩子结点。此时在a的孩子结点中，先序ebdc，后序bcde，可知e是bcd的祖先。
由二叉树的 先序遍历 和 后序遍历 不能唯一地确定一棵二叉树，但可以确定二叉树中结点的祖先关系。
由遍历序列反过来构造二叉树：
本题本质是求以序列 a b c d 入栈，可以得到多少个出栈序列。1/n+1 C2n n = 14。
以先序序列abcd的不同二叉树共有多少个？
也意味着一个结点不可能同时有左右孩子。即仅有N1
某二叉树的前序序列 与 后序序列 正好相反，则该二叉树一定是 只有根结点 或 单支树（只有左子树或只有右子树）即二叉树的高度等于结点数 h=n。
二叉树遍历的题型：
二叉树的遍历：
先来对比 传统二叉树 与 线索二叉树：遍历二叉树后存储至传统二叉链表，其仅能体现一种父子关系，不能直接得到结点在遍历中的前驱或后继。
定义：利用空链域存放指向结点的直接前驱或后继的指针。这种附加的指针称为“线索”，加上线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树。
ltag = 0 lchild域指示结点的左孩子ltag = 1 lchild域指示结点的直接前驱
rtag = 0 rchild域指示结点的右孩子rtag = 1 rchild域指示结点的直接后继
标志域说明：
1表线索，0表孩子。
规定：若某一结点无左子树，则令lchild指向其前驱结点，若无右子树，则令rchild指向其后继结点；再增加两个标志域标识指针域，用以指向左右孩子或前驱后继。
作用：引入线索二叉树，就是为了加快查找结点前驱和后继的速度。这样就可以像遍历单链表那样方便、更快地遍历二叉树。
二叉树 是逻辑结构，所以 线索二叉树 是二叉树在计算机内部的 一种存储结构。
特点：线索二叉树是一种物理结构。线索二叉树即加上线索的二叉链表，还是属于链表，链表是链式存储结构。
对二叉树以某种次序遍历 使其变为 线索二叉树 的过程称为 线索化。线索化的本质就是二叉树的遍历。
设n个结点，共有2n个指针，用了n-1个，除根结点，2n-(n-1) = n+1 个空指针。
每个叶结点有2个指针，每个度为1的结点有一个指针，所以空指针= 2n0 + n1 ，又因为n0=n2+1，所以指针个数为：n0+n1+n2+1 = n+1。
空指针的计算：
子主题
总结：先序不好找前驱，后序不好找后继【不能有效解决此问题，其中双亲结点的前后驱未知，即此时线索帮不上忙，只能按常规方法全遍历所得】
不是每个结点通过线索都可以直接找到其前驱和后继。
线索二叉树的题型：
线索二叉树：
所以线索化的过程就是在遍历的过程中修改中空指针的过程。可用递归算法。
线索二叉树构造的实质 是将二叉链表中的 空指针 改为 指向前驱或后继的 线索。
线索化的实质就是遍历一次二叉树。
对二叉树按照不同的遍历次序进行线索化，可以得到不同的线索二叉树，包括先序、中序和后序。
设指针p指向当前访问的结点，指针pre指向刚才访问过的结点，由此记录下遍历过程中访问结点的先后关系。
建立font color=\"#569230\
例：以结点p为根的子树的 font color=\"#569230\
构造线索二叉树：
二叉树
树与二叉树
在二叉排序树中，如果先删除分支结点后再插入它，则会导致二叉排序树的重构，其结果与之前不再相同。
题型：
⌊log₂ n⌋
树的存储要求既要存储结点的数据元素，也要存储结点之间的逻辑关系。能唯一的反映树中各结点之间的逻辑关系
定义：用一组连续的存储空间存储树的所有结点，同时在结点中附加一个指示器(伪指针)，指示其双亲结点在数组中的位置。 根结点下标为0，伪指针域为-1
该存储结构利用了每个结点( 根结点除外 )，只有唯一双亲的性质，可以很方便地找到任一结点的双亲结点。若无则找到了根结点。
双亲表示法 容易找双亲，但若找结点的孩子时，需要从头到尾遍历整个结构。
应用：适合于 找双亲多，找孩子少 的情景——>并查集
注意：区别树的顺序存储结构与二叉树的顺序存储结构的不同：树的顺序存储结构中，数组下标代表结点的编号，下标中所存的内容指示了各结点间的关系。二叉树的顺序存储结构中，数组下标既代表了结点的编号，也代表了二叉树中各结点的关系。当然二叉树属于树，所以可以用树的存储结构存储。但树不能用二叉树的存储结构。
双亲表示法：（顺序存储）
定义：是指 将每个结点的孩子结点用单链表链接，则n个结点有n个孩子链表，此时n个结点就有n个孩子链表（叶结点的孩子链表为空表）， 这n个结点头指针 即每一个双亲又构成一个线性表，以顺序结构存储。
孩子表示法 容易找孩子，找双亲时需要遍历孩子链表。
应用：适合于找孩子多，找双亲少的情景——>服务流程树（如：客服系统）
孩子表示法：（顺序+链式存储）
定义：孩子兄弟表示法，又称二叉树表示法，二叉链表表示法。即以二叉链表作为树的存储结构。每个结点包含三部分：结点值；指向该结点的第一个孩子结点和下一个兄弟结点（沿此域可以找到该结点的所有兄弟结点）。分别命名：firstchild域，nextsibling域。转换成的BT 左孩子表示父子，右孩子表示兄弟。
例：若要访问结点x的第i个结点，只要先从firstchild域中找到第一个孩子结点，然后沿着孩子结点的nextsibling域连续走i-1步，便可找到x结点的i孩子。
孩子兄弟表示法容易找孩子。
优点：最方便实现 树转换成二叉树 的操作。
缺点：是从当前结点找其双亲结点比较麻烦。若为每个结点添加parents域，则也能方便的查找到其双亲。
孩子兄弟表示法：（链式存储）
树的常用三个存储结构：
将 双亲表示法 与 孩子表示法 的优缺相结合，即给n个有孩子链表的n个结点 加上伪指针指示其双亲 在数组中的位置。
存储结构优化：
树的存储结构：
定义：由于 二叉树 与 树 都可用 二叉链表 作为存储结构，则以二叉链表作为媒介可导出树与二叉树之间的对应关系。
从物理结构来看，树与二叉树的二叉链表是相同的，只是指针拐个弯，解释不同。
给定一棵树，总可以找到唯一的一棵二叉树与树对应。
根据树的二叉链表吧表示定义可知，任何一棵树对应的二叉树，其右子树必空。
由于根结点没有兄弟，所以所以对应的二叉树没有右子树。
树转二叉树的规则；每个结点的左指针指向它的第一个孩子，右结点指向它在树中的相邻右兄弟。——《左孩儿右兄弟》规则
层序处理，将结点 所有孩子 串成 糖葫芦 斜着放在其左子树。
树 转 二叉树：
层序处理，将结点左孩子串成的糖葫芦拆开，平放在此结点下方。
二叉树 转 树：
—————————————————————————————————————————————————————————————————————
然后再进行 各棵树 内部的 树转二叉树。
森林中各棵树的根结点为 平级兄弟结点，将所有树的根用右指针串成糖葫芦斜着放。
森林 转 二叉树：
然后在森林内部进行 二叉树 转 树。
将二叉树 根结点及其右子树糖葫芦串 拆开 作为 森林内部多棵树的根结点。
二叉树 转 森林：
题型：（画出）
树、森林 与 二叉树 的转换：
== 对应二叉树的 先序遍历
先根遍历：若树非空，先访问根结点，再依次遍历根结点的每棵子树。遍历子树时仍遵循 先根后子树 的规则。
== 对应二叉树的 中序遍历
后根遍历：若树非空，先访问根结点的每棵子树，再访问根结点。 遍历子树时仍遵循 先子树后根 的规则。
层序遍历：按层序依次访问各结点。
树的遍历 （三种） 是指用某种方式反问树中的每个结点，且仅访问一次。
== 对应二叉树的 先序遍历
访问森林中第一棵树的根结点。先序遍历第一棵树中 根结点 的子树森林。先序遍历除第一课树之后剩余的树。
先序遍历：
中序遍历森林中第一棵树根结点的子树树林。访问第一棵树的根结点。中序遍历除第一棵树之后剩余的树。
中序遍历：
森林的遍历 (两种)
树和森林的遍历：
因为树根结点没有兄弟结点，所以对应二叉树没有右分支。
一棵树转换成二叉树后，其左分支表示树中的孩子关系，二叉树的右分支表示树中的兄弟关系。
一棵树转成二叉树后，由于只有一棵树，所以根结点是没有右子树的；根据左孩子，右兄弟规则，得出转换成的二叉树是唯一的。
二叉树与森林的关系：森林中树的棵树 等于 其对应二叉树的的根结点及其右孩子(兄弟)数目。或丛根结点开始不断访问根结点右孩子。
森林转二叉树的本质：相当于 用孩子兄弟表示法 表示此森林。
n = n0 + nk树中所含边数为e （这些边均是由这个m个非叶子结点发出的，所以e=m*k）又因为 e = n-1 n=e+1 = mk+1 = n0+m所以n0 = m(k-1)+1
若T有m个非叶子结点，问T有几个叶子结点？
最多则为1 -> h-1为满二叉树，h层均为叶结点：公式h = log k [n *(k-1)+1] 得n*(k-1) = k得h-1次 n=k得h-1次 / k-1。
最少结点的正则k叉树 树形为：第一层一个根结点，第2-h层分别只有1个分支结点和k-1个叶结点，h层有k个叶结点，故2 -> h 每层均有k个结点。所以n = 1 + (h-1)k
若T的高度为h，则T结点树最多为？，最少为？
k叉树，已知每个非叶子结点 都有k个孩子，则称T为 正则k叉树。
解：孩子兄弟表示法又叫 左孩子右兄弟表示法，森林中的叶结点因为没有孩子结点，当转换为二叉树时，该结点就没有左孩子结点。
将森林F转换成对应二叉树T时，F中叶结点的个数 等于 T中左孩子指针为空的结点个数。
解：因为看右子树，最右侧结点就是森林 根结点。
解：在树转二叉树时，若几个叶结点具有共同的双亲，则转换成二叉树后 就仅有一个叶结点。（即最右侧结点）
若树中的任意两个叶结点都不存在相同的双亲，树中叶子数 才等于 对应二叉树的叶子数。
一棵树中的叶子数在什么时候 等于其对应的二叉树的叶子数 ？
若森林只有一棵树，则根结点的右指针为空。
若森林中不只一棵树，根据树转二叉树，是用孩子兄弟表示法 表示树 得，根结点右指针不为空。根结点右指针指向森林中第二棵树的根结点。
利用二叉链表存储森林时，根结点的右指针可能为空，也可能不为空。
二叉树B右指针域为空代表着该结点没有兄弟结点。森林中的树从第二棵树开始连接在第一棵树的右子树中，因此最后一棵树的根结点右子树为空。
同理，每个非终端结点，的孩子层序处理，转换后，最后一个孩子的右指针也为空。
综上：对应二叉树中 无右孩子结点 的个数 = 分支结点数 + 1.
解：什么叫右指针域为空？
F ——> B 若F中有n个非终端结点，则B中右指针域为空的结点有几个？
在森林的二叉树中，若M、N是同以父结点的左儿子和右儿子，在在该森林中，M和N可能无公共关系。
所以在一棵树中，结点总是比边数多一。引申至森林，结点数比边数多几，就是森林中包含几棵树。
n个结点的树，有n-1条边。
树与森林
描述
数据结构：如何用数据描述表示现实世界的问题，包括数值型问题，非数值型问题。
处理
算法：就树如何高效地处理数据，以解决实际问题。
程序 = 数据结构 + 算法
相同数据类型是指每个数据元素所占空间一样大
第 i 个是表示位序，从1开始。数组下标从0开始。
定义：线性表是 相同数据类型 的n(n >= 0)个数据元素 的 有限 序列
顺序表可以随机存取O(1)，插入和删除是O(n)链式存储的查询是O(n)，插入和删除是O(1)单链表只能单向按顺序查找
线性表(Linear List)
元素之间的关系可以由存储单元的邻接关系直接表现。
定义：用顺序存储的方式实现线性表。顺序存储 即把逻辑上相邻的元素存储在物理结构也相邻的存储单元中。
插入：(n + 0)n/2 * 1/n = n/2
删除：(n-1 + 0)n/2 * 1/n = (n-1)/2
顺序存储的线性表中移动元素的次数
在长度为n的顺序表第i个位置插入一个元素时，元素移动次数为n-i+1，即要移动该位置及其之后的所有元素
当已知顺序表中元素的查找概率时，为使查找成功的平均查找长度达到最小，则应交换表中元素次序，查找概率大的放在顺序表的前列
静态分配：利用静态数组存储顺序表。数组长度一旦确定即不可改变
顺序表的实现：
顺序表
线性表的链式存储结构称为链表。每个存储结点不仅包括结点本身信息，且饱含元素与元素之间的逻辑关系信息，分别称数据域与指针域。链式存储设计时，各个不同结点的存储的存储空间可以不连续，但结点内的存储单元地址必须连续。
单链表：单向性，单链表中只有一个指示直接后继的指针域（因此从某个结点出发只能顺着指针往后查找其他结点，若查找结点的直接前驱，则需重新从表头出发）。
单链表中访问后继结点的时间复杂度为O(1)，访问前驱结点的时间复杂度为O(n)
单链表带头结点的优点：1️⃣使链表 首结点的插入和删除操作 与其他结点一致。无需特殊处理。2️⃣无论单链表是否为空，均有头结点，统一空表与非空表的处理过程。
头插法与尾插法：头插法：是将新的结点插入到当前链表的表头上（插入在头结点之后，原开始结点之前）。形成一个“逆序”的序列。 s->next = L->next; L->next = s;尾插法：是将新的结点插入到当前链表的表尾上（将s插入到r尾指针之后）。形成一个“顺序”的序列。 r->next = s; r=s; (原r 与 现r)
不带头结点的单链表：空表：head == NULL; //头指针直接指向第一个结点
带头结点的单链表：空表： head->next == NULL;
单链表
双链表的结点中有两个指针域，一个指向直接后继，一个指向直接前驱。
从任一结点出发可以快速访问其他结点。
双链表可以从任一结点出发可以快速找到某一结点的前驱结点和后继结点。
尾插法：r = L; //r始终指向尾结点，开始时指向头结点s->data = a[i]; r->next = s； //将s插入r之后s->prior = r;r = s; //将r指向尾结点
双链表的头插法与尾插法：头插法：s->data = a[i]; //创建数据结点ss->next = L->next;if(L->next != NULL) //若L存在数据指针 则需要 修改前驱指针 L-> next->prior = s; L->next = s;s->prior = L;
双链表
因此从表中任一结点出发，都可以找到链表中的其他结点。
有的单循环链表不设头指针，只设尾指针。这是因为 单循环链表有了尾指针之后 r->next 就转化为了 头指针——>这样对表头 表尾 的操作就都成了O(1)。
单循环链表在实现约瑟夫问题时不需要头结点。
单循环链表：单循环链表的 尾结点 next域 指向头结点，使整个单链表形成一个环。
因此从表中任一接结点出发，都可以找到链表中的其他结点。
双循环链表：双循环链表的尾指针next指向头结点，而头指针的prior指针指向尾结点，这样使整个双链表形成两个环。
循环链表
与指针型描述的线性链表有所不同。
静态链表是利用一维数组去描述一个线性链表。
静态链表的整形变量cur便于在不设“指针”类型的高级程序语言中使用链表结构。这样数组的一个分量表示一个结点，游标（指针域cur）代替指针 用以指示结点在数组中的相对位置。数组的0结点看成头结点，其指针域指示链表的第一个结点。
静态链表结构需要预先分配一个较大的存储空间，但在做线性表的插入和删除操作时不需要移动元素，只需要修改指针，故仍具有链式存储结构的主要优点。
静态链表
链式存储的定义和特点
给不带头结点的单链表的头上插入一个新结点，相当于无头结点的头插法：将t的下一结点指向h，然后将t改为新的头结点。 t->next = h; h=t;
一个单链表中，有头尾两个指针，执行什么操作与链表的长度有关删除第一个元素。 删除最后一个元素。 在第一个元素前插入一个元素。 在最后一个元素后插入一个元素。单链表中想找到最后一个元素只能按顺序遍历。
p是尾指针，p=q就表示要删除的是尾结点，所以在删除尾结点后，要将尾指针指向头结点。
当删除最后一个结点时候要进行特处：if(p == q) p=h;
单链表中删除时候：先存再删
如删除链表的第一个元素：【先存后删】【p尾指针，q临时指针存待删结点】q = h->next; h->next = h->next-next； (h->next = q->next;)if(p==q) //p=q的含义是，待删除结点事尾元素时候 p=h; //将尾指针指向头结点 free(q);
以单链表方式存储的队列，在进行删除时候一般只用修改队头指针即可，但有一种情况就是出队以后是空队列了，需要修队尾指针以对准队头指针。所以链队列的删除运算时，头尾指针都有可能修改。
若用单链表来表示队列，则选用带尾结点单循环链表来实现表头出队（删除），表尾入队（插入）。
先建表，后依次插入建立有序表 O(n的平方)
先排序，后依次建表 O(n*log2n)
给定n个元素的一维数组，建立一个有序单链表的最低时间复杂度是：O(n*log2n)
所以删除表尾元素的时间复杂度与与表长有关。
所有单链表，不管是循环单链表还是有尾指针的单链表，在删除尾结点时要十分注意！O(n)。因为删除结点后需要找到其前驱，将尾指针指向尾结点前驱。
只要是单链表 删除结点 都需要格外注意
注意⚠️所有的删除都要找到删除元素 的前驱
若用单链表来表示队列（队列：队尾插入，队头删除），所以用带尾指针的循环单链表。
两个单链表的拼接：将长度为n的链接在长度为m的单链表之后时间复杂度为：其实就是找到m链表的尾指针，然后将其指向n头结点即可。
答：0 / 50个，因为题干中给的是线性表，没说是顺序存储还是链式存储
线性表a0--a100中，删除a50需要移动多少个元素？
删除p指针：【先连p的前驱，后连p的后继】p->next->prior = p->prior; p->prior->next = p->next
*p之后插入*s：先处理待插入结点的后继，再处理后一结点的前驱；然后处理前一结点的后继，再处理待插入结点的前驱。s->next = p->next; p->next->prior = s; p->next = s; s->prior = p; 1️⃣ ——> 2️⃣ <—— 3️⃣ ——> 4️⃣ <——先处理待插入结点的前驱，再处理待插入结点的后继；然后处理前一结点的后继，再处理后一结点的前驱。 s->prior = p; s->next = p->next; p->next = s; s->next->prior = s; 1️⃣ <—— 2️⃣ ——> 3️⃣ ——> 4️⃣ <——先处理待插入结点的前驱，再处理待插入结点的后继；然后处理后一结点的前驱，再处理前一结点的后继。 s->prior = p; s->next = p->next; p->next->prior = s; p->next = s; 1️⃣ <—— 2️⃣ ——> 3️⃣ <—— 4️⃣ ——>
*p之前插入*q：先处理前一结点的后继，再处理待插入结点的后继；然后处理待插入结点的前驱，再处理后一结点的前驱 p->prior->next = q; q->next = p; q->prior = p->prior; p->prior = q; 1️⃣ ——> 2️⃣ ——> 3️⃣ <—— 4️⃣ <——
需要注意的顺序，所有最先开始的是1️⃣s->next = p->next插入删除不能断链，不能有歧义。也就是4️⃣要在3️⃣前。先p->next->prior = s。再p->next = s。若相反，则会导致歧义：s->prior = s。
1️⃣在最前，4️⃣在3️⃣前。
共性就是：平行的去处理，且箭头都对应完整
非循环链表可以没用头结点，有头结点只是更好，操作一致循环链表必须要有头结点，否则循环没有意义，找不到循环的头了（没有腰带扣啦）
单循环链表的主要优点：从表中任一点出发都能扫描遍历到整个链表
单循环链表的判空条件：head->next == head;
单循环链表的判空条件：L->next == L 【翻译过来就是头结点的指针域 与 L的值相等。而不是与L的地址相等】
某线性表常用的操作是：在最后一个结点后插入一个新结点 或 删除第一个元素 最适合用：带有尾指针的单循环链表在最后一个结点后插入一个新结点 或 删除最后一个结点 宜采用：双向链表
其实问题的核心就是要访问被删除结点以及被删除结点的前驱。
这样的话带尾结点的单循环链表还不够，因为带尾指针只是能更快的访问到尾结点，访问到尾结点的前驱还需要再遍历一圈。
带头结点的双循环链表好万能。
所以选用带头结点的双循环链表即可，这样从头结点出发到过来访问尾结点以及其前驱。
要实现在链表末尾的 插入 和 删除 操作，最好选用？
如果是带头结点，要找到被删除结点的前驱结点。首元结点即第一个数据结点，所以其前驱正是头结点，此时带带头/尾指针找到前驱都是O(1)。
如果是不带头结点，首元结点的前驱就是链表的尾结点。所以带头指针的找前驱是O(n)，带尾结点的不带头结点的找前驱是O(1)。
若删除循环单链表的首元结点所花费的时间为O(n)，则判断该结构是带头结点还是不带头结点，带不带尾指针？
0或1
这时需要记得特处。因为题干没有说明是否为空，因为空链表也合适此代码。head->next 就是首元结点，首元结点的next抱住头结点。线性表为空时，长度L为0。线性表有了首元结点后，长度L就是1。
某线性表用带头结点的循环单链表存储。头指针为head，当head->next->next == head成立时，线性表的长度可能为？
单循环链表
双循环链表的插入与删除。
双链表最突出的特点是：访问前后相邻结点更加灵活、便利。
在双链表中必须带头结点，带头结点的双链表可以在表中迅速找到任意位置 != 随机存取
双循环链表
一维数组还能实现很多结构：栈，树，图
定义：静态链表是使用一维数组实现的链式存储结构
特点：整体需要分配较大的连续的存储空间。 适合 插入、删除 操作，不需要移动大量元素。 静态链表一旦定义，其容量固定不变。 还是不适合随机存储哈 会造成浪费现象
题型总结
链表
顺序存储结构只能通过其物理上的顺序邻接来体现逻辑结构
链式结构使用的是指针，指针的创建与设置比较万能，代表性强故可更方便的表示各逻辑结构
顺序存储与链式存储的对比
顺序表可以用以为数组表示，所以顺序表与一维数组在逻辑结构上相同？答：顺序表的三大特点：有限；数据类型相同；必须连续存储。而一维数组可以不用连续存储。且栈，队列，树都可以用一维数组表示。
存取方式是指读/写方式，顺序表支持随机存取，根据起始地址+元素符号，可以很方便的访问任何一个元素。
线性表的顺序存储结构是一种 随机存取的存储结构。
线性表
字符串简称串，串，是由 零个或多个 字符组成的序列。是线性结构，也是一种特殊的线性表。
S=“String177”，S是串名，“ ”‘ ’括起来的是串值，串中字符的个数n是串长，n=0是空串。
子串：串中任意多个连续的字符组成的子序列称为该串的子串。主串：包含子串的串。某个字符在串中的序号称为 该字符在串中的位置。
空格串 ！= 空串，由一个或多个空格组成。
串与线性表的区别：1️⃣两种数据结构所操作的数据对象不同：串——>字符集，线性表——>数据种类多。2️⃣串的基本操作以 子串 作为操作对象。 线性表的操作以 单个元素 作为操作对象。
串的定义：
舍弃0号位的 定长数组 +最后用len变量标记串长度。
定长顺序存储表示：
采用链表的方式存储，每个结点存储多个字符，若最后一个结点未满，就填入 # 补足。
块链存储表示：
串的存储结构：
用sub返回串s第pos个字符起 长度为len的子串
若主串S中存在与串T值相同的子串，则返回它在主串第一次出现的位置。
S>T，返回值>0S=T，返回值=0S<T，返回值<0
用T返回S1，S2连接而成的新串。
返回串S的元素个数
求串长 StrLength（S）
串的基本操作：
串的模式匹配：在主串S中，查找是否存在子串T；若存在，则返回T得位置Index
BF算法 朴素模式匹配算法：——O(m*n)
KMP算法：——O(m+n)
KMP算法Pro：
串的模式匹配：
串
收藏
收藏
职业：暂无
0 条评论
回复 删除
下一页
