＜长篇文章！！＞数据结构与算法的重要知识点与概要总结 ( ?? ω ?? )??临近考试和查漏补缺的小伙伴看这一篇就都懂啦~

一、数据结构概论

1、数据元素和数据项
数据由数据元素组成，即数据元素是数据的基本单位，而数据元素又由若干个数据项组成，数据项是组成数据元素的最基本、不可分割的最小单位。
2、数据结构
数据结构，是数据元素中存在一种或多种特定关系的数据元素的集合，即数据结构就是带结构的数据元素集合，包括逻辑结构、存储结构（物理结构）和数据的运算共三个方面，三个方面缺一不可。另外，可以用抽象数据类型定义一个完整的数据结构。

探究一种数据结构的方法可分为三个步骤：
1、数据如何组织？
2、数据如何存储？
3、数据的运算如何实现？

3、逻辑结构
逻辑结构指的是数据元素之间在逻辑上的关系，可分为线性结构和非线性结构，线性结构是一对一的关系，例如有线性表、栈、队列、串、一维数组等；非线性结构是一对多或多对多的关系，例如有二维数组（多维数组）、广义表、树（二叉树）、图等。

4、存储结构（物理结构）
数据的逻辑结构在计算机中的表示称为存储结构，也称为物理结构，包括数据元素的表示和关系的表示，根据其存储特点可以分为四种存储结构，即顺序存储结构、链式存储结构、索引存储结构和散列存储结构。

以上四种存储结构，由于每种存储结构都有其优缺点，不能直接地说哪种存储结构最优，只能说在针对某种数据结构中需要选择不同的存储结构时，应该选择符合其特点的数据结构才是最优的。

5、顺序存储结构
顺序存储由存储单元的邻接关系体现，即把逻辑上相邻的元素存储在物理位置上也相邻的存储单元里，其中数据是连续的。该存储结构的优点是可以实现随机存取，每个元素占用最少的存储空间，缺点是由于只能使用相邻的一整块存储单元，从而会产生较多的外部碎片。

以线性表为例，通过顺序存储的线性表称为顺序表，它是将线性表中所有元素按照其逻辑顺序，依次存储到指定存储位置开始的一块连续的存储空间里；而通过链式存储的链表中，每个结点不仅包含该元素的信息，还包含元素之间的逻辑关系的信息。

6、链式存储结构
链式存储不要求逻辑上相邻的元素物理位置上也相邻，而是通过指示元素存储地址的指针来体现元素之间的逻辑关系，其数据是可离散的。该存储结构的优点是充分利用了所有的存储单元，不会造成碎片现象，但缺点是由于通过指针来表示逻辑关系，所以指针也要存储，从而占用额外的存储空间，即链式存储的存储结构所占存储空间分两部分，一部分存放结点的值，另一部分存放表示结点间关系的指针（结点内的存储单元要求连续，而不同结点的存储空间可以不连续），例如，顺序表的存储密度=1，而链表的存储密度<1，是由于结点中含有指针域。另外，链式结构只能顺序存取，不能随机存储。

以线性表为例，单链表是通过链式存储的，其每个结点除了存放数据元素之外，还存储指向下一个结点的指针；而顺序表是顺序存储的，其每个结点只存放数据元素。顺序存储结构可以随机存取、顺序存取，而链式存储结构只能顺序存取，顺序存储结构不仅可用于存储线性结构，还能用于树、图等非线性结构。

针对线性表，以上两种存储结构在线性表中的实际选择：
在一般情况下，若需对表进行频繁的插入、删除操作，此时适合选链式存储，因为顺序表平均需要移动近一半的元素且耗费时间（其插入和删除算法的平均时间复杂度为O(n)），而链表在插入和删除操作时不需要移动元素，只需修改指针；当若表的总数基本稳定，且很少进行插入和删除操作，则顺序表相较于链表可以充分发挥其存取速度块、存储利用率高的优点。
7、索引存储结构
索引存储在存储数据元素的同时还需要建立附加的索引表，其中的索引项的形式为关键字和地址，其数据是可离散的。该存储结构的优点是在查找数据元素时很快、容易找到，而缺点是由于附加了索引表，从而占用了额外的存储空间，同时，若需要增加和修改数据时，需修改索引表，会花费较多时间。

例如，查找算法中树型查找的B树、B+树的应用到了索引存储结构。

8、散列存储结构
散列存储是根据数据元素的关键字直接计算其存储地址，也称为哈希存储（Hash），其数据是可离散的。该存储结构的优点是在对数据元素进行增加、删除结点操作时很快，而缺点是若定义的哈希函数不能完全贴合情况，则会发生元素存储单元的冲突，而减少冲突从而会花费时间和一定的空间上的开销。

例如，哈希表即为一种基于散列存储结构的查找表。

二、算法概论

1、算法分析
将解决问题的确定方法和有限步骤称为算法，在计算机中，算法指的是对特定问题求解步骤的一种描述，是若干条指令的有穷序列。算法分析是对一个算法需要多少计算时间和存储空间作定量的分析，分析算法的效率以求改进是其目的。通过设计一个具有正确性、可读性、健壮性、高效率（执行速度快，时间复杂度低）和低存储（不费内存，空间复杂度低）的算法，再加上合适的数据结构，从而构成一个良好的程序。

程序 = 算法 + 数据结构

2、算法的特性
算法具有五个特性，分别是输入、输出、确定性、可行性和有穷性。

算法可以有零个或多个输入，但算法至少有一个或多个输出。

3、时间复杂度
时间复杂度是对算法运行时间的数量级，有两种度量方法，分别是事后统计法和事前分析估算法，计算算法的时间复杂度属于一种事前分析估算的方法。通常，对一个算法的时间复杂度考察三个方面，即最好情况、平均情况和最坏情况，从而对应最好时间复杂度、平均时间复杂度和最坏时间复杂度，其中平均时间复杂度是指所有输入在等概率的情况下，该算法的期望运行时间。时间复杂度为O(1) 常数阶算法的效率最高，而像O(2ⁿ) 、 O(n!) 、 O(nⁿ)这类的算法的效率最低，如下图：

