BEGIN
if head=tail writeIn('empty’) else BEGIN
head:=head mod m+1； y:=q[head]； END； END；
【练习题】单项选择题：
1.若用一个大小为6的数组来实现循环队列，且当一和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？
A.1和5 B.2和4 C.4和2 D.5和1
2.设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的序列是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是（ ）. A.6 B.4 C.3 D.2
3.如右图所示的循环队列中元素数目是( ).其中 tail=32指向队尾元素，head=15指向队首元素的前 一个空位置，队列空间m=60. A.42 B.16 C.17 D.41
4.3 树
前两节学习的栈和队列属于线性结构.在这种结构中，数据元素的逻辑位置之间呈线性关系，每一个数据元素通常只有一个前件(除第一个元素外)和一个后件(除最后一个元素外).在实际生活中，可以用线性结构描述数据元素之间逻辑关系的问题是很广泛的，但也有很多问题不能依靠线性结构来解决，例如家谱、行政组织机构等都是非线性的数据结构.其中树就是一种非线性的数据结构. (一)树的递归定义为树(Tree)是n(n≥O)个结点的有限集T，T为空时称为空树，否则它满足 如下两个条件：
(1)有且仅有一个特定的称为根(Root)的结点；
6
(2)其余的结点可分为m(m≥0)个互不相交的子集，T1，T2，?，Tm，其中每个子集本身又是一棵树，并称其为根的子树(Subtree).
比如在现实生活中，有如下血统关系的家族可用树形图(图4-3-1)表示：
张源有三个孩子张明、张亮和张丽；张明有两个孩子张林和张维；张亮有三个孩子张平和张群；张丽有两个孩子张晶和张磊.
以上表示很像一棵倒画的树.其中“树根”是张源，树的“分支点\是张明、张亮和张平，该家族的其余成员均是“树叶\，而树枝(即图中的线段)则描述了家族成员之间的关系.显然，以张源为根的树是一个大家庭.它可以分成张明、张亮和张丽为根的三个小家庭；每个小家庭又都是一个树形结构. 以下介绍几个关于树的基本概念.
1.度.一个结点的子树数目称为该结点的度.所有结点中最大的度称为该树的度.如图4-3-2，结点i的度为3，结点t的度为2，结点b的度为1.显然，所有树叶的度为0，该树的度为3. 2.树的层次和高度.树是分层次的，结点所在的层次是从根算起的，根节点在第一层，根的后件在第二层，其余各层依此类推.树中最大的层次称为树的深度，亦称高度.如图中，树共有5层，树的高度为5.
3.森林.若干棵互不相交的树的集合。如图去掉根结点r,其原来的三棵子树的集合即为森林。 (二)二叉树
二叉树（BinaryTree）是树形结构的一个重要类型.许多实际问题抽象出来的数据结构往往是二叉树的形式，即使是一般的树也能简单地转换为二叉树，而且二又树的存储结构及其算法都较为简单，因此二又树显得特别重要.但是值得特别注意的是：二叉树并非是树的特殊情形，它们是两种不同的数据结构.下面给出二叉树的递归定义：二叉树是n(n≥0)个结点的有限集，它或者是空集（n=0）,或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成.
7
二叉树的五种基本形态如图4-3-3所示.
二叉树具有以下重要性质：
性质1二叉树第i层上的结点数目最多为2i-1(i≥l)： 性质2深度为k的二叉树至多有2k-1个结点(k≥1).
性质3在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，
则n0=n2+1.
例、有n个结点的二叉树，已知叶结点个数为n0，写出求度为1的结点的个数nl的计算公式；若此树是深度为k的完全二叉树，写出n为最小的公式；若二叉树中仅有度为0和度为2的结点，写出求该二叉树结点个数n的公式. (1)记度为2的结点个数为n2，则n=n0+n1+n2 ① 又因为除了根结点以外，其余结点均由父结点射出，所以 n=l+nl+2*n2 ② 由①②两式得n1=n+1-2n0
(2)当树是深度为k的完全二叉树时，n的最小值nmin=2k-1 (3)当二叉树中仅有度为0和度为2的结点时，
n=n0+n2.n=2n2+1
所以：n0=n2+1 n=2n0-1
满二叉树和完全二叉树是二叉树的两种特殊情形. 1.满二叉树(Full BinaryuTree)
一棵深度为k且有2k-1个结点的二叉树称为满二叉树.满二叉树的特点： (1)每一层上的结点数都达到最大值.即对给定的高度，它是具有最多结点数的二叉树.
(2)满二叉树中不存在度数为1的结点，每个分支结点均有两棵高度相同的子树，且树叶都在最下一层上.
(3)可以验证具有n个叶结点的满二叉树共有2n-1个结点. 如图(a)是一个深度为4的满二叉树.
8
2.完全二叉树(Complete BinaryTree)
若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树.特点： (1)满二叉树是完全二叉树，完全二叉树不一定是满二叉树.
(2)在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树.
(3)在完全二又树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点.
如图(b)是一棵完全二叉树. (a)满二叉树 .(b)完全二又树
性质4 具有n个结点的完全二叉树的深度为 [lgn]+1或[1g(n+1)]
证明：设所求完全二叉树的深度为k.由完全二叉树定义可得：
深度为k得完全二叉树的前k—l层是深度为k一1的满二叉树，一共有2k-1-1个结点.
由于完全二叉树深度为k，故第k层上还有若干个结点，因此该完全二叉树的结点个数：
n>2k-1-1.
另一方面，由性质2可得：
n≤2k一1，
即： 2k-1-l k-1≤lgn 又因k一1和k是相邻的两个整数，故有 k-1=[lgn]， 由此即得： k=[ lgn] +l 例、 已知一棵完全二叉树共有892个结点，试求：(1)树的高度(2)叶子结点数(3)单支结点数(4)最后一个非终端结点的序号 【解答】(1)已知深度为k的二叉树至多有2k-1个结点(k≥1)，由于29-l<892<210-1所以树的高度为l0. 9 (2)对完全二叉树来说，度为1的结点只能是0或1.由n=n0+nl+n2和n0=n2++1 ①设nl=0，则有：892=n0+0+n2=n2+1+n2=2n2+1，因得到的n2不为整数而出错； ②设n1=1，则有：892：n0+1+n2：n2+l+1+n2=2n2+2，得到n2=445，代入n0=n2+1则最后得到n0=446，故叶子结点数为446. (3)由(2)可知单支结点数为1. (4)对有n个结点的完全二又树，最后一个树叶结点，即序号为n的叶结点其双亲结点n/2，即为最后一个非终端结点，也即序号为向下取整(892/2)=446.此外，由(2)可知：n2=44，n1=1；则最后一个非终端结点的序号为：445+1=446。 (三)二叉树的遍历 所谓遍历（Traversal）是指沿着某条搜索路线，依次对树中每个结点均做一次访问。访问结点所做的操作依赖具体的应用问题。遍历是二叉树上最重要的运算之一，是二叉树上进行其它运算之基础. 1.遍历方案 从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成.因此，在任一给定结点上，可以按某种次序执行三个操作： (1)访问结点本身(N)； (2)遍历该结点的左子树(L)； (3)遍历该结点的右子树(R). 以上三种操作有六种执行次序： NLR、LNR、LRN、NRL、RNL、RLN. 注意：前三种次序与后三种次序对称，故只讨论先左后右的前三种次序. 2.三种遍历的命名 根据访问结点操作发生位置命名： ①NLR：前序遍历(PreorderTraversal亦称(先序遍历)) ——访问结点的操作发生在遍历其左右子树之前. ②LNR：中序遍历(InorderTraversal) ——访问结点的操作发生在遍历其左右子树之中(间). ③LRN：后序遍历(PostorderTraversal) ——访问结点的操作发生在遍历其左右子树之后. 由于被访问的结点必是某子树的根，所以N(Node)、L(Left subtree)和R(Right subtree)又可解释为根、根的左子树和根的右子树.NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历. 10