第1章 数据结构与算法[视频讲解]
视频二维码（扫码观看）
1算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。
2数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。
3线性表的定义；线性表的顺序存储结构及其插入与删除运算。
4栈和队列的定义；栈和队列的顺序存储结构及其基本运算。
5线性单链表、双向链表与循环链表的结构及其基本运算。
6树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。
7顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。
1.1 算 法
视频二维码（扫码观看）
一、算法的基本概念
1算法的定义
算法是指解题方案的准确而完整的描述，即算法是对特定问题求解步骤的一种描述。
【注意】算法不等于程序，也不等于计算方法。
2算法的基本特征
（1）可行性（Effectiveness）：算法中的每一个步骤必须能够实现，执行的结果要能够达到预期的目的。
（2）确定性（Definiteness）：算法中的每一个步骤都必须是有明确定义的，不允许有模棱两可的解释或多义性。
（3）有穷性（Finiteness）：算法必须能在有限的时间（合理的时间）内做完，即算法必须能在执行有限个步骤之后终止。
（4）拥有足够的情报：输入是否足够并正确，输出是否合理。初始状态是否正确。
二、算法设计基本方法
1列举法
（1）基本思想
根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。
（2）特点
简单，方便用计算机进行大量列举；情况较多时，工作量将会很大。
（3）使用
将与问题有关的知识条理化、完备化、系统化，从中找出规律，进行分类，减少列举量。
【例1】今有鸡母一，值钱三；鸡翁一，值钱二；鸡雏一，值钱半。凡百钱买百鸡，问鸡母、鸡翁、鸡雏各几何？
假设买母鸡I只、公鸡J只、小鸡K只。根据题意，粗略的列举算法描述如下：
共有三层循环，每层循环各需要循环101次，大约为100万次。
优化后的算法
共有两层循环，循环次数为
2归纳法
（1）基本思想
通过列举少量的特殊情况，经过分析最后找出一般的关系。
（2）特点
归纳是一种抽象，即从特殊现象中找出一般关系。
（3）使用
由于在归纳的过程中不可能对所有的情况进行列举。因此，最后由归纳得到的结论还只是一种猜测，还需要对这种猜测加以必要的证明。实际上，通过精心观察而得到的猜测得不到证实或最后证明猜测是错的，也是常有的事。
3递推
（1）基本思想
从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。
（2）特点
本质上属于归纳法，递推关系式往往是归纳的结果。
（3）使用
递推算法在数值计算中是极为常见的。但是，对于数值型的递推算法必须要注意数值计算的稳定性问题。
4递归
（1）基本思想
为了降低问题的复杂程度，将问题逐层分解，最后归结为一些最简单的问题，这种将问题逐层分解的过程，实际上并没有对问题进行求解，而只是当解决了最后那些最简单的问题后，再沿着原来分解的逆过程逐步进行综合。
（2）特点
结构清晰，可读性强。
（3）使用
递归在可计算性理论和算法设计中占有很重要的地位。
（4）分类
直接递归（自己调用自己）和间接递归（P调用Q，Q又调用P）。
【例2】编写一个过程，对于输入的参数n，依次打印输出自然数1到n。
非递归算法：
递归算法：
5减半递推技术
所谓“减半”，是指将问题的规模减半，而问题的性质不变；所谓“递推”，是指重复“减半”的过程。
【例3】设方程f（x）＝0在区间[a，b]上有实根，且f（a）与f（b）异号。利用二分法求该方程在区间[a，b]上的一个实根。
用二分法求方程实根的减半递推过程如下：
（1）首先取给定区间的中点c＝（a＋b）/2。
（2）然后判断f（c）是否为0：
如果f（c）＝0，则说明c即为所求的根，求解过程结束；
如果f（c）≠0，则根据以下原则将原区间减半：
①若f（a）f（c）＜0，则取原区间的前半部分；
②若f（b）f（c）＜0，则取原区间的后半部分。
（3）最后判断减半后的区间长度是否已经很小：
①若|a－b|＜ε，则过程结束，取（a＋b）/2为根的近似值；
②若|a－b|≥ε，则重复上述的减半过程。
6回溯法
（1）基本思想
通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，对于每一步的试探，若试探成功，就得到问题的解，若试探失败，就逐步回退，换别的路线再进行试探。这种方法称为回溯法。
（2）特点
在工程上，有些实际问题很难归纳出一组简单的递推公式或直观的求解步骤，并且也不能进行无限的列举。对于这类问题，一种有效的方法是“试”。
三、算法复杂度
主要包括时间复杂度和空间复杂度。
1算法的时间复杂度
（1）定义
执行算法所需要的计算工作量。
（2）衡量标准
通常用算法在执行过程中所需基本运算的执行次数来度量算法的工作量。算法所执行的基本运算次数还与问题的规模有关。
综上所述，算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即算法的工作量＝f（n）。
（3）存在问题
算法所执行的基本运算次数还可能与特定的输入有关，而实际上又不可能将所有可能情况下算法所执行的基本运算次数都列举出来。
（4）解决方法
①平均性态（Average Behavior）
用各种特定输入下的基本运算次数的加权平均值来度量算法的工作量：
②最坏情况复杂性（Worst-Case Complexity）
规模为n时，算法所执行的基本运算的最大次数：
2算法的空间复杂度
【定义】执行这个算法所需要的内存空间。
（1）算法程序所占的空间；
（2）输入的初始数据所占的存储空间；
（3）算法执行过程中所需要的额外空间。
【注意】
①如果额外空间量相对于问题规模来说是常数，则称该算法是原地工作的。
②在许多实际问题中，为了减少算法所占的存储空间，通常采用压缩存储技术，以便尽量减少不必要的额外空间。
【考题1】算法的时间复杂度是指（ ）。
A．执行算法程序所需要的时间
B．算法程序的长度
C．算法执行过程中所需要的基本运算次数
D．算法执行过程中所需要的所有运算次数
E．算法程序中的指令条数
【答案】C
【解析】算法的时间复杂度是指算法执行过程中所需要的基本运算次数。执行算法程序所需要的时间、算法长度、指令条数等与时间复杂度没有直接关系。
【考题2】算法的空间复杂度是指（ ）。
A．算法程序的长度
B．算法程序中的指令条数
C．算法程序所占的存储空间
D．算法执行过程中所需要的存储空间
E．算法所处理的数据量
【答案】D
【解析】算法的空间复杂度是指算法执行过程中所需要的存储空间。算法程序的长度、指令条数、所处理的数据量等与空间复杂度没有直接关系。
1.2 数据结构的基本概念
视频二维码（扫码观看）
数据结构作为计算机的一门学科，主要研究和讨论以下三个方面的问题：
（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；
（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；
（3）对各种数据结构进行的运算。
讨论以上问题的目的：
（1）提高数据处理的速度；
（2）尽量节省在数据处理过程中所占用的计算机存储空间。
一、什么是数据结构
【定义】数据结构是指相互有关联的数据元素的集合。
数据元素具有广泛的含义：
描述一年四季的季节名：春、夏、秋、冬
表示数值的各个数：18、11、35、23、16…
表示家庭成员的各成员名：父亲、儿子、女儿
数据处理：对数据集合中的各元素以各种方式进行运算，包括插入、删除、查找、更改等运算，也包括对数据元素进行分析。
【注意】作为某种处理，其中的数据元素一般具有某种共同特征，一般情况下，在具有相同特征的数据元素集合中，各个数据元素之间存在有某种关系，这种关系反映了该集合中的数据元素所固有的一种结构。
1数据的逻辑结构
（1）定义
反映数据元素之间逻辑关系的数据结构。一个数据结构应包含以下两方面的信息：
①表示数据元素的信息；
②表示各数据元素之间的前后件关系。
（2）数据的逻辑结构有两个要素：
一是数据元素的集合，通常记为D；
二是D上的关系，它反映了D中各数据元素之间的前后件关系，通常记为R；
即一个数据结构可以表示成B＝（D，R）。
【例4】一年四季的数据结构可以表示成
B＝（D，R）
D＝{春，夏，秋，冬}
R＝{（春，夏），（夏，秋），（秋，冬）}
2数据的存储结构
定义：数据的逻辑结构在计算机存储空间中的存放形式。
【注意】
①各数据元素在计算机存储空间中的位置关系与它们的逻辑关系不一定是相同的，而且一般也不可能相同。
②在数据的存储结构中，不仅要存放各数据元素的信息，还需要存放各数据元素之间的前后件关系的信息。
③常用的存储结构有顺序、链接、索引等存储结构。
④采用不同的存储结构，其数据处理的效率是不同的。
二、数据结构的图形表示
一个数据结构除了用二元关系表示外，还可以直观地用图形表示。
（1）对于数据集合D中的每一个数据元素用中间标有元素值的方框表示，一般称之为数据结点，并简称为结点；
（2）对于关系R中的每一个二元组，用一条有向线段从前件结点指向后件结点，有时箭头可省去。
图1-1 一年四季数据结构的图形表示图（线性）
图1-2 家庭成员间关系数据结构的图形表示（树型结构）
【考题】下列叙述中正确的是（ ）。
A．线性表是线性结构
B．栈与队列是非线性结构
C．循环链表是非线性结构
D．二叉树是线性结构
【答案】A
【解析】选项A正确；选项B，栈和队列都是线性结构，二者区别是，栈只允许在一端插入和删除，队列只允许在一端插入，在另一端删除；选项C，循环链表是线性表的链式存储结构；选项D，二叉树是一种典型的非线性结构。
三、线性结构与非线性结构
根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。
如果一个非空的数据结构满足下列两个条件：
（1）有且只有一个根结点；
（2）每一个结点最多有一个前件，也最多有一个后件。
则称该数据结构为线性结构，线性结构又称线性表。
【注意】在一个线性结构中插入或删除任何一个结点后还应是线性结构。如果一个数据结构不是线性结构，则称之为非线性结构。
【考题】设数据集合为D＝{1，3，5，7，9}，D上的关系为R。下列数据结构B＝（D，R）中为非线性结构的是（ ）。
A．R＝{（5，1），（7，9），（1，7），（9，3）}
B．R＝{（9，7），（1，3），（7，1），（3，5）}
C．R＝{（1，9），（9，7），（7，5），（5，3）}
D．R＝{（1，3），（3，5），（5，9）}
【答案】D
【解析】如果一个非空的数据结构满足下列两个条件：①有且只有一个根结点；②每一个结点最多有一个前件，也最多有一个后件。则该数据结构为线性结构。
选项A：5是根结点，5的后件是1，1的后件是7，7的后件是9，9的后件是3，故选项A是线性结构；
选项B：9是根结点，9的后件是7，7的后件是1，1的后件是3，3的后件是5，故选项B是线性结构；
选项C：1是根结点，1的后件是9，9的后件是7，7的后件是5，5的后件是3，故选项C是线性结构；
选项D：1是根结点，1的后件是3，3的后件是5，5的后件是9，7也是根结点，没有前件也没有后件，线性数据结构第一个条件不满足，故选项D是非线性结构，即选项D正确。
1.3 线性表及其顺序存储结构
视频二维码（扫码观看）
一、线性表的基本概念
线性表（Linear List）是最简单、最常用的一种数据结构。如：一个n维向量、矩阵，学生情况登记表。
线性表是由n（n≥0）各数据元素a1，a2，…，an组成的一个有限序列，表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。即线性表或是一个空表，或可以表示为（a1，a2，…，ai，…，an），其中ai（i＝1，2，…，n）是属于数据对象的元素，通常也称其为线性表中的一个结点。
非空线性表有如下一些结构特征：
（1）有且只有一个根结点a1它无前件；
（2）有且只有一个终端结点an，它无后件；
（3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。
【说明】
①线性表中结点的个数n称为线性表的长度。
②当n＝0时，称为空表。
二、线性表的顺序存储结构
1特点
（1）线性表中所有元素所占的存储空间是连续的；
（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
在线性表的顺序存储结构中，其前后件两个元素在存储空间中是紧邻的，且前件元素一定存储在后件元素的前面。
图1-3 线性表的顺序存储结构
【注意】
①在程序设计语言中，通常定义一个一维数组来表示线性表的顺序存储空间。
②在用一维数组存放线性表时，该一维数组的长度通常要定义得比线性表的实际长度大一些，以便对线性表进行各种运算，特别是插入运算。
2线性表的相关操作
（1）插入：在线性表的指定位置处加入一个新的元素。
（2）删除：在线性表中删除指定的元素。
（3）查找：在线性表中查找某个（或某些）特定的元素。
（4）排序：对线性表中的元素进行整序（即线性表的）。
（5）分解：按要求将一个线性表分解成多个线性表。
（6）合并：按要求将多个线性表合并成一个线性表。
（7）复制：复制一个线性表。
（8）逆转：逆转一个线性表。
三、顺序表的插入运算
【例5】长度为8的线性表顺序存储在长度为10的存储空间中。在第2个元素之前插入一个新元素87。然后在线性表的第9个元素之前插入一个新元素14。
图1-4 线性表在顺序存储结构下的插入
线性表的存储空间从1到m，线性表的长度为n（n≤m），插入的位置为i（i表示在第i个元素之前插入）。线性表的插入操作如下：
第一步首先处理以下三种异常情况：
①当存储空间已满（即n＝m）时为“上溢”错误，不能进行插入，算法结束；
②当i＞n时，认为在最后一个元素之后插入；
③当i＜1时，认为在第1个元素之前插入。
第二步从最后一个元素开始，直到第i个元素，每一个元素往后移动一个位置。
第三步将新元素插入到第i个位置，线性表的长度加1。
四、顺序表的删除运算
【例6】长度为8的线性表顺序存储在长度为10的存储空间中。现在要求删除线性表中的第1个元素。再删除线性表中的第6个元素。
图1-5 线性表在顺序存储结构下的删除
线性表的存储空间从1到m，线性表的长度为n（n≤m），删除的位置为i（表示删除第i个元素）。线性表的删除操作如下：
第一步首先处理以下两种异常情况：
①当线性表为空（即n＝0）时错误，不能进行删除，算法结束；
②当i＜1或i＞n时，错误，不能进行删除，算法结束。
第二步删除线性表中的第i个元素。
第三步从第i＋1个元素开始，直到最后一个元素，其中每一个元素均依次往前移动一个位置。线性表的长度减小1。
1.4 栈和队列
视频二维码（扫码观看）
一、栈及其基本运算
1什么是栈
【定义】限定在一端进行插入与删除的线性表
【说明】
①允许插入与删除的一端称为栈顶（指针top），而不允许插入与删除的另一端称为栈底（指针bottom）。
②栈是按照“先进后出”（FILO）的原则组织数据。
③栈具有记忆作用。
④往栈中插入一个元素称为入栈运算，从栈中删除一个元素（即删除栈顶元素）称为出栈运算。
图1-6 栈示意图
2栈的顺序存储及其运算
图1-7（a）是容量为10的栈顺序存储空间，栈中已有6个元素；图1-7（b）与图1-7（c）分别为入栈与退栈后的状态。
图1-7 栈在顺序存储结构下的运算
（1）入栈运算
入栈运算是指在栈顶位置插入一个新元素。操作过程如下：
①首先判断栈顶指针是否已经指向存储空间的最后一个位置。如果是，则说明栈空间已满，不可能再进行入栈操作（这种情况称为栈“上溢”错误），算法结束。
②然后将栈顶指针进一（即top加1）。
③最后将新元素x插入栈顶指针指向的位置。
（2）退栈运算
退栈运算是指取出栈顶元素并赋给一个指定的变量。操作过程如下：
①首先判断栈顶指针是否为0。如果是，则说明栈空，不可能进行退栈操作（这种情况称为栈“下溢”错误），算法结束。
②然后将栈顶元素（栈顶指针指向的元素）赋给一个指定的变量。
③最后将栈顶指针退一（即top减1）。
（3）读栈顶元素
读栈顶元素是指将栈顶元素赋给一个指定的变量。操作过程如下：
①首先判断栈顶指针是否为0。如果是，则说明栈空，读不到栈顶元素，算法结束。
②然后将栈顶元素赋给指定的变量y。
【注意】这个运算不删除栈顶元素，只是将它的值赋给一个变量，因此，在这个运算中栈顶指针不会改变。
【考题】下列关于栈的叙述中正确的是（ ）。
A．在栈中只能插入数据
B．在栈中只能删除数据
C．栈是先进先出的线性表
D．栈是先进后出的线性表
E．栈是一种非线性结构
【答案】D
【解析】在栈中，只允许在栈顶一端进行插入和删除，所以A、B错误；队列是“先进先出”的线性表，栈是“先进后出”的线性表，所以C、E错误，D正确。
二、队列及其基本运算
1什么是队列
加入的元素总是插入到线性表的末尾，并且又总是从线性表的头部取出（删除）元素。这种线性表称为队列。
【说明】
①允许插入的一端称为队尾（rear），允许删除的一端称为队头（front）。
②在队列中按照“先进先出”的原则进行操作。
图1-8 具有6个元素的队列示意图
图1-9 队列运算示意图
【考题】下列关于队列的叙述中正确的是（ ）。
A．在队列中只能插入数据
B．在队列中只能删除数据
C．队列是先进先出的线性表
D．队列是先进后出的线性表
【答案】C
【解析】在队列中，只允许在一端进行插入，在另一端进行删除，所以A、B错误；队列是“先进先出”的线性表，栈是“先进后出”的线性表，所以D错误，选择C。
2循环队列及其运算
【定义】循环队列是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。
图1-10 循环队列存储空间示意图
用队尾指针rear指向队列中的队尾元素，用排头指针front指向排头元素的前一个位置。
在实际使用循环队列时，为了能区分队列满还是队列空，通常还需增加一个标志s，s值的定义如下：
由此可以得出队列空与队列满的条件如下：
队列空的条件为s＝0；
队列满的条件为s＝1且front＝rear。
图1-11 循环队列运算示意图
（1）入队运算
入队运算是指在循环队列的队尾加入一个新元素。操作过程如下：
①首先判断循环队列是否满。当循环队列非空（S＝1）且队尾指针等于排头指针时，说明循环队列已满，不能进行入队运算。这种情况称为“上溢”。此时算法结束。
②然后将队尾指针进一（即rear＝rear＋1），并当rear＝m＋1时置rear＝1。
③最后将新元素x插入队尾指针指向的位置，并且置循环队列非空标志。
（2）退队运算
退队运算是指在循环队列的排头位置退出一个元素并赋给指定的变量。操作过程如下：
①首先判断循环队列是否为空。当循环队列为空（s＝0）时，不能进行退队运算。这种情况称为“下溢”。此时算法结束。
②然后将排头指针进一（即front＝front＋1），并当front＝m＋1时置front＝1。
③再将排头指针指向的元素赋给指定的变量。
④最后判断退队后循环队列是否为空。当front＝rear时置循环队列空标志（即s＝0）。
【考题】设循环队列为Q（1：m），其初始状态为front＝rear＝m。经过一系列入队与退队运算后，front＝30，rear＝10。现要在该循环队列中作顺序查找，最坏情况下需要比较的次数为（ ）。
A．19
B．20
C．m－19
D．m－20
【答案】D
【解析】在该循环队列中作顺序查找，最坏情况下需要比较的次数，实际上就是求循环队列中元素的个数。元素的个数＝（rear－front＋m） mod m＝（10－30＋m） mod m＝m－20，选项D正确。
1.5 线性链表
视频二维码（扫码观看）
一、线性链表的基本概念
【定义】线性表的链式存储结构称为线性链表。线性链表的数据结构包括两部分，一是数据元素的值，二是数据元素之间的前后件关系。
图1-12 线性链表的一个存储结点
为什么用线性链表？
（1）线性表顺序存储结构存在的缺点：
①插入或删除过程中需要移动大量的数据元素。
②出现线性表的存储空间已满，但还需要插入新的元素时，就会发生“上溢”错误。
③线性表的顺序存储结构不便于存储空间的动态分配。
（2）线性表链式存储结构存在的优点：
在链式存储结构中，存储数据结构的存储空间可以不连续，各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致，而数据元素之间的逻辑关系是由指针域来确定的。
【说明】
①在线性链表中，用一个专门的指针HEAD指向线性链表中第一个数据元素的结点（即存放线性表中第一个数据元素的存储结点的序号）。线性表中最后一个元素没有后件，因此，线性链表中最后一个结点的指针域为空（用NULL或0表示），表示链表终止。
图1-13 线性链表的逻辑结构
②在线性表的链式存储结构中，各数据结点的存储序号是不连续的，并且各结点在存储空间中的位置关系与逻辑关系也不一致。
③当HEAD＝NULL（或0）时称为空表。
图1-14 线性链表例
1双向链表
对线性链表中的每个结点设置两个指针，一个称为左指针（Llink），用以指向其前件结点；另一个称为右指针（Rlink），用以指向其后件结点。
图1-15 双向链表示意图
2带链的栈
栈也是线性表，也可以采用链式存储结构。
图1-16 带链的栈
在实际应用中，带链的栈可以用来收集计算机存储空间中所有空闲的存储结点，这种带链的栈称为可利用栈。
图1-17 可利用栈及其运算
3带链的队列
队列也是线性表，也可以采用链式存储结构。
图1-18 带链的队列及其运算
二、线性链表的基本运算
线性链表的运算主要有以下几个：
①插入：在线性链表中包含指定元素的结点之前插入一个新元素。
②删除：在线性链表中删除包含指定元素的结点。
③合并：将两个线性链表按要求合并成一个线性链表。
④分解：将一个线性链表按要求进行分解。
⑤逆转
⑥复制
⑦排序
⑧查找
1在线性链表中查找指定元素
从头指针指向的结点开始往后沿指针进行扫描，直到后面已没有结点或下一个结点的数据域为x为止。
因此，由这种方法找到的结点p有两种可能：
①当线性链表中存在包含元素x的结点时，则找到的p为第一次遇到的包含元素x的前一个结点序号；
②当线性链表中不存在包含元素x的结点时，则找到的p为线性链表中的最后一个结点号。
2线性链表的插入
图1-19 线性链表的插入
3线性链表的删除
图1-20 线性链表的删除
三、循环链表
线性链表中，其插入与删除的运算虽然比较方便，但还存在一个问题，在运算过程中对于空表和对第一个结点的处理必须单独考虑，使空表与非空表的运算不统一。
1循环链表的特点
（1）增加了表头结点，其数据域为任意或者根据需要来设置，指针域指向线性表的第一个元素的结点。循环链表的头指针指向表头结点。
（2）循环链表中最后一个结点的指针域不是空，而是指向表头结点。即在循环链表中，所有结点的指针构成了一个环状链。
图1-21 循环链表的逻辑状态
2循环链表与线性单链表相比主要有以下两个方面的优点：
（1）在循环链表中，只要指出表中任何一个结点的位置，就可以从它出发访问到表中其他所有的结点。线性单链表做不到这一点。
（2）由于在循环链表中设置了一个表头结点，因此，在任何情况下循环链表中至少有一个结点存在，从而使空表与非空表的运算统一。
1.6 树与二叉树
视频二维码（扫码观看）
一、树的基本概念
【定义】树（Tree）是一种简单的非线性结构，树中所有数据元素之间的关系具有明显的层次特性。
图1-22 学校行政层次结构树
【说明】
①在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点，简称为树的根。
②在树结构中，每一个结点可以有多个后件，它们都称为该结点的子结点。没有后件的结点称为叶子结点。
③在树结构中，一个结点所拥有的后件个数称为该结点的度。
④在树中，所有结点中的最大的度称为树的度。
⑤树中的结点数＝树中所有结点的度之和＋1。
⑥根结点在第1层。同一层上所有结点的所有子结点都在下一层。树的最大层次称为树的深度。
树在计算机中的存储方式：
树在计算机中通常用多重链表表示。多重链表中的每个结点描述了树中对应结点的信息，而每个结点中的链域（指针域）个数将随树中该结点的度而定。
图1-23 树链表中的结点结构
二、二叉树及其基本性质
1什么是二叉树
二叉树具有以下两个特点：
①非空二叉树只有一个根结点；
②每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树。
【注意】在二叉树中，每一个结点的度最大为2。
图1-24 二叉树例
2二叉树的基本性质
【性质1】在二叉树的第k层上，最多有2k－1（k≥1）个结点。
【性质2】深度为m的二叉树最多有2m－1个结点，即21－1＋22－1＋…＋2m－1＝2m－1。
【性质3】在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。
【性质4】具有n个结点的二叉树，其深度至少为[log2n]＋1，其中[log2n]表示取log2n的整数部分。
【考题1】在深度为5的满二叉树中，叶子结点的个数为（ ）。
A．32
B．31
C．16
D．15
【答案】C
【解析】叶子结点的个数＝2（5－1）＝16。
【考题2】设树T的度为4，其中度为1，2，3，4的结点个数分别为4，2，1，1。则树T中的叶子结点数为（ ）。
A．8
B．7
C．6
D．5
【答案】A
【解析】结点数为所有结点的度数之和加1，同时，注意到叶子结点的度数为0，则总结点数（设叶子结点数为X）1*4＋2*2＋3*1＋4*1＋X*0＋1＝16，叶子结点数为X＝16－4－2－1－1＝8。
3满二叉树与完全二叉树
（1）满二叉树
【定义】满二叉树是指这样的一种二叉树：除最后一层外，每一层上的所有结点都有两个子结点。
【说明】在满二叉树中，每一层上的结点数都达到最大值，即在满二叉树的第k层上有2k－1个结点，且深度为m的满二叉树有2m－1个结点。
图1-25 满二叉树
（2）完全二叉树
【定义】所谓完全二叉树是指这样的二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。
除第一层外，每层上的结点都有两个子结点。
【说明】满二叉树也是完全二叉树，而完全二叉树一般不是满二叉树。
图1-26 完全二叉树
完全二叉树还具有以下两个性质：
【性质5】具有n个结点的完全二叉树的深度为[log2n]＋1。
【性质6】设完全二叉树共有n个结点。如果从根结点开始，按层序（每一层从左到右）用自然数1，2，…，n给结点进行编号，则对于编号为k（k＝1，2，…，n）的结点有以下结论：
①若k＝1，则该结点为根结点，它没有父结点；若k＞1，则该结点的父结点编号为INT（k/2）。
②若2k≤n，则编号为k的结点的左子结点编号为2k；否则该结点无左子结点（显然也没有右子结点）。
③若2k＋1≤n，则编号为k的结点的右子结点编号为2k＋1；否则该结点无右子结点。
【考题】设一棵完全二叉树共有700个结点，则该完全二叉树中的叶子结点数为（ ）。
A．351
B．350
C．349
D．348
【答案】B
【解析】完全二叉树所有结点的度数最大为2。设度为0的结点数为n0，度为1的结点数为n1，度为2的结点数为n2，即有：n0＋n1＋n2＝700①；根据二叉树性质3：在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个，知：n2＝n0－1②；根据完全二叉树的特点：n1＝0或1③。联立①②③，易知：n0＝350，所以选项B正确。
视频二维码（扫码观看）
三、二叉树的存储结构
在计算机中，二叉树通常采用链式存储结构。
用于存储二叉树中各元素的存储结点也由两部分组成：数据域与指针域。
图1-27 二叉树存储结点的结构
图1-28 二叉树的链式存储结构
四、二叉树的遍历
【定义】二叉树的遍历是指不重复地访问二叉树中的所有结点。
在遍历二叉树的过程中，一般先遍历左子树，然后再遍历右子树。在先左后右的原则下，根据访问根结点的次序，二叉树的遍历可以分为三种：前序遍历、中序遍历、后序遍历。
1前序遍历（DLR）
若二叉树为空，则结束返回。否则：
①访问根结点；
②前序遍历左子树；
③前序遍历右子树。
2中序遍历（LDR）
若二叉树为空，则结束返回。否则：
①中序遍历左子树；
②访问根结点；
③中序遍历右子树。
3后序遍历（LRD）
若二叉树为空，则结束返回。否则：
①后序遍历左子树；
②后序遍历右子树；
③访问根结点。
【例7】已知二叉树如图1-29所示。
图1-29 二叉树
根据二叉树遍历规则有：
前序序列：A B D E G C F
中序序列：D B G E A C F
后序序列：D G E B F C A
【说明】
①如果知道了某二叉树的前序序列和中序序列，则可以唯一地恢复该二叉树。
②如果知道了某二叉树的后序序列和中序序列，则也可以唯一地恢复该二叉树。
③如果只知道某二叉树的前序序列和后序序列，是不能唯一恢复该二叉树的。
【例8】某二叉树的前序序列为DBACFEG，中序序列为ABCDEFG，则二叉树的回复过程如下：
图1-30 二叉树的恢复过程
【考题1】设有下列二叉树：
对此二叉树进行中序遍历的结果为（ ）。
A．ABCDEF
B．DBEAFC
C．ABDECF
D．DEBFCA
【答案】B
【解析】中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。故选项B正确。
【考题2】设一棵二叉树的中序序列为DBEAFC，前序序列为ABDECF，则后序序列为（ ）。
A．ABCDEF
B．FEDCBA
C．DEBFCA
【答案】C
【解析】前序遍历首先遍历根结点，知A是根结点，后续序列最后访问根结点，故排除A；根据中序遍历首先遍历左子树及左子树其他全部结点，然后访问根结点，知D、B、E三个结点肯定在该二叉树根结点A的左子树上，F、C两个结点在根结点A的右子树上，又后序序列也是首先访问左子树及左子树其他全部结点，然后访问右子树及右子树其他全部结点，故后序序列的访问顺序中，对结点D、B、E三个结点的访问肯定先于F、C两个结点，故排除B，得到正确选项C。
【注意】熟练掌握三种遍历方式的区别和联系，在选择题中完全可以按照解析中的快速排除法锁定选项，节约做题时间。
【考题3】下列叙述中正确的是（ ）。
A．线性表是线性结构
B．栈与队列是非线性结构
C．循环链表是非线性结构
D．二叉树是线性结构
【答案】A
【解析】选项A正确；选项B，栈和队列都是线性结构，二者区别是，栈只允许在一端插入和删除，队列只允许在一端插入，在另一端删除；选项C，循环链表是线性表的链式存储结构；选项D，二叉树是一种典型的非线性结构。
1.7 查找技术
视频二维码（扫码观看）
【定义】查找是指在一个给定的数据结构中查找某个指定的元素。常见的查找方式有：顺序查找、二分法查找等。
一、顺序查找
基本方法如下：
（1）从线性表的第一个元素开始，依次将线性表中的元素与被查元素进行比较，若相等则表示找到（即查找成功）；
（2）若线性表中所有的元素都与被查元素进行了比较但都不相等，则表示线性表中没有要找的元素（即查找失败）。
顺序查找的优点：
算法简单，对线性表的结构无任何要求，无论是用数组还是用链表来存放结点，也无论结点之间是否按关键字有序，它都同样适用。
顺序查找的缺点：查找效率低。
【注意】下列两种情况只能用顺序查找法：
一是无序线性表；
二是链式存储结构。
【考题1】对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为（ ）。
A．n＋1
B．n
C．（n＋1）/2
D．n/2
【答案】B
【解析】顺序查找，最坏的情况有两种，一是所找元素不在线性表中，而是所找元素在线性表最后一个位置，两种最坏情况，都是需要从第一个元素开始，一直到最后一个元素进行比较，故比较次数为n，所以选项B正确。
【考题2】在长度为n的线性表中寻找最大项，在最坏情况下所需要的比较次数为（ ）。
A．n＋1
B．n－1
C．n
D．n/2
【答案】B
【解析】寻找最大项，只需要在线性表中任选一个元素，跟其他元素进行比较，最坏比较次数自然是n－1，所以选项B正确。
二、二分法查找（又称对分查找、折半查找法）
二分法查找只适用于顺序存储的有序表，即表中结点按关键字排序。
设有序线性表的长度为n，被查元素为x，则二分查找的方法如下：
（1）将x与线性表的中间项进行比较：若中间项的值等于x，则说明查到，查找结束。
（2）若x小于中间项的值，则在线性表的前半部分（即中间项以前的部分）以相同的方法进行查找。
（3）若x大于中间项的值，则在线性表的后半部分（即中间项以后的部分）以相同的方法进行查找。
（4）这个过程一直进行到查找成功或子表长度为0（说明线性表中没有这个元素）为止。
【注意】
①二分查找的效率要比顺序查找高得多。
②对于长度为n的有序线性表，在最坏情况下，二分查找只需要比较O（log2n）次，而顺序查找需要比较n次。
【考题】在长度为n的有序线性表中进行二分查找，在最坏情况下所需要的比较次数为（ ）。
A．n－1
B．n/2
C．（n－1）/2
D．O（log2n）
【答案】D
1.8 排序技术
视频二维码（扫码观看）
【定义】将一个无序序列整理成按值非递减顺序排列的有序序列。
在本节所介绍的排序方法中，其排序的对象一般认为是顺序存储的线性表，在程序设计语言中就是一维数组。
常见的排序方法：
交换类排序：冒泡排序、快速排序
插入类排序：直接插入排序、折半插入排序、希尔排序
选择类排序：简单选择排序、堆排序
一、交换类排序法
【定义】借助数据元素之间的互相交换进行排序的一种方法。
【注意】冒泡排序法与快速排序法都属于交换类的排序方法。
1冒泡排序法
（1）定义
冒泡排序法是一种最简单的交换类排序方法，它是通过相邻数据元素的交换逐步将线性表变成有序。
（2）排序过程
①首先，从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，前面的元素大于后面的元素，则将它们互换，称之为消去了一个逆序。
②然后，从后到前扫描剩下的线性表，同样，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，后面的元素小于前面的元素，则将它们互换，这样就又消去了一个逆序。
③对剩下的线性表重复上述过程，直到剩下的线性表变空为止，此时的线性表已经变为有序。
图1-31 冒泡排序过程示意图
2快速排序法
（1）定义
快速排序法也是一种互换类的排序方法，但由于它比冒泡排序法的速度快，因此称之为快速排序法。
（2）基本思想
从线性表中选取一个元素，设为T，将线性表后面小于T的元素移到前面，而前面大于T的元素移到后面，结果就将线性表分成了两部分（称为两个子表），T插入到其分界线的位置处，这个过程称为线性表的分割。
通过对线性表的一次分割，就以T为分界线，将线性表分成了前后两个子表，且前面子表中的所有元素均不大于T，而后面子表中的所有元素均不小于T。
图1-32 快速排序示意图
（3）排序过程
①首先，在表的第一个、中间一个与最后一个元素中选取中项，设为P（k），并将P（k）赋给T，再将表中的第一个元素移到P（k）的位置上。
②然后设置两个指针i和j分别指向表的起始与最后的位置。反复操作以下两步：
a．将j逐渐减小，并逐次比较P（j）与T，直到发现一个P（j）＜T为止，将P（j）移到P（i）的位置上。
b．将i逐渐增大，并逐次比较P（i）与T，直到发现一个P（i）＞T为止，将P（i）移到P（j）的位置上。
③上述两个操作交替进行，直到指针i与j指向同一个位置（即i＝j）为止，此时将T移到P（i）的位置上。
二、插入类排序法
1简单插入排序法
（1）定义
将无序序列中的各元素依次插入到已经有序的线性表中。
（2）插入过程
首先将第j个元素放到一个变量T中，然后从有序子表的最后一个元素（即线性表中第j－1个元素）开始，往前逐个与T进行比较，将大于T的元素均依次向后移动一个位置，直到发现一个元素不大于T为止，此时就将T（即原线性表中的第j个元素）插入到刚移出的空位置上，有序子表的长度就变为j了。
图1-33 简单插入排序示意图
2希尔排序法
（1）定义
希尔排序法（Shell Sort）属于插入类排序，但它对简单插入排序做了较大的改进。
（2）排序过程
将整个无序序列分割成若干小的子序列分别进行插入排序。子序列的分割方法如下：
①将相隔某个增量h的元素构成一个子序列。在排序过程中，逐次减小这个增量，最后当h减到1时，进行一次插入排序，排序就完成。
②增量序列一般取ht＝n/2k（k＝1，2，…，[log2n]），其中n为待排序序列的长度。
三、选择类排序法
1简单选择排序法
排序过程
①扫描整个线性表，从中选出最小的元素，将它交换到表的最前面（这是它应有的位置）；
②然后对剩下的子表采用同样的方法，直到子表空为止。
图1-34 简单选择排序法示意图
2堆排序法
（1）堆的定义
具有n个元素的序列（h1，h2，…，hn），当且仅当满足
称之为堆。本节只讨论满足前者条件的堆。
【说明】若上述数列是堆，则k1必是数列中的最小值或最大值，分别称作小顶堆或大顶堆。
（2）堆的表示
在实际处理中，可以用一维数组H（1：n）来存储堆序列中的元素，也可以用完全二叉树来直观地表示堆的结构。
图1-35 堆顶元素为最大的堆
（3）建立堆
从无序序列的第⌊n/2⌋个元素起，至第一个元素止，进行反复筛选。
【例9】无序序列（49，38，65，97，76，13，27，50）建立小顶堆。n＝8，⌊n/2⌋＝4。
图1-36 调整建堆示意图
（4）堆排序的方法
①首先将一个无序序列建成堆。
②将堆顶元素（序列中的最大项）输出，将堆中最后一个元素放到堆顶。显然，该子序列已不是堆，但左、右子树仍为堆，可以将该子序列调整为堆。反复做第②步，直到剩下的子序列为空为止。
【例10】对无序序列（49，38，65，97，76，13，27，50）进行堆排序。
第一步：建堆
第二步：堆排序
各种排序方法时间性能比较
时间复杂度为O（nlogn）的方法有：快速排序、堆排序，其中以快速排序为最好；
时间复杂度为O（n2）的有：直接插入排序、冒泡排序和简单选择排序，其中以直接插入为最好，特别是对那些对关键字近似有序的记录序列尤为如此。
【考题】下列排序法中，在最坏情况下时间复杂度最小的是（ ）。
A．快速排序
B．希尔排序
C．堆排序
【答案】C
【解析】选项A，快速排序的最坏情况下时间复杂度是n（n－1）/2，即O（n2）；选项B，希尔排序最坏情况下时间复杂度是O（n1.5）；选项C，堆排序最坏情况下时间复杂度是O（nlog2n）。显然，O（nlog2n）＜O（n1.5）＜O（n2），选项C正确。