4、空间复杂度
空间复杂度是指定义该算法所需要耗费的存储空间，根据其规模函数f(n)，可记为O[f(n)]，若算法需要的存储空间是常量，则其空间复杂度为O(1)。
5、递归算法
一个递归算法必须包括终止条件和递归部分，例如，二叉树的先序、中序、后序遍历中每一次函数调用都会在内存栈中分配空间，都运用了递归算法。另外，n的阶乘也是一个递归算法，该递归算法停止条件是n=0，函数可定义如下：
$$n!=\{\begin{array}{ll}1& \text{，n=0}\\ n(n?1)!& \text{，n>0}\end{array}$$
6、贪心法
贪心算法不考虑整体上最优，而只考虑局部上最优来解决问题，即每次选择的都是最优的解决方案，不考虑该决策对整体的影响，即贪心算法的时间复杂度一般较低，但缺点是不能保证得到全局上的最优解。贪心法的两大性质为最优子结构性质【可分割】和贪心选择性质【局部最优】。

贪心算法在处理一些情况下，可以得到最优解的很好近似方案，例如，哈夫曼编码、求最小生成树中的普里姆算法（Prim）、克鲁斯卡尔算法（Kruskal）、求单源最短路径中的迪杰斯特拉算法（Dijkstra）等算法。

7、分治法
分治法分为分解、治理两大步骤，主要在于将问题划分成相互独立的子问题。分解，是将问题分解成多个规模上较小、内容上相互独立、性质上与原问题相同的子问题；治理，是对各个子问题直接求解，若仍不容易解决，则再进行进一步分解后再求解，由于性质相同，所以求解子问题的解决方法和原问题是相同的；另外，治理中包含合并，是将得到的各个子问题的解进行合并，从而得到原问题的解。若各个子问题之间不是相互独立的时，则会造成重复，分治法会有很高的时间复杂度。

分治法在查找中的二分（折半）查找和排序中快速排序、归并排序中应用，例如快速排序基于分治思想，通过多次划分操作来实现排序

8、动态规划
动态规划通常解决的是具有重叠子问题性质和最优子结构性质的问题，其中解决子问题只需一次，解决后会将其解保存并重复使用，从而避免重复计算。动态规划通常采用自底向上的方式，通过先解决子问题，再解决大问题的方式进行求解。动态规划适合用于优化问题，并且能够保证得到全局最优解。但对比贪心法、分治法算法，由于需要存储各种状态，所以其需要的空间更大。

贪心法、分治法与动态规划的对比：
这三种算法共同点都是在解决问题时通过划分子问题、解决子问题的方法来的，贪心法的解决方案呈线性，每次都是选择局部最优，分治法主要在于将问题划分成相互独立的子问题，动态规划主要解决子问题重叠的情况，且每个子问题只解决一次，子问题的解被存储从而避免了重复计算。

9、搜索算法
（1）穷举搜索
穷举搜索法也被称为穷举法，其基本思想是将问题的所有的候选解都枚举出来，然后对候选解按照某种顺序进行逐一枚举和检验，并从中找出符合问题要求的候选解作为问题的解。其优点是实现简单且易于理解，适合规模较小的问题，但当问题的规模较大时，由于需要运行问题所有的候选解消耗大量的时间，从而导致算法的效率大大降低。
（2）回溯法
回溯法用到了深度优先搜索（DFS）的思想，首先，通过穷举所有可能的解（明确搜索范围），从初始状态出发，以深度优先搜索来搜索解，若当前结点不满足，则会退一步回溯到上一个结点尝试其他选择，直到最后找到包含问题解的结点。当问题规模较大时，由于需要穷举所有可能的解，此时回溯法的搜索效率较低。【找出解空间树中满足约束条件的所有解】

另外，回溯法中还运用了剪枝函数（隐约束）来避免无效搜索，所以可以说回溯法是一种带有约束函数（约束条件）或限界函数（限界条件）的深度优先搜索方法。

（3）分支限界法
分支限界法中通常采用广度优先搜索（BFS），以最大收益（最小耗费）的方式来搜索解空间树，其中的限界就是利用上界和下界来提高搜索效率，即搜索解空间树中利用上界和下界的信息来剪枝搜索树的分支，舍弃导致不可行解或导致非最优解的分支。【找出解空间树中满足约束条件的一个解】

回溯法的适用场景有：n皇后问题、子集树（0-1背包问题、最大团问题）、排列树（旅行商问题、批处理作业调度问题）、组合树（图的m着色问题）等等；
分支限界法的适用场景有：0-1背包问题、旅行商问题、集装箱装载问题、电路设计中的布线问题等等。

10、NP完全理论
P类问题是较“容易”的问题，在计算机中可以在多项式时间内解决，而NP类问题是较“复杂”的问题，只能验证是否存在解（解是否正确）。主要区别在于时间复杂度，P类问题时间复杂度较低，而NP类问题可以在多项式时间内的不确定性算法来进行判定或求解问题，其求解过程较困难。

常见的P类问题有排序、搜索算法等等，但不是所有的排序算法都是P类问题，例如，排序中的快速排序、堆排序和归并排序是P类问题，其平均时间复杂度呈多项式，而由于插入排序、冒泡排序、简单选择排序的平均时间复杂度都呈指数级，所以不属于P类问题，属于NP类问题。

NP完全问题是NP问题的一个子类，可以说它比NP问题更复杂的问题，也是只能在多项式时间内验证问题的解，例如多项式变换技术问题、布尔可满足性问题以及旅行商问题（TSP）、哈密尔顿回路问题等等。

三、线性表

1、线性表
线性表是具有相同数据类型的n个数据元素的有限序列，其中n≥0，即线性表可以为空（有限序列，可以为空），当n=0时，称线性表是一个空表。线性表是一种逻辑结构，且为线性结构，即数据元素之间是一对一关系。另外，线性表中表头元素无前驱，表尾元素无后继。
2、线性表的存储结构
通过不同的存储结构，可以将线性表分为由顺序存储结构的顺序表和由链式存储结构的链表（链表包括单链表、双链表、循环链表等），顺序存储结构是通过物理上相邻的地址来表示逻辑关系，而链式存储结构是通过指针来表示逻辑关系。另外，链表还可以细分，例如，静态链表中指针是通过结点的数组下标表示，它是借助数组来描述链式结构。

顺序表和链表的优缺点如下：
顺序表实现简单，可以随机存取，其存储密度大，但是执行插入、删除操作需要移动大量元素，效率低，另外其存储空间需事先分配，容易造成空间浪费或溢出。
链表不支持随机存取，只能顺序存取，通过指针来体现元素之间的逻辑关系，存储密度比顺序表小，其执行插入、删除操作不需要移动元素，只需修改指针，效率高，另外它还支持动态分配存储空间，不会造成空间浪费或溢出。

3、顺序表的插入、删除和查找
（1）顺序表的插入
若在顺序表的表尾插入元素，则不需要执行元素后移操作，即最好情况，所以最好时间复杂度为O(1)。若在顺序表的表头插入元素，需要执行n次元素后移操作，即最坏情况，所以最坏时间复杂度为O(n)。设在顺序表第i个位置插入元素的概率为pi=1/(n+1)，即设插入概率相同，此时为平均情况，在长度为n的线性表中插入一个结点，所需移动元素的平均次数为n/2，故顺序表插入操作的平均时间复杂度为O(n)。

名称	插入时间复杂度
最好时间复杂度	O(1)
最坏时间复杂度	O(n)
平均时间复杂度	O(n)

（2）顺序表的删除
若删除顺序表的表尾元素，则不需要执行元素后移操作，即最好情况，所以最好时间复杂度为O(1)，与顺序表的插入操作的最好情况一样。若删除顺序表的表头元素，则执行n次移动操作，即最坏情况，所以最坏时间复杂度为O(n)，与顺序表的插入操作的最坏情况一样。设删除顺序表第i个位置上元素的概率为pi=1/n，即设删除概率相同，在长度为n的线性表中删除一个结点，若删除第一个结点需移动n-1次，……，删除第n个结点移动0次，即平均情况，所需移动元素的平均次数为(n-1)/2，故顺序表的删除操作的平均时间复杂度为O(n)。

名称	删除时间复杂度
最好时间复杂度	O(1)
最坏时间复杂度	O(n)
平均时间复杂度	O(n)

在长度为n的顺序表中删除第i个结点（1≤i≤n）时，需要移动n-1个结点，而在第i个结点（1≤i≤n）前插入一个结点时，需要移动n-i+1个结点。

（3）顺序表的查找
若查找元素在顺序表的表头，则在常数级即可查找到该元素，即最好情况，最好时间复杂度为O(1)。若查找元素在顺序表的表尾或不存在时，需要遍历整个顺序表，即最坏情况，最坏时间复杂度为O(n)。平均情况下，按值查找一个元素的平均次数为(n+1)/2，故顺序表的按值查找的平均时间复杂度为O(n)。

平均情况下，顺序表的各种操作数据元素的平均比较次数和平均时间复杂度如下表【插入n/2，删除减一，查找加一】：

名称	插入	删除	查找
平均比较次数	n/2	(n-1)/2	(n+1)/2
平均时间复杂度	O(n)	O(n)	O(n)

4、单链表
单链表是链式存储的，其每个结点除了存放数据元素之外，还存储指向下一个结点的指针，链表中不要求结点所占空间连续，但是一个结点内部空间必须连续；而顺序表是顺序存储的，其每个结点只存放数据元素。单链表无论是否带有头结点，其头指针都指向单链表中第一个结点，在带头结点的单链表中，头结点只作为单链表存在的标志且不存储数据。在带头结点的单链表，若L->next==NULL时，则该单链表为空，即头结点的指针域next为空时，此时单链表为空表。

头指针具有标识作用，用头指针代指链表的名称，同时可以防止链表为空；头结点的设置保证了插入元素和删除元素操作的统一性，带有头结点的单链表，其存储位置存放在头结点L的指针域中，指向单链表的第一个结点。

5、单链表的插入、删除
（1）插入操作——后插操作
单链表中，在指针 *p 所指向的结点之后插入结点 *q，先将 *q与原本 *p的指针域指向的结点相连，再与p相连【先连后，再连前】，代码如下：

q->next=p->next;
p->next=q;

（2）插入操作——前插操作
在单链表中在 *p的前插入一个 *q指向的新结点，以temp为中间变量，即通过中间变量temp来交换数据域data的代码部分【先后插，再交换】，代码如下：

q->next=p->next;
p->next=q;

temp=p->data;	//交换数据域
p->data=q->data;
q->data=temp;

（3）单链表的删除
在单链表中删除一个以前驱 *p， *q指向的结点，查找后删除的步骤可概括为【先定位，后断开释放】，将 *q指针指向要删除的结点，p为其前驱结点，代码如下：

q=p->next;	//先定位，定位删除位置
p->next=q->next;	//断开q与p的连接，p与下一个结点连接
free(q);	//通过free()函数进行释放

也可以在单链表中直接删除*p指向的结点，代码如下：

q=p->next;	//先定位，定位删除位置
p->data=p->next->data;	//与后继结点交换数据域data
p->next=q->next;	//断开q与p的连接，p与下一个结点连接
free(q);	//通过free()函数进行释放

6、双链表
根据线性表的链式存储结构中每一个结点包含的指针个数，可将线性链表分成单链表和双链表。双链表是在单链表结点上增添了一个指针域prior，指针域prior指向当前结点的前驱结点，即此时链表的每个结点中都有两个指针域prior和next，从而可以很容易通过后继结点找到前驱结点，故访问前驱和后继结点的时间复杂度都为O(1)。一个带头结点L的双链表，若L->next == NULL时，则该双链表为空；一个不带头结点的双链表，若L==NULL时，则该双链表为空。

7、双链表的插入、删除
（1）双链表的插入
由于双链表可以很快地找到前驱结点，所以双链表的插入、删除操作的时间复杂度都为O(1)。双链表的插入操作可以概括为【先连后，再连前】，若在指针 *p 指向的结点之后插入结点 *q，首先，新结点q与原本 *p的指针域相连，即下一个结点，然后将结点q插入到结点p之后，再将其prior和next域相连，代码如下：

q->next=p->next;
p->next->prior=q;
q->prior=p;
p->next=q;

这里的代码插入不唯一，插入操作必须保证的是不能断链，即不能导致*p的后继结点的指针丢掉。

（2）双链表的删除
双链表的删除的代码如下：

p->next=q->next;
q->next->prior=p;
free(q);

8、循环单链表
（1）循环单链表的定义
循环单链表的优点是从任一结点出发都可以访问到链表中的每一个元素。在带头结点L的循环单链表中，若L== head->next时，循环单链表为空；在不带头结点的循环单链表中，若L==NULL时，循环单链表为空。

（2）循环单链表的查找
在一个带头结点的循环单链表中：
若只设置头指针L，则查找表头结点的时间复杂度为O(1)，查找表尾结点需要依次遍历整个链表，即时间复杂度为O(n)，而查找一个结点的前驱结点时的时间复杂度为O(n)；若只设置尾指针R，这样的好处是可以使查找链表的开始结点和终端结点很方便，其查找时间都为O(1)，而查找一个结点的前驱结点时的时间复杂度为O(n)。
（3）循环单链表的插入
循环单链表的插入操作与单链表类似，也是【先连后，再连前】，若在指针 *p 指向的结点后插入结点 *p ，步骤是：首先将q的指针域与p结点原本的指向下一个结点的指针域相连，即q->next=p->next，然后再将q结点与p结点相连，即p->next=q，如下代码：

q->next=p->next;	//先连后
p->next=q;		//再连前

（3）循环单链表的删除
循环单链表的删除操作也与单链表类似，删除的步骤可概括为【先定位，后断开释放】，将*q指针指向要删除的结点，p为其前驱结点，如下代码：

q=p->next;	//先定位，定位删除位置
p->next=q->next;	//断开q与p的连接，p与下一个结点连接
free(q);	//free()函数释放结点

9、循环双链表
（1）循环单链表的定义
循环双链表基于双链表，头结点L的prior域指向表尾结点，查找表头结点和表尾结点的时间复杂度均为O(1)，查找一个结点的前驱结点时的时间复杂度也为O(1)。一个带头结点L的循环双链表，若L->prior== L&&L->next ==L时，则该双链表为空。（头结点的prior和next域都指向其本身时为空）

（2）循环单链表的插入
若要在指针 *p 指向的结点后插入结点 *p，其代码如下：

q->next=p->next;
p->next->prior=q;
q->prior=p;
p->next=q;

（3）循环单链表的删除
将*p指针指向要删除的结点，其代码如下：

p->next->prior=p->prior;
p->prior->next=p->next;
free(p);

10、静态链表
根据指针的连接方式，链表可分成静态链表和（动态）链表。静态链表借助数组来描述链式结构，每个数组元素有两个分量，一是数据元素的值，二是指针，指针指向下一个元素在数组中的位置 (下标)。静态链表在插入和删除操作时只需修改指针，而不需要不移动数据，但静态链表不支持随机存取。另外，若定义的数组太大，有可能浪费较多的存储空间。

四、栈

1、栈
栈是被限制存取点的线性表，只允许在一端进行插入或删除操作，与队列具有相同的逻辑结构，都属于线性结构，区别在于对其中元素的处理不同，栈遵循的原则是先进后出（FILO），即后进的元素先被取出来。由于它是一种线性表，所以有两种方式：顺序存储结构和链式存储结构，即顺序栈和链式栈。另外，栈的插入操作称为进栈，栈的删除操作称为出栈。

栈有以下应用场景：
①递归及函数调用；
②表达式求值（例如，中后缀表达式、括号匹配等等）；
③进制转换（例如，十进制数转为二进制数等等）；
④迷宫求解；
⑤缓存机制；
⑥用栈对二叉树进行前、中、后序遍历；
⑦用栈模拟队列。

2、共享栈
使用共享栈可以更加有效地利用存储空间，降低发生上溢的可能，通过让两个顺序栈共享一个一维数组空间，可以使其中一个栈可用该空间的一半或以上，将这两个顺序栈的栈底分别设置在数组空间的两端，其中两个栈的栈顶指针都指向栈顶元素，当top1=-1时顺序栈1为空，当top2=MaxSize时顺序栈2为空，另外当两个栈顶指针相邻，即top2-top1=1时，此时共享栈满。

3、顺序栈
顺序栈存储空间的实现是使用数组来存储栈元素的，通过一组数组地址的连续的存储单元来存放从栈底开始至栈顶的数据元素，同时设置一个栈顶指针top，用于指示当前栈顶元素的位置。判断顺序栈是否为空栈的条件是S.top==-1，判断顺序栈是否为满栈的条件是S.top==MaxSize-1。
（1）进栈
将一个元素插入顺序栈中，即进栈，首先应判断栈是否为满【进栈先判满】，即S.top==MaxSize-1，进栈的操作可以概括为指针先加1，然后再入栈，代码如下：

/*进栈操作*/
bool StackPush(SqStack &S,int x) {
	if(S.top==MaxSize-1)//若栈已满，则报错
		return false;
	++S.top;//top指针始终指向栈顶，新的元素进栈，所以指针先加1
	S.data[S.top]=x;//将进栈元素的值传入并入栈
	//S.data[++S.top]=x;
	return true;
}

（2）出栈
将一个元素从顺序栈中删除，即出栈，首先应判断栈是否为空【出栈先判空】，即S.top==-1，出栈的操作可以概括为先出栈，然后指针再减1，由于栈的特性，只能先进后出，即从栈顶进行删除操作，代码如下：

/*出栈操作*/
bool StackPop(SqStack &S,int x) {
	if(S.top==-1)//若栈为空，则报错
		return false;
	x=S.data[S.top];//出栈
	S.top--;//指针减1
	//x=S.data[S.top--];
	return true;
}

4、链栈
由于顺序栈的数组的大小是固定的，不能动态分配大小，而链栈相比顺序栈的最大优势就是它可以动态地分配存储空间。

（1）进栈
同单链表当中动态分配新结点的步骤类似，创建一个值为x的新结点p（通过malloc()函数动态分配，需在开头加头文件#include<stdlib.h>），首先将x值赋给新结点p的数据域中，然后将新结点p插入到链栈的栈顶前，最后再将新结点p作为当前栈顶元素，完整代码如下：

/*进栈（插入操作）*/
void PushStack(LinkStack &S, int x) {
	StackNode *p;
	p = (StackNode*)malloc(sizeof(StackNode));//动态分配创建一个新结点p
	p->data = x;	//将x放入新结点p的数据域中
	p->Lhead = S;	//将新结点p插入到当前链栈的栈顶前
	S = p;	//将新结点p作为栈顶元素
}

（2）出栈
出栈操作首先必须判断栈是否为空【出栈先判空】，即S==NULL，然后通过变量x，将栈顶元素S->data赋给x取出，然后将指针p指向原栈顶（为要删除的结点），并将栈顶S指向下一个结点，最后通过free()函数释放要删除的结点p，完整代码如下：

/*出栈（删除操作）*/
bool PopStack(LinkStack &S,int &x) {
	StackNode *p;
	if(S==NULL)//若栈为空，则报错
		return false;
	x=S->data;//x记录当前栈顶元素
	p=S;//p指针指向原栈顶
	S=S->Lhead;//S指向下一个结点
	free(p);//释放栈顶元素
	return true;
}

5、栈的应用——前、中、后缀表达式转换
将常用的中缀表达式转换为前缀表达式、后缀表达式后，可以通过栈的相关原理来实现具体的出栈 、入栈操作逻辑，从而可以一样完成与中缀表达式相同的运算。
（1）中缀表达式转换为前缀表达式的思路
首先，按照运算优先级将所有的操作数都加上括号；然后，将运算符移至相对应的括号前；最后，将括号去掉，即可得到前缀表达式。
（2）中缀表达式转换为后缀表达式的思路
与前缀表达式相反，第二步将运算符移至相对应的括号后，然后再去掉括号即可。

五、队列

1、队列
队列与栈一样，它也是一种特殊的线性表，其操作受限，与栈具有相同的逻辑结构，都属于线性结构，区别在于其中元素的处理不同，栈遵循的原则是先进后出，而队列的原则是先进先出（FIFO），栈只允许在一端进行插入、删除操作，而队列只允许在一端进行插入、另一端进行删除操作。

队列的应用场景有以下：
①缓冲区（例如计算机与打印机中间的打印数据缓冲区）；
②页面替换算法；
③图的广度优先搜索、树的层次遍历，都借助到了队列的基本思想。

2、循环队列
基于顺序存储结构的队列即为顺序队列，由于顺序队列会出现“假溢出”的问题，所以可以将顺序队列的一维数组首尾相连形成一个环状（在逻辑上视为一个环连接起来），即为循环队列。初始条件时循环队列为空，其队头指针等于队尾指针，即判空代码为Q.front==Q.rear，指针front、rear都指向同一位置。判断循环队列是否为满队就要另外写代码，规定：牺牲一个存储单元来区分是否满队，入队时少使用一个队列单元，即队头指针在队尾指针的下一个位置时，此时作为满队的条件【队尾指针加1取余等于队头指针】，代码如下：

//判断循环队列满队
if((Q.rear+1)%MaxSize==Q.front)
	return true;

（1）入队
其中队头指针、队尾指针加1时通过取余运算实现，从而防止队列的“假溢出”。进队操作针对队尾指针，即Q.rear=（Q.rear+1）%MAXSIZE。每次入队操作时，首先判断队列是否为满队【入队先判满】，然后先送值到队列的末尾，然后再将队尾指针Q.rear加1取模（通过%实现），代码如下：

//入队（插入操作）
bool EnterQueue(SqQueue &Q,int x){
	if((Q.rear+1)%MaxSize==Q.front)	//若队列为满，则报错 
		return false;
	Q.data[Q.rear]=x;	//送入入队数据元素x的值 
	Q.rear=(Q.rear+1)%MaxSize;	//队尾指针加1取模 
	return true;
}

（2）出队
出队操作针对队头指针，即Q.front=（Q.front+1）%MAXSIZE。每次出队操作时，首先判断队列是否为空队【出队先判空】，然后先取队列的队头元素，然后再将队头指针Q.front加1取模（通过%实现），代码如下：

//出队（删除操作）
bool PopQueue(SqQueue &Q,int x) {
	if(Q.front==Q.rear)	//若队列为空，则报错 
		return false;
	x=Q.data[Q.front];	//取出队头数据元素x的值 
	Q.front=(Q.front+1)%MaxSize;	//队头指针加1取模 
	return true;
}

（3）输出循环队列中的元素个数
若要输出当前循环队列中的元素个数，首先判断队列是否为空，然后，通过队尾指针减队头指针加上MaxSize的值与MaxSize取余，可得到数据元素个数，即(Q.rear-Q.front+MaxSize)%MaxSize，代码如下：

//循环队列的数据元素个数
bool NumQueue(SqQueue Q){
	if(Q.front==Q.rear)	//若队列为空，则报错 
		return false;
	int num=(Q.rear-Q.front+MaxSize)%MaxSize;
	printf("当前循环队列的数据元素个数为：%d\n",num);
}

3、链队列
链队是通过带有队头指针和队尾指针的单链表实现的，使用链队的好处是可以避免出现队满溢出的问题，且适用于数据元素变动较大的情形时，若使用单链表来表示队列，则使用带尾指针的循环单链表最合适。

用循环链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别为O(1)和O(n)；若只设尾指针，则出队和入队的时间复杂度为O(1)和O(1)，所以使用带尾指针的循环单链表最合适。

六、串

1、串
串是一种线性结构，它也是一种特殊的线性表，与栈和队列一样，由零个或多个字符组成的有限序列，串的数据元素必须是字符，其通常以字符串的形式出现。由任意多个连续的字符组成的子序列称为串的子串，包含子串的串称为主串，线性表是以单个元素进行相关操作，而串是以子串进行相关操作的。

空串是任意串的子串，任意串是自身的子串。

2、定长顺序存储
通过静态数组实现定长顺序存储，一组地址连续的存储单元存储串值的字符序列，其中每个串都被分配一个固定长度的ch[MAXLEN]数组。
3、链式存储
对不确定长度的串进行存储时，就要用到动态存储方式，这里可以采用链式存储，链式存储串中，每个结点有两个域，分为数据域（data）和指针域（next），数据域由于存放串的各字符，指针域用于存放后继结点的地址。使用链式存储的优点是插入、删除运算方便，但缺点是存储、检索效率低，其空间利用率低。
4、堆分配存储
与定长顺序存储一样，也是采用一组地址连续的存储单元来存放串值的字符序列，但堆分配存储的存储空间是动态分配的，通过malloc()和free()函数来完成动态存储的分配和释放。分配成功时，返回一个指向起始地址的指针*ch作为串的基地址，它指向动态分配存储区首地址的字符指针，若分配失败则返回NULL。
5、KMP算法
串的模式匹配也称为串的定位，搜索串中的子串，若存在则返回子串在串S中第一次出现的位置。一般的字符串匹配算法的时间复杂度为O(m×n)，而KMP算法的时间复杂度为O(m+n)，其主串指针不用回溯，当主串的长度很大需要部分匹配和一次不能调入内存时，其优点较一般匹配更突出。

七、多维数组与矩阵

1、数组
数组是由n（n≥1）个相同数据类型的数据元素组成的有限序列，在定义数组时，会为数组分配一个固定大小的内存空间，用来存储元素，数组在被定义后，其维度不可以被改变。

数组在确定其维度和维界后，元素的个数是固定的，所以不能进行插入和删除运算。数组中最常见的两种操作是查找和修改。

2、多维数组
数组可分为一维数组和多维数组（常见的有二维数组），二维数组可以看作一维数组的一维数组。顺序表是一个一维数组，所以它是线性结构，与栈、队列、串的逻辑结构相同，而多维数组则是典型的非线性结构，也可以说它是嵌套的线性结构。

例如，一个二维数组A[3][4]在内存中实际上是一个长度为3的一维数组，每个元素是一个长度为4的一维数组，即对应三行四列，其中元素是从上到下、从左到右依次存储的，如下：

	0	1	2	3
0	[0，0]	[0，1]	[0，2]	[0，3]
1	[1，0]	[1，1]	[1，2]	[1，3]
2	[2，0]	[2，1]	[2，2]	[2，3]

由于数组中是从下标0开始的，所以一个m行n列的二维数组中，最开始的元素是[0，0]，最后的元素是[m-1，n-1]，上面三行四列的二维数组A[3][4]中的最后一个元素即为[2，3]。

3、多维数组的存储
二维数组的存储较一维数组不一样，有两种存储方式，可分为行优先存储和列优先存储，前者是先按每行存储满后再继续下一行，后者相反先按每列存储满后再继续下一列。

例如，定义一个二维数组A[3][3]，在连续的内存空间里，如下：

若按照行优先存储，以A[2][0]为例，在存储A[2][0]之前，是这样存储的：

而按照列优先存储，以A[1][1]为例，在存储A[1][1]之前，是这样存储的：

4、特殊矩阵与稀疏矩阵
在数据结构中，矩阵是一个按照长方阵列排列的复数或实数集合。它通常由一组数的全体在括号内排列成m行n列（横为行，竖为列）的一个数表，并被称为m×n阵。若一个矩阵有n行n列，则称该矩阵是一个n阶方阵。相同的元素或零元素在矩阵中的分布存在一定规律的矩阵称为特殊矩阵，反之则为稀疏矩阵。简单的来说，特殊矩阵既然特殊，说明其中有很多相同或者有零元素，且存在一定规律在矩阵中分布。常见的特殊矩阵有对称矩阵、反对称矩阵、上/下三角矩阵、对角矩阵等等，例如对角矩阵中，只有对角线上有元素，其余元素均为零：

5、特殊矩阵的压缩存储
对矩阵压缩的目的是节省存储空间。若一个n阶方阵满足A_i×j=A_j×i，则称为对称矩阵。由于对称矩阵中上三角部分和下三角部分的元素对应相同，在存储对称矩阵时，为了避免空间的浪费，可以只存储上或下三角部分的元素，将其存放在一个一维数组中，数组的大小为1+2+……+n=n(1+n)/2。例如，矩阵B如下，将其视为一个对称矩阵：

若对其进行压缩存储，若按行序将元素通过一维数组存储实现，首先确定数组大小，由于矩阵是4×4的方阵，阶数为n=4，所以需要的一维数组大小为n(1+n)/2=(4×5)/2=10，由于是对称矩阵，只存储上或下三角部分的元素，这里以存储上三角元素为例：

6、稀疏矩阵的压缩存储
稀疏矩阵中非零元素的分布与特殊矩阵相反，是没有规律的。稀疏矩阵中大部分元素都为0，且与非零元素的分布一样，也是没有规律的，稀疏矩阵的两种存储结构是三元组表（数组）和十字链表。
（1）三元组表
为了压缩存储稀疏矩阵，在存储时不仅要存储矩阵中非零元素的值，同时还要存储该元素所在的行与列，从而组成一个三元组表（行、列、值），依此减少了存储空间。由于是将稀疏矩阵中的非零元素以及其对应的行、列号以三元组的形式存储在一个数组中，所以经过这种压缩存储后就无法通过数组的下标直接存取矩阵的元素，失去了随机存取的特性。

//以整型int为例，可替换其他类型
typedef struct{
	int i,j;	//行与列
	int x;		//值
}Sparsematrix;

例如，一个稀疏矩阵A，进行压缩存储：

对应的三元组表，如下：

i（行）	j（列）	x（值）
1	1	4
1	3	2
2	0	5

例如，有一个100×90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示矩阵时，求所需的字节数。

解析：三元组表包括行、列、值，每个整型数占2字节，所以10个非0元素占3×2×10=60字节，另外还有三元组表中行数、列数和总的非零元素个数共6个字节，一共60+6=66字节。
（2）十字链表
十字链表法中，稀疏矩阵的行和列都用一个带头结点的链表表示，从而对应着五个分量：行、列、数据域、指向下方结点的指针和指向右方结点的指针，其结点的结构如下：

八、广义表

1、广义表
广义表也是一种特殊的线性表，是由n（n≥0）个数据元素组成的有限序列。线性表中的数据元素只能是单个元素（原子），它是不可分割的，而广义表中的数据元素既可以是原子，也可以是一个广义表（包括空表和非空表），广义表通过圆括号“()”括起来，通过逗号“,”隔开表中的各个数据元素。

2、广义表的表头和表尾
广义表是可以递归的，一个广义表也可以是其自身的子表，广义表中的第一个元素称为广义表的表头，而剩余数据元素组成的表称为广义表的表尾，广义表的表头和表尾可以看作通过函数head()和tail()对广义表操作。任何一个非空广义表，其中表头可能是单个元素（原子）或广义表，但表尾只可能是广义表，其原因是广义表的取表尾tail()是非空广义表除去表头元素后，剩余元素组成的表，所以不可能是原子。

3、广义表的深度和长度
广义表的深度通过括号的层数求得，而长度是广义表中所含元素的个数。【深度层数，长度个数】

例如，一个空广义表G=()，括号层数为1，所以广义表的深度为1，而由于是空表，所以广义表的长度为0；
例如，一个广义表H=((a,b),(c,(d,e)))，括号层数为3，所以广义表的深度为3，最高层为(c,(d,e))，逗号隔开了原子( c )和广义表( d,e )，元素个数为2，所以广义表的长度为2。

4、广义表表示二叉树
根据广义表中“ 数据元素既可以是原子，也可以是一个广义表（包括空表和非空表) ”这一点可以来表示二叉树，即通过(根结点，根结点的广义表)的形式来表示，其中可以嵌套。例如，下面是一个满二叉树：

