7.2.4 队列

1. 队列的基本概念

队列是只允许在一端进行删除，在另一端进行插入的顺序表，通常将允许 删除的这一端称为队头，允许插入的这一端称为队尾。当表中没有元素时称为空队列。

队列的修改是依照先进先出的原则进行的，因此队列也称为先进先出的线 性表，或者后进后出的线性表。例如：火车进遂道，最先进遂道的是火车头， 最后是火车尾，而火车出遂道的时候也是火车头先出，最后出的是火车尾。若 有队列：Q =(q1,q2,?,qn)那么，q1为队头元素（排头元素），qn为队尾元素。队列中的元素是按照 q1，q2，?，qn 的顺序进入的，退出队列也只能按照这个次序依次退出，即只有在 q1，q2，?，qn-1都退队之后，qn才能退出队列。因最先进入队列的元素将最先出队， 所以队列具有先进先出的特性，体现“先来先服务”的原则。队头元素q1是最先被插入的元素，也是最先被删除的元素。队尾元素qn是 最后被插入的元素，也是最后被删除的元素。因此，与栈相反，队列又称为“先进先出”（First In First Out，简称 FIFO） 或“后进后出”（Last In Last Out，简称 LILO）的线性表。 2. 队列运算

入队运算是往队列队尾插入一个数据元素；退队运算是从队列的队头删除一个数据元素。队列的顺序存储结构一般采用队列循环的形式。循环队列 s=0 表示队列空；s=1 且 front=rear 表示队列满。计算循环队列的元素个数：“尾指针减头指针”， 若为负数，再加其容量即可。

第13页共35页

7.2.5 链表

在链式存储方式中，要求每个结点由两部分组成：一部分用于存放数据元素 值，称为数据域；另一部分用于存放指针，称为指针域。其中指针用于指向该结 点的前一个或后一个结点（即前件或后件）。

链式存储方式既可用于表示线性结构，也可用于表示非线性结构。 1.线性链表

线性表的链式存储结构称为线性链表。

在某些应用中，对线性链表中的每个结点设置两个指针，一个称为左指针， 用以指向其前件结点；另一个称为右指针，用以指向其后件结点。这样的表称为 双向链表。 在线性链表中，各数据元素结点的存储空间可以是不连续的，且各数据元素 的存储顺序与逻辑顺序可以不一致。在线性链表中进行插入与删除，不需要移动 链表中的元素。 线性单链表中，HEAD 称为头指针，HEAD=NULL（或 0）称为空表。 如果是双项链表的两指针：左指针（Llink）指向前件结点，右指针（Rlink）指向后件结点。 线性链表的基本运算：查找、插入、删除。 2. 带链的栈

栈也是线性表，也可以采用链式存储结构。带链的栈可以用来收集计算机存储空间中所有空闲的存储结点，这种带链的栈称为可利用栈。

7.2.6 二叉树

1. 二叉树概念

二叉树是一种很有用的非线性结构，具有以下两个特点： ① 非空二叉树只有一个根结点；

② 每一个结点最多有两棵子树，且分别称为该结点的左子树和右子树。 在二叉树中，每一个结点的度最大为 2，即所有子树（左子树或右子树）也均为二叉树。另外，二叉树中的每个结点的子树被明显地分为左子树和右子树。

在二叉树中，一个结点可以只有左子树而没有右子树，也可以只有右子树而 没有左

第14页共35页

子树。当一个结点既没有左子树也没有右子树时，该结点即为叶子结点。

例如，一个家族中的族谱关系如图所示：

A 有后代 B，C；B 有后代 D，E；C 有后代 F。 图 1-1 二叉树图 表 1-2 二叉树的基本概念

在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点父结点只有一个，称为树的根结点，简称树的根。例如，在图 1-1 中，结点 （根） A 是树的根结点。 在树结构中，每一个结点可以有多个后件，称为该结点的子结点。没有子结点和叶后件的结点称为叶子结点。例如，在图 1-1 中，结点 D，E，F 均为叶子结点 子结点。 在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。例如，在图 1-1 中，根结点 A 和结点 B 的度为 2，结点C 的度为 1，叶子结点 D，E，F 的度为 0。所以，该树的度为 2。 定义一棵树的根结点所在的层次为 1，其他结点所在的层次等于它的父结点所在的层次加 1。树的最大层次称为树的深度。例如，在图 1-1 中，根结点A 在第 1 层，结点 B，C 在第 2 层，结点 D，E，F 在第 3 层。该树的深度为 3。 在树中，以某结点的一个子结点为根构成的树称为该结点的一棵子树。 度 深度 子树 2. 二叉树基本性质

二叉树具有以下几个性质：

性质 1：在二叉树的第 k 层上，最多有 2k-1（k≥1）个结点。 性质 2：深度为 m 的二叉树最多有 2m-1 个结点。

性质 3：在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。

第15页共35页

性质 4：具有n个结点的二叉树，其深度至少为[log2n]+1，其中[log2n]表示 取log2n的整数部分。 3. 满二叉树与完全二叉树 1) 满二叉树

满二叉树是指这样的一种二叉树：除最后一层外，每一层上的所有结点都有 两个子结点。在满二叉树中，每一层上的结点数都达到最大值，即在满二叉树的第 k 层上有 2k-1 个结点，且深度为 m 的满二叉树有 2m-1 个结点。

2) 完全二叉树

完全二叉树是指这样的二叉树：除最后一层外，每一层上的结点数均达到最大值；在最后一层上只缺少右边的若干结点。 对于完全二叉树来说，叶子结点只可能在层次最大的两层上出现：对于任何一个结点，若其右分支下的子孙结点的最大层次为 p，则其左分支下的子孙结点 的最大层次或为 p，或为 p+1。

完全二叉树具有以下两个性质：

性质 1：具有 n 个结点的完全二叉树的深度为[log2n]+1。

性质 2：设完全二叉树共有 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；否则该结点无右子结点。 1.6.2 二叉树的遍历

在遍历二叉树的过程中，一般先遍历左子树，再遍历右子树。在先左后右的 原则下，根据访问根结点的次序，二叉树的遍历分为三类：前序遍历、中序遍历 和后序遍历。 （1）前序遍历 先访问根结点，然后遍历左子树，最后遍历右子树；并且在遍历左、右子树时，仍需先访问根结点，然后遍历左子树，最后遍历右子树。例如，对图 1-1 中 的二叉树进行前序遍历的结果（或称为该二叉树的前序序列）为：A，B，D，E， C，F。 （2）中序遍历 先遍历左子树、然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。例如，对图 1-1 中的二叉树进行中序遍历的结果（或称为该二叉树的中序序列）为：D，B，E，A，C，

第16页共35页