通过广义表表示该二叉树：
(A , ( B , ( D , E ) ) , ( C , ( F , G ) ) ) )
这个二叉树的解释如下：
根结点是A，它的左孩子是B，B的左孩子是D，B的右孩子是E。
根结点A的右孩子是C，C的左孩子是F，C的右孩子是G。

九、树与二叉树

1、树和森林
树是一种非线性结构，它是树形结构，含有n个有限元素的数据元素集合（其中n≥0，n=0时为空树），线性结构中的数据元素之间是“一对一”的关系，而树形结构中的数据元素之间是“一对多”的关系。树（n>0）满足两个条件，一个树有且只有一个根结点，其中根结点没有前驱结点，除了根结点其他所有结点都只有一个前驱结点，剩下的结点为m(m≥0)个互不相交的非空集合，其中每个集合又可以称为一棵树，即根的子树。

树中两个结点之间的路径由两个结点间所经过的序列构成，路径长度是路径上所经过的边的个数，而树的路径长度是指根结点到每个结点的路径长的总和。如下图是一棵树，其中结点的关系是一对多：

另外，由m（m≥0）棵互不相交的树的集合称为森林，如下图是一个森林：

2、结点
以下图这个二叉树（每个结点最多有两个结点的树）为例，介绍结点的相关知识。
（1）叶子结点：叶子结点也称为终端结点，它是没有子结点的结点（度为0），例如下图中，D、E、F、G都是叶子结点；
（2）孩子结点：一个结点的后继结点称为该结点的孩子结点，例如下图中，A的孩子结点是B、C；
（3）双亲结点：一个结点称为其后继结点的双亲结点，例如下图中，B、C的双亲结点是A，D、E的双亲结点是B；
（4）兄弟结点：在同一双亲结点下的孩子结点互为兄弟结点，例如下图中，B、C互为兄弟结点，它们有共同的双亲A，另外D、E互为兄弟结点，它们有共同的双亲B。

3、树的性质
（1）树中结点的子结点（孩子）个数称为该结点的度，而树中结点的最大度数称为树的度，例如上图这个树中，结点B有两个子结点D和E，所以结点B的度为2，结点D的度为0，树的度为2。【二叉树的度小于等于2，只有一个结点的二叉树的度为0】

• 树中结点的个数等于所有结点的度数之和加1。

例如，上图的结点的个数为N=（2+2+2）+1=7。

• 另外，树中结点的个数也等于总分支数加1，其中总分支数=1n₁+2n₂+3n₃+…+mn_m（度为m的结点引出m条分支）。

例如，上图树中，总分支数为6，故结点个数为6+1=7。

（2）树中结点的最大层数为树的高度（深度），结点的深度是由树的根结点开始由上至下，而结点的高度是由树的叶子结点开始由下至上的。

• 度为m的树中第i层上（i≥1），至多有m^i-1个结点。

4、二叉树
二叉树是一种逻辑结构，它是一种特殊的树，与普通的树相比，普通树中结点的后继结点可以是任意多个，而二叉树中结点的后继结点最多只能有两个，二叉树中不存在度大于2的结点，即二叉树的度小于等于2。二叉树是由一个根结点以及两个不相交的非空树，分别称为左子树和右子树，同样，左子树和右子树也是二叉树。另外，二叉树是一个特殊的有序树（其中结点的各子树从左到右有序），左右子树的次序不能任意交换。另有两种特殊的二叉树，满二叉树和完全二叉树。

满二叉树是完全二叉树的特例，可以说，若一棵树是满二叉树，则它必是完全二叉树，但不能说一个完全二叉树必是满二叉树。

5、二叉树的性质

• 二叉树中，设度为0、1和2的结点个数分别为n₀、n₁和n₂，即结点总数N=n₀+n₁+n₂；另外，叶子结点数等于度为2的结点数加1，即n₀=n₂+1。

例如，下图完全二叉树中，可以验证一下，度为2的结点个数为4，所以度为0的结点（叶子结点）个数为n₀=4+1=5。

• 二叉树中，分支总数=N-1=n₁+2n₂。

例如，下图完全二叉树中，分支总数等于9-1=8，或者等于度为1的结点个数加上两倍度为2的结点个数，即n₁+2n₂=0+2×4=8。

• 二叉树中，第i层上至多有2^i-1（i≥1）个结点，这种即为满二叉树的情况。

例如，在一棵二叉树中，第四层至多有2^4-1=2³=8个结点。

• 高度为h的二叉树至多有2^h-1个结点，另外高度为h的m叉树中，至多有（m^h-1）/（m-1）个结点。

例如下图是一个二叉树，其高度（深度）为4，h=4，即至多有2⁴-1=15个结点，这个二叉树并不是一个满二叉树，而是一个完全二叉树。

• 对于n个结点，可以组成N种不同的二叉树，如下：
  $$N=\frac{C_{2n}^n}{n+1}$$

例如，由3个结点A、B、C构成的二叉树，可以有$$N=\frac{C_6^3}{3+1}=20/4=5种不同的二叉树。$$

6、满二叉树与完全二叉树
（1）满二叉树与完全二叉树的定义

满二叉树与完全二叉树的特点如下表：

二叉树名称	特点
满二叉树	深度（高度）为h，具有2h-1个结点的二叉树，其中每层结点都是满的
完全二叉树	树中除最后一层外，其余层的结点都是满的的二叉树，或结点的右子树缺少连续的若干个结点

另外，完全二叉树的另一种定义是，若对深度为h，结点数为n个的二叉树进行编号后，各结点的编号与深度为h的满二叉树中相同位置结点上对应的编号均相同时，则这种二叉树为完全二叉树。

（2）满二叉树与完全二叉树的性质

• 一棵高度为h的满二叉树的结点总数为2^h-1，若它有n个结点，则含有（n+1）/2个叶子结点，含有（n-1）/2个分支结点，其高度为h=log₂(n+1)。

推导过程：由于是满二叉树，所以度为1的结点为0，即n₁=0，由于二叉树的性质n₀=n₂+1以及n=n₀+n₁+n₂，可得n=2n₀-1，所以叶子结点n₀=（n+1）/2；
由于分支总数=n-1=n₁+2n₂，且n₀=n₂+1、n₁=0，所以分支总数=2n₂=n₀-1=（n-1）/2；
高度为h的满二叉树的结点数为1+2+4+……+2^h-1=2^h-1（首项为1，公比为2的等比数列），即n=S_n=[a₁(1-qⁿ)]/1-q=2^h-1，从中解出h，高度为h=log₂(n+1)。

• 由于完全二叉树的结点排法，可知叶子结点尽可能地往左边排，故度为1的结点个数只有一个或零个。

例如，已知一棵完全二叉树的第6层有8个叶子结点，求该完全二叉树的最多和最少结点数。由于第6层有叶子结点，所以完全二叉树的高度可能为6或7，当为6时，完全二叉树拥有最少结点数，由于前5层都为满二叉树，即1+2+4+8+16+8=31+8+39；当为7时，前6层都为满二叉树，其中有8个结点没有左右结点，即1+2+4+8+16+32+(32-8)×2=63+48=111，故该完全二叉树的最多和最少结点数分别为39和111。

• 一棵含有n个结点的完全二叉树中，叶子结点个数等于n/2【n为偶数】或（n+1）/2【n为奇数】。

例如，已知一棵完全二叉树有1001个结点，所以其叶子结点个数就等于（1001+1）/2=501个。

例如，已知一棵完全二叉树具有124个叶子结点，求其最多和最少结点数。当结点数n为偶数时，结点数最大，124=n/2，解得n=248，n为奇数时，结点数最小，124=（n+1）/2，解得n=247，故最多和最少结点数为248和247。
另一种解法是，根据n₀=n₂+1可知，n₀=124，n₂=123，由于N=n₀+n₁+n₂，且该树为完全二叉树，根据完全二叉树的性质，度为1的结点个数只有一个或零个，即N=124+1+123=248和N=124+0+123=247，所以最多和最少结点数为248和247。

• 一棵树高为h的完全二叉树至少有2^h-1个结点，至多有2^h-1个结点，总结点N与高h的关系是h=?log₂(n+1)?。即对于一棵含有n个结点的二叉树，当它为完全二叉树时，具有最小高度，最小高度为h=?log₂(n+1)?或?log₂n?+1（其中 ? ?表示向上取整，取比自己大的最小整数，? ?表示向下取整，取比自己小的最大整数）；当它为一棵单支树时具有最大高度，为一个线性表，即最大高度为n。

例如，设一颗二叉树的结点个数为50，求其最小高度，我们知道当这棵树为完全二叉树时高度最小，n=50，即h=?log₂50?+1 =5+1=6，所以其最小高度为6。

例如，求一棵具有1025个结点的二叉树的高度，首先我们知道当二叉树为单支树时此时具有最大高度，即每层只有一个结点，最大高度为1025；另外，当二叉树为完全二叉树时高度最小，此时即最小高度为?log₂1025?+1=10+1=11，故该二叉树的高度为11~1025。

7、平衡二叉树
平衡二叉树的特点是其中任一结点的左右子树的深度之差都不超过1，如下是一个平衡二叉树：

8、二叉树的存储结构
（1）顺序存储
二叉树的顺序存储结构通过使用一组地址连续的存储单元数组进行存储，其中根结点的编号设定为1，若结点的编号为i，则对应存储的一维数组下标为i-1，但是顺序存储结构存在浪费情况，就是在最坏情况下，一个高度为h的二叉树需要占据2^h-1个数组存储单元（非完全二叉树）。
（2）链式存储
二叉树的链式存储结构通过链表实现，一个二叉树链表结点由数据域和指针域组成，除了data数据域用于存放结点的信息外，每个结点含有两个指针，左指针域lchild和右指针域rchild，分别指向该结点的左孩子结点和右孩子结点，它们用于存放该结点左/右子树的地址，当左/右子树不存在，其指针域为空（“^”），如下图：

例如，下面这个树的链式表示如下：

对应的链式结构如下：

从中可以得到一个结论：

• 在由n个结点组成的二叉链表中，含有n+1个空指针域，含有n-1个非空指针域。

例如，上图二叉树中，含有8个结点，它含有8+1=9个空指针域，含有8-1=7个非空指针域。

9、二叉树的遍历
二叉树的遍历是按某种规定的顺序来对访问树中的所有结点，且每个结点仅被访问一次，由于二叉树由根结点（D）、左子树（L）和右子树（R）组成，可分为二叉树的先、中、后遍历另外还有每一层的遍历，即层次遍历，如下表：

名称	遍历顺序
先序遍历	根、左、右
中序遍历	左、根、右
后序遍历	左、右、根

二叉树的中序遍历序列中，由“左中右”的遍历关系以及根结点可以确认二叉树的左右子树，同时由二叉树的前序或后序遍历序列再确定结点中的父子关系，从而结合可以唯一确定一棵二叉树。

二叉树的先、中、后序遍历都可以通过递归算法实现，递归结束的条件是T==NULL，即当二叉树为空时，遍历结束。

（1）二叉树的先序遍历（DLR）
二叉树的先序遍历中，首先是根结点，遍历完根结点的左子树，然后再遍历完根结点的右子树，依次下去至所有结点都遍历到，例如下图二叉树：
其先序遍历序列为ABDCE。
（2）二叉树的中序遍历（LDR）
二叉树的中序遍历中，首先是遍历完根结点的左子树，然后是根结点，最后遍历完根结点的右子树，依次下去至所有结点都遍历到，通过中序遍历可以得到一个递增的有序序列。

例如，一个二叉树中，根据中序遍历可知，中序遍历序列的最后一个结点一定是从根结点开始沿着右子树走到最底的结点，若它为叶子结点，则先序遍历序列和中序遍历序列的最后一个结点都为该结点；若不为叶子结点，它还有一个左子结点，则该左子结点是前序遍历序列的最后一个结点。

中序遍历序列为：DBACE，由于中序遍历序列的最后一个结点一定是从根结点开始沿着右子树走到最底的结点，所以中序遍历序列的最后一个结点为E，由于该结点是叶子结点，所以先序遍历序列和中序遍历序列的最后一个结点都为该结点。

先序：ABDCE
中序：DBACE

（3）二叉树的后序遍历（LRD）
二叉树的后序遍历中，首先是遍历完根结点的左子树，然后遍历完根结点的右子树，最后是根结点，依次下去至所有结点都遍历到，也就是从二叉树的底层往上层依次遍历。

该二叉树的后序遍历序列为：DBECA。
（4）先序、中序和后序遍历的相关性质
在二叉树的前序遍历、中序遍历和后序遍历序列中，所有叶子结点的先后顺序是相同的。例如，该二叉树的三种遍历分别为ABDCE、DBACE、DBECA，可以看出叶子结点D和E的先后顺序总是一样的，D结点永远都在E结点的前面。

若一棵二叉树为空树或只有根结点，则其先序遍历序列和后序遍历序列相同；若二叉树为单右支二叉树或孤立结点，则其先序遍历序列和中序遍历序列相同。例如，下面单右支二叉树，先序遍历序列和中序遍历序列相同的，都为ABC：

若一棵二叉树为空树或任一结点都缺右子树的单支树，则其中序遍历序列和后序遍历序列相同。例如，下面二叉树，其中任一结点至多只有左子树，中序遍历序列和后序遍历序列相同，都为DCBA：

若一棵非空的二叉树只有一个叶子结点，或二叉树的高度等于结点个数，则其先序遍历序列和后序遍历序列相反。例如，下面二叉树只有一个叶子结点，其结点个数为3也等于高度h=3，所以其先序遍历序列和后序遍历序列相反，即ABC和CBA：

（5）二叉树的层次遍历
层次遍历中，层次优先，当对一层的结点都遍历完后，遍历下一层，按照次序对每个结点的左、右孩子进行遍历。
例如，下面二叉树，其层次遍历为ABCDEFG：

若一棵二叉树为空树或任一结点至多只有右子树，则中序遍历序列与层次遍历序列相同。层次遍历二叉树中可以通过链式队列实现，首先二叉树的根结点入队，然后进入循环，循环条件为队列是否为空，若不为空，则当前队头结点出队，此时该结点被访问到，并将该结点的左、右孩子结点插入到队列的队尾。
10、树的存储结构
树的存储结构中反映的是一棵树中各结点之间的关系，在存储中，不仅存储树中每个结点的值，还存储各结点之间的关系，主要有三种存储结构，分别是双亲表示法、孩子链表示法和孩子兄弟表示法。
（1）双亲表示法
双亲表示法是通过采用一维数组来存储树中的结点，其中每个结点被赋予一个结构体类型，包含data域和parent域，分别存储结点的数据域和存储该结点双亲的数组下标。

#define MAXSIZE 100
typedef struct
{
	int data;		//数据域
	int parent;		//双亲位置域
}ParNode[MAXSIZE];

例如，下图该树，通过双亲表示法进行存储，规定从数组下标为0开始存储，根结点下标为0，同时设根结点的parent域为-1：

通过双亲表示法中可以很容易地找到每个结点的双亲和祖先，但是其缺点是若寻找结点的孩子结点或兄弟结点就较为麻烦，需遍历整个数组。

（2）孩子链表表示法
将所有结点存放在一个顺序表中，每个数据元素有两个域，分别是该结点的数据域和存放该结点的第一个孩子的地址，同时为树中每个结点都构建一个单链表，它也有两个域，分别是存放该孩子结点在顺序表中的数组下标和存放下一个孩子的地址。

#define MAXSIZE 100
/*顺序表定义*/
typedef struct
{
	int data;				//数据域
	ChildNode *children;	//第一个孩子的地址
}Head;

/*单链表定义*/
typedef struct Node
{
	int address;		//该孩子结点在顺序表中的数组下标
	struct Node *next;	//下一个孩子的地址
}ChildNode;
Head T[MAXSIZE];		//建立顺序表头结构

例如，通过孩子链表表示法进行存储上树，规定顺序表下标为0的位置存放根结点：

通过孩子链表表示法可以很容易地找到该结点的孩子结点，但是若要找到结点的双亲则较为麻烦，需遍历n个结点中孩子链表指针域所指向的n个孩子链表。

（3）孩子兄弟表示法
孩子兄弟表示法是采用二叉链表，其中包含三个域，分别是数据域和两个指针，即*child指向第一个孩子结点的地址、*brother指向该结点的下一个兄弟结点的地址。

typedef struct Node
{
	int data;		//数据域
	struct Node *child,*brother;	//第一个孩子结点的地址和下一个兄弟结点的地址
}ChildBNode;

例如，通过孩子兄弟表示法进行存储树：

这种方法的缺点是若从当前结点查找其双亲结点较为麻烦，解决方法是为每个结点增设一个parent域用于指向其父结点。

11、树的存储结构
（1）树转换成二叉树
①对树中所有的兄弟结点连线；【兄弟连线】
②对树中每个结点，只保留它与第一个孩子结点的连线，删除其他孩子结点之间的连线；【只留第一个孩子】
③以树的根结点为轴心，旋转一定的角度变成一棵二叉树。【旋转】
（2）二叉树还原成树
二叉树还原成树的前提是该二叉树的根结点无右子树。
①对二叉树中每个结点，若某结点的左孩子有右子树，则该结点与其左孩子的右子树的右分支上结点连线；
②删除各结点的右分支连线；
③以树的根结点为轴心，旋转一定的角度变成一棵树。
（3）森林转换成二叉树
①与树转换成二叉树的第一步一样，将该森林中每棵树转换为二叉树，即各个树中所有兄弟结点之间连线；【兄弟连线】
②将所有树的根结点相连；【根结点连线】
③每个结点只保留最左边第一个孩子结点的连线，删除其他孩子结点之间的连线；【只留最左第一个孩子】
④以树的根结点为轴心，旋转一定的角度变成一棵二叉树。【旋转】
（4）二叉树还原成森林
①对于双亲，若某结点是其双亲的左孩子，则将该结点的右孩子、右孩子的右孩子等等都与该结点的双亲结点连接；
②删除二叉树中所有双亲结点与其右孩子结点的连线；
③整理所得到的树和森林。

具体例题，可看之前的文章： 数据结构学习笔记——树的存储结构以及树、森林与二叉树之间的转换

12、树与森林的遍历
（1）树的遍历
树的遍历主要分为两种：先序遍历和后序遍历，和二叉树的遍历规则一样，例如下图该树：

该树的先序遍历序列为ABDEHMI，后序遍历序列为DBHMEIA。
另外也有层次遍历，该树的层次遍历序列为ABEIDHM。
将上图中的树转为二叉树后，如下：

我们知道该二叉树的先序遍历序列为ABDEHMI，中序遍历序列为DBHMEIA，后序遍历序列为DMHIEBA，可以得出：

• 树的先序遍历序列为转换成二叉树后的先序遍历序列，树的后序遍历序列为转换成二叉树后的中序遍历序列。

（2）森林的遍历
森林的遍历也是主要分为两种：
先序遍历和后序遍历，和二叉树的遍历规则一样，例如下图该森林：

对其进行先序遍历和后序遍历得到的序列分别为ABDEHMICFJKGL、DBHMEIAJFKCLG。
将上图中的森林转为二叉树后，如下：

对该二叉树进行先序遍历、中序遍历和后序遍历得到的遍历序列为：ABDEHMICFJKGL、DBHMEIAJFKCLG、DMHIEBJKFLGCA。
不难看出，可以得到以下结论：

• 森林的先序遍历序列为转换成二叉树后的先序遍历序列，森林的后序遍历序列为转换成二叉树后的中序遍历序列。

总结以上结论：

对应关系	树	森林	二叉树
-	先序遍历	先序遍历	先序遍历
-	后序遍历	中序遍历	中序遍历

只需记住： 树、森林、二叉树的先序遍历序列都是相同的。 森林和二叉树的中序遍历序列对应树的后序遍历。

13、线索二叉树
（1）线索二叉树的定义
由于在含有n个结点的二叉树的链式存储结构中，有n+1个空指针，对于叶子结点，它有两个空指针；对于度为1的结点（只有一个子结点），它只有一个空指针。将这些空指针利用起来，例如可以让其存放指向该结点的前驱或后继，从而使遍历二叉树更加简便，加快查找结点的前驱或后继的速度，即线索二叉树，由于线索二叉树是加上线索的链表结构，是计算机内部的一种存储结构，是一种物理结构。

• 另外，由于有n个结点，即有链域指针2n个，除了根结点以外，每个结点都被一个指针所指向，剩余的链域建立线索，即n个结点的线索二叉树含义的线索数为2n-(n-1)=n+1个。

• 线索二叉树也分为前序线索二叉树、中序线索二叉树以及后序线索二叉树，即它们都是对二叉树中的所有结点的空指针进行某种遍历方式加线索，指向结点前驱和后继的指针称为线索。

（2）画出二叉树的先/中/后序线索二叉树
简单的来说，若要画出二叉树的先/中/后序线索二叉树，只需经过以下几个步骤：
①首先求出要画的相应线索二叉树的先/中/后序遍历序列；
②画线索（针对二叉树中缺少左、右孩子的结点）：
若该结点无左孩子，则线索指向相应线索二叉树的先/中/后序遍历序列的前驱，若无前驱则指向NULL；【无左孩子，转前驱】
若该结点无右孩子，则线索指向相应线索二叉树的先/中/后序遍历序列的后继，若无后继则指向NULL。【无右孩子，转后继】
14、哈夫曼树
（1）路径和路径长度
在树中，一个结点和另一个结点之间的分支即为这两个结点之间的路径；路径长度即为树中路径上的分支数目，即路径上所经过的边的个数。树的路径长度等于根结点到树中每个结点的路径长度之和。
（2）权值
为树中每个叶子结点（度为1的结点）赋予一个数值，则该值称为叶子结点的权值，简称为权。

（3）带权路径长度
叶子结点的权值与树的根结点到该叶子结点之间的路径长度的乘积称为叶子结点的带权路径长度。

例如，上图二叉树中，叶子结点D的权值为4，根结点A到结点D的分支数目为2，所以该叶子结点的带权路径长度为4×2=8。

树中所有叶子结点的权值乘以该结点的路径长度之和即为树的带权路径长度（WPL）。

例如，上图二叉树中，该二叉树的带权路径长度为：
WPL=4×2+2×2+3×2+3×2=24。

（4）哈夫曼树

哈夫曼二叉树是哈夫曼n叉树的一种，以下都以哈夫曼二叉树为例。

哈夫曼树是一棵最优二叉树，给定n个带有权值的叶子结点，构造一棵二叉树，使构造的二叉树的带权路径长度最小，即为最优二叉树，也称为哈夫曼树。其中，两个权值最小的结点一定是兄弟结点，且任意一非叶子结点的权值不小于其下一层的任意一结点的权值。

哈夫曼树既不是满二叉树，也不是完全二叉树，只是一棵二叉树。另外，哈夫曼树中只有度为0和2的结点，不存在度为1的结点。

（5）哈夫曼树的构建步骤
基于给定的n个带权值的结点构成的初始森林，首先，选出两棵权值最小的树作为左右子树相加，得出的权值之和是一个新根结点的权值，然后，将新结点插入到森林中，同时将左右子树从森林中删除，重复选取，直到森林中只有一棵树时，即为哈夫曼树。
（6）哈夫曼编码
哈夫曼编码是一种可变长度编码，且是无前缀编码，它根据字符出现的概率来对每个字符设定二进制编码，规定一个编码不能是其它编码的前缀，主要应用在数据压缩、加密解密等场景。
15、二叉排序树
二叉排序树也称为二叉查找树或二叉搜索树，其中各结点值的大小关系是：左子树<根结点<右子树，且左、右子树也是一棵二叉排序树满足其条件，若对该树进行中序遍历，可得到一个递增的序列。

十、图

图的知识点由于过多，……这边不放上了，可以去我的系列文章中查看：
数据结构