《C语言程序设计与数据结构》课件第14章.ppt

C语言程序设计与数据结构,第十四章 栈、队列与树,C语言程序设计与数据结构,总体要求： 掌握栈、队列和树的概念、有关术语； 掌握栈、队列的基本操作； 掌握树的定义与二叉树的性质； 掌握二叉树的存储结构及二叉树的先序、中序、后序遍历算法； 学会栈、队列和树的灵活应用。 学习重点： 栈和队列的基本操作； 二叉树的存储和遍历。六种位运算的综合使用,C语言程序设计与数据结构,14.1 栈 14.2 队列 14.3 树,C语言程序设计与数据结构,14.1 栈 14.1.1什么是栈 14.1.2顺序栈的实现,C语言程序设计与数据结构,栈和队列是在软件设计中常用的两种数据结构，它们的逻辑结构和线性表相同。其特点在于运算受到了限制：栈按“后进先出”的规则进行操作，队按“先进先出”的规则进行操作，故称操作受限制的线性表。 树型结构是一种非常重要的非线性结构，它是具有分支关系的层次结构，可以用来描述较复杂的数据关系。树型结构应用非常广泛，特别是在数据处理方面，如在文件系统、编译系统、目录组织等方面，显得更加突出。,C语言程序设计与数据结构,14.1.1 什么是栈 栈（Stack）是限定仅在表的一端进行插入和删除操作的线性表。通常将表中允许插入、删除操作的这一端称为栈顶（top），因此栈顶的当前位置是动态变化的，它由一个称为栈顶指针的位置指示器指示。同时表的另一端被称为栈底（bottom）。栈顶的第一个元素叫做栈顶元素。不含任何数据元素的栈称为空栈。栈的插入操作被形象的称为进栈或入栈，删除操作称为出栈或退栈。 假设有栈S=(a1,a2,an)，如图14.1(a)所示，元素是以a1,a2,an的顺序进栈，因此栈底元素是a1，栈顶元素是an。退栈的第一个元素应为栈顶元素an。 图14.1(a) 栈,C语言程序设计与数据结构,下面举例说明栈的结构特征。 假设有一个很窄的死胡同，胡同里能容纳若干人，但每次只能容许一个人进出。现有五个人，分别编号为，按编号的顺序进入胡同，如图14.1(b)所示。若要出来，必须等退出后才有可能。若要退出，则必须等到依次都退出后才行。这里，人进出胡同的原则是后进去的先出来。换句话说，先进去的后出来。 栈可以比作这里的死胡同，栈顶相当于胡同口，栈底相当于胡同的另一端，进、出胡同可看作栈的插入、删除运算。插入、删除都在栈顶进行，进出都经过胡同口。这表明栈的原则是后进先出。因此，栈又称为后进先出(last in first out)线性表，简称 LIFO表。 栈的基本操作除了在进栈（栈顶插入）、出栈（删除栈顶元素）外，还有建立堆栈（栈的初始化）、判空和取栈顶元素等运算。 基本操作： （1）INI_STACK(S) （2）EMPTY_STACK (S) （3）PUSH_STACK(S, x) （4）POP_STACK(S) （5）TOP_STACK(S),C语言程序设计与数据结构,14.1.2 顺序栈的实现 栈作为一种特殊的线性表，在计算机中也主要有两种基本的存储结构：顺序存储结构和链式存储结构。我们称顺序存储的栈为顺序栈，链式存储的栈为链栈。 顺序栈是用顺序存储结构实现的栈。顺序栈的存储结构可以用C语言中的一维数组来表示。栈的顺序存储结构定义如下： #define MaxSize /* 线性表可能达到的最大长度 */ typedef struct /* 顺序栈类型定义 */ Elemtype dataMaxSize; int top; /* 指示栈顶位置 */ SeqStack; 这里把存放栈中元素的数组和指向栈顶的变量都作为结构体类型SeqStack的分量来定义。鉴于C语言中数组的下标值约定从0开始，则当以C语言作描述语言时，数组的0下标端设为栈底。这样，空栈时，栈顶指针top为-1；入栈时，栈顶指针top加1；出栈时，栈顶指针top减1。,C语言程序设计与数据结构,假设用一维数组sq表示一个栈，图14.2说明了这个顺序栈的几种状态。 图14.2栈顶指针和栈中元素之间的关系 图14.2(a)是空栈；图14.2 (b)是只有一个元素时的状态；图14.2 (c)是A、B、C、D、E、F这六个元素依次进入栈之后的状态；图14.2(d)是删除E、F两个元素后的状态，此时栈中还有四个元素，或许刚出栈的元素E、F仍然在原先的单元存储着，但top指针已经指向了新的栈顶，则元素E、F已不在栈中了，通过这个示意图要深刻理解栈顶指针的作用。 由于栈是一个动态结构，而数组是静态结构，因此会出现所谓的溢出问题。当栈中已经有MaxSize个元素时，如果再进行进栈操作，则会产生溢出，通常称为上溢(overflow)；而对空栈进行出栈操作时，也会产生溢出，通常称为下溢(underflow)。为了避免溢出，在对栈进行进栈操作和出栈操作前，应分别检查栈是否已满或者是否已空。,C语言程序设计与数据结构,顺序栈的基本操作的实现如下： （1）初始化 顺序栈的初始化即构造一个空的顺序栈。为栈结构申请空间，并将栈顶指针赋值为-1。具体算法描述如下： 【算法14.1】构造一个空栈 SeqStack *Init_SeqStack( ) SeqStack *s; s = (SeqStack *) malloc ( sizeof (SeqStack ) ); if (s = = NULL) printf ( “ Out of space!n“ ); else s-top=-1; return (s); （2）判栈空 判栈空运算，即判断一个栈是否为空栈，为空时，返回TRUE，否则返回FALSE。具体算法描述如下： 【算法14.2】 int Empty_SeqStack(SeqStack *s) /* 判断栈s是否为空 */ if (s-top = =-1) return (TRUE); else return (FALSE); ,C语言程序设计与数据结构,（3）进栈 入栈运算，即往栈中插入(或称为压入或推入)一个值为x的新元素。 完成这一操作的基本步骤： (1) 首先判断栈是否已满； (2) 当栈不满时，先修改栈顶指针，将其值加1； (3) 然后把元素x放入栈顶指针指向的位置中。 具体算法描述如下： 【算法14.3】 int Push_SeqStack ( SeqStack *s, Elemtype x ) /* 向栈s中压入一个新元素x为栈顶元素，并返回成功与否的标志 */ if ( s-top = = MaxSize-1) printf ( “Overflow! n“ ); return ( FALSE ); /* 栈满不能入栈，返回FALSE */ else s - top +; s - datas-top = x ; return ( TRUE ); /* 操作成功，返回TRUE */ ,C语言程序设计与数据结构,（4）出栈 出栈运算，即从栈中删除(或称为弹出)一个元素。当栈不空时，可通过将栈顶指针减1，达到元素删除的目的。这里需要说明的是，所谓的删除，只是将栈顶位置下移一位，这样原来的栈顶元素就认为不包括在栈中了。实际上，该元素还存在于原来的存储单元中，只是当新的元素入栈时，会将其覆盖。具体算法描述如下： 【算法14.4】 int Pop_SeqStack ( SeqStack *s , Elemtype *x ) /* 若栈s不为空，则删除栈顶元素，并返回栈顶元素值和删除成功与否的标志 */ if (s-top = =-1) printf ( “Underflow!n“ ); return (FALSE); /* 栈空不能出栈，返回FALSE */ else *x= s-datas-top; s-top - - ; /*修改栈顶指针*/ return (TRUE ); / * 栈顶元素存入*x，返回TRUE */ ,C语言程序设计与数据结构,（5）取栈顶元素 取栈顶元素运算，即当栈不为空时，将栈顶元素取出，而栈本身没有发生任何变化。具体算法描述如下： 【算法14.5】 Elemtype Top_SeqStack ( SeqStack *s ) /* 当栈s不为空时，求栈顶元素 */ if s-top != = -1 return ( s-datas-top ); else return ( SPECIAL); /* 栈为空，返回一个栈中没有的特殊值 */ 说明： (1) 对于顺序栈，入栈时，应首先判栈是否已满，栈满的条件为s-top = = MaxSize-1，栈满时，不能入栈；否则出现空间溢出，引起上溢错误。 (2) 出栈和读栈顶元素操作，应先判栈是否为空，为空时不能操作，否则产生下溢错误。通常栈空时常作为一种控制转移的条件。,C语言程序设计与数据结构,14.2 队列 14.2.1 什么是队列 14.2.2 队列的基本操作,C语言程序设计与数据结构,14.2.1 什么是队列 队列（Queue）是另一种操作受限的线性表，它是只允许在表的一端进行插入，而在另一端进行删除的线性表。能进行插入的一端称为队列的尾（rear），能进行删除的一端称为队列的头（front）。先进入队列的元素称为队列的头元素（队列的头），最后进入队列中的元素称为队列的尾元素（队列的尾）。队列称为先进先出的线性表（First In First Out），简称FIFO表。 例如，一个有六个元素的队列q = (a1、a2、a3、a4、a5、a6)，那么a1 就是队头元素，a6则是队尾元素。入队的顺序依次为a1、a2、a3、a4、a5、a6，那么出队时的顺序将依然是a1、a2、a3、a4、a5、a6，也就是说，a1离开队列后，a2才能退出队列，a1、a2、a3、a4、a5都离开后，a6才能退出队列。队列q的示意图如图14.3所示。 图14.3 队列q的示意图,C语言程序设计与数据结构,14.2.2 队列的基本操作 队列的基本操作： （1）Init_Queue(q) （2）IsEmpty_ Queue(q) （3）En_Queue(q,x) （4）Out_ Queue(q,x) （5）GetHead_ Queue (q,x),C语言程序设计与数据结构,与栈类似，队列通常有两种实现方法，即顺序队列实现和链式队列实现。队列的顺序存储结构称为顺序队，它由一个一维数组(用于存储队列中元素)及两个分别指示队头和队尾的变量组成，这两个变量分别称为队头指针和队尾指针(注意它们并非指针型变量)。因为在操作过程中，队头位置和队尾位置经常变化，所以设置了头、尾两个指针。通常约定队尾指针指示队尾元素在一维数组中的当前位置，队头指针指示队头元素在一维数组中的当前位置的前一个位置(这样设置是为了某些操作的方便，并不是唯一的方法)。由此可见顺序队列实际上就是运算受限制的顺序表。顺序队列的类型定义如下： #define MaxSize 线性表可能达到的最大长度 typedef struct Elemtype dataMaxSize; /* 队员的存储空间 */ int front,rear; /* 队头，队尾指针 */ SeqQueue; 定义一个指向队的指针变量为 SeqQueue *sq,C语言程序设计与数据结构,队列的数据区为：sq-data0sq-dataMaxSize -1。 每当插入新的队尾元素时，在不考虑溢出的情况下，队尾指针加1，指向新位置后，元素入队。操作如下： sq-rear+; sq-datasq-rear=x; 每当删除队头元素时，在不考虑队空的情况下，队头指针加1，表明队头元素出队。操作如下： sq-front+; x=sq-datasq-front; /* 原队头元素送x中 */ 整个队列的数据区为sq-data0至sq-dataMaxSize -1。队中元素的个数m为队尾指针sq-rear减去队头指针sq-front的值。队满时，m= MaxSize；队空时，m=0。 置空队则为sq-front=sq-rear=-1; 如图14.4所示，是一个队列的操作示意图，它描述了队列的变化过程。 图14.4 队列操作示意图,C语言程序设计与数据结构,从图14.4中可以看出，在这样的顺序队列中，入队操作就是要在队尾增加元素，并将尾指针rear后移。出队时，则是头指针front后移。进行了一定数量的入队和出队后，会使整个队列整体向后移动。这样就可能会出现图14.4(d)中的情况：队尾指针rear已指到数组的最后一个元素，即rear=MaxSize-1，此时若再执行入队操作，便会出现溢出。然而，由于在此操作之前可能也执行了若干次出队操作，因而数组的前面部分可能还有闲置的元素空间，即这种溢出并非是真的没有可用的存储空间，故称这种溢出现象为假溢出。显然，必须要解决假溢出问题，才能保证队列结构的正确应用。,C语言程序设计与数据结构,采用循环结构就可以解决假溢出的问题，具体方法是：将数组元素data0看作是dataMaxSize-1的下一个存储位置，也就是说，将数组看作是一个循环结构。这样，当执行入队或出队操作时，如果原指针rear或front的值为MaxSize-1，即已经指向了数组的最后一个元素时，则执行入队或出队操作后，相应指针的值就要变为0。这样就可以使被删除的结点在被使用，称这种形式的队列为循环队列，如图14.5所示。 图14.5 循环队列示意图,C语言程序设计与数据结构,循环队列操作如图14.6所示。 图14.6 循环队列操作示意图,C语言程序设计与数据结构,队列的链式存储结构就是用一个线性链表来表示队列，队列中的每个元素对应链表中的一个结点，这样的队列简称链式队列。 在采用链式队列存储时，首先要确定链表的形式及队尾的位置。其讨论如下： (1) 一个链式队列显然需要两个分别指示队头和队尾的指针(分别称为头指针和尾指针)才能唯一确定。由于队列的入队和出队操作分别是在队尾和队头进行，故将链表头作为队头、链表表尾作为队尾比较合适。出队时，只需要进行删除表头的操作，而入队时所要做的操作是在表尾添加结点。 (2) 和线性表的单链表一样，为了操作方便起见，也给链队列添加一个头结点，并令头指针指向头结点。 链式队列的结构如图14.7所示。 图14.7 链式队列示意图,C语言程序设计与数据结构,链式队列的结点类型描述如下： typedef struct queuenode /* 结点结构 */ Elemtype data; struct queuenode *next; QueueNode; 为了强调队头和队尾是队列的属性，将队列封装，引入链式队列类型： typedef struct QueueNode *front, *rear; /* 队头和队尾指针 */ LinkQueue; 按这种思想建立的带头结点的链式队列如图14.8所示。 图14.8 头尾指针封装在一起的链式队列,C语言程序设计与数据结构,14.3 树 14. 3 .1 什么是树 14.3.2 二叉树的概念及性质 14.3.3 二叉树的存储及遍历,C语言程序设计与数据结构,14. 3 .1 什么是树 1.树的定义 树（Tree）是n（n0）个结点的有限集合。当n0时，称这棵树为空树；当n0时，该集合需满足以下条件： （1）有且仅有一个称为根（root）的结点，它没有直接前驱，但有零个或者多个直接后继。 （2）其余n-1个结点可以被划分成m（m0）个互不相交的有限集T1，T2，Tm，其中每一个集合Ti（1im）又是一棵树，称为根root的子树。每棵子树的根结点有且仅有一个直接前驱，但有零个或者多个直接后继。 可见树的定义是一个递归定义，它反映了树的固有特性，因为一棵树是由根和它的子树构成，而子树又由子树的根和更小的子树构成。树的表示形式如图14.9所示。 图14.9 树的一般形式,C语言程序设计与数据结构,2.树的常用术语 结点：包含一个数据元素及若干指向其他结点的分支信息。 结点的度：一个结点的子树个数。图14.9中，A的度为3，B的度为1。 树的度：树中结点的最大度。图14.9中，树的度为3。 终端结点(叶子结点)：度为0的结点，即无后继的结点。 分支结点：度不为0的结点，也称非终端结点。 孩子结点：一个结点的直接后继结点。 双亲结点：一个结点的直接前驱结点称为该结点的双亲结点。 结点的层次：根为第一层，根的直接后继所在的层为第二层，以此类推。 树的深(高)度：树中结点的最大层次称为树的深度(或高度)。 兄弟结点：同一双亲结点的孩子结点之间互称兄弟结点。 祖先结点：一个结点的祖先是从根到该结点所经分支上的所有结点。 子孙结点：以某结点为根的子树中的任一结点都称为该结点的子孙结点。 有序树：结点的子树从左到右有顺序，否则，称为无序树。图14.9中的两棵树，若看成是有序树，它们是不等价的；若看成是无序树，两者相等。 森林：若干棵的互不相交的树的集合就是森林，一棵树除去根结点后的子树集合也是森林。 图14.10 有序树和无序树的比较,C语言程序设计与数据结构,14.3.2 二叉树的概念及性质 二叉树（Binary Tree）是一种特殊的树形结构，它必须满足以下两个条件： （1）树中每个结点的度都不大于2； （2）树中每个结点的子树有左右之分，其次序不能任意颠倒。 图14.11给出了二叉树的五种基本形态。 （a）空二叉树 （b）只有根结点的二叉树 （c）只有左子树的二叉树 （d）只有右子树的二叉树 （e）左右子树均非空的二叉树 图14.11 二叉树的五种基本形态,C语言程序设计与数据结构,满二叉树：一棵深度为k并且有2k-1个结点的二叉树称为满二叉树。在满二叉树中，每层结点都是满的，即每层结点都具有最大结点树。图14.12所示的二叉树，即为一棵满二叉树。 完全二叉树：深度为k，结点数为n的二叉树，当且仅当其每个结点都与深度为k的满二叉树中编号从1至n的结点一一对应，称为完全二叉树。 完全二叉树的特点是： 叶子结点只能出现在层次最大的两层上； 对任意一结点，若其右分支下的子孙的最大层次是L，则其左分支下的子孙的最大层次一定是L或L+1。 图14.13 完全二叉树 图14.12 满二叉树,C语言程序设计与数据结构,由于二叉树是一种特殊的树，故前面所介绍的有关树的术语都适用于二叉树。另外二叉树还具有下列性质： 性质1： 在二叉树的第i层上至多有2i-1个结点(i1)。 性质2： 深度(高度)为k的二叉树最大结点数为2k-1(k0)。 性质3： 对任意一棵二叉树，如果叶子结点个数为n0，度为2的结点个数为n2，则有n0=n2+1。 性质4： 具有n个结点的完全二叉树的深度为。其中表示不大于x的最大整数。 性质5： 如果将一棵有n个结点的完全二叉树从上到下，从左到右对结点编号为1，2，n，然后按此编号将该二叉树中各结点顺序地存放于一个一维数组中，并简称编号为j的结点为 j(1jn)，则有如下结论成立： (1) 若 j=1，则结点j为根结点，无双亲，否则j的双亲为； (2) 若2jn，则结点j的左孩子为2j，否则无左孩子。即编号为j且满足2jn的结点为叶子结点； (3) 若2j+1n，则结点j的右孩子为2j+1，否则无右孩子； (4) 若结点j序号为奇数且不等于1，则它的左兄弟为j-1； (5) 若结点j序号为偶数且不等于n，它的右兄弟为j+1。,C语言程序设计与数据结构,14.3.3 二叉树的存储及遍历 1.二叉树的存储结构 二叉树的结构是非线性的，每一个结点最多可以有两个后继。 二叉树的存储结构有两种：顺序存储结构和链式存储结构。 （1）顺序存储结构 此结构是将二叉树的所有结点，按照一定的次序，存储到一片连续的存储单元中。因此，必须将结点排成一个适当的线性序列，使得结点在这个序列中的相应位置能反映出结点之间的逻辑关系。这种结构特别适用于完全二叉树。 在一棵具有n个结点的完全二叉树中，从树根起，自上层到下层，逐层从左到右给所有结点编号，就能得到一个足以反映整个二叉树结构的线性序列。 因此，可以对树的类型作如下说明： #define MAX 50 typedef struct ElementType aMAX; int count;BinTree; 在结构体类型中，count成员项用于记录完全二叉树中结点的个数。,C语言程序设计与数据结构,将数组下标作为结点名称(编号)，就可将二叉树中所有结点的标号存储在一维数组中。例如，图14.14中的二叉树的顺序存储结构如图14.15所示。 图14.14 完全二叉树的结点编号 图14.15 完全二叉树的顺序存储示意图,C语言程序设计与数据结构,对于图14.14所示的一棵完全二叉树，做如下实现为 (1) 给出某一结点编号x，求出该结点的左孩子。算法如下： 【算法14.6】 typedef char ElementType ElementType LChild(BinTree BT,int x) if(x=1 顺序存储方式对于一棵完全二叉树来说非常方便，但对于一般的二叉树，空间的浪费太大，这是顺序存储结构的一大缺点。为解决这一问题，可用链式存储结构来存储树。,C语言程序设计与数据结构,（2）链式存储结构 将一个结点分成三部分，一部分存放结点本身信息，另外两部分为指针，分别存放左、右孩子的地址。结点形式如右图所示： LChildDataRChild对于图14.15所示二叉树： (a) 完全二叉树 (b) 非完全二叉树 图14.15 两种不同类型的树 用二叉链表形式描述，如图14.16所示。 (a)完全二叉树的二叉链表表示法(b) 非完全二叉树的二叉链表表示法 图14.16 二叉树的二叉链表表示法,C语言程序设计与数据结构,1) 二叉链表的数据类型 数据类型描述如下： typedef struct node ElementType data; struct node *LChild,*RChild; BinNode,*BinTree; 2) 二叉链表的建立 为了用二叉链表表示一棵二叉树，在此介绍建立二叉链表的算法(假设ElementType为char型)。假设二叉链表的数据类型描述如刚才所述，为建立二叉链表，用一个一维数组来模拟队列，存放输入的结点，但是，输入结点时，必须按完全二叉树形式，才能使结点间满足性质5，若为非完全二叉树，则必须给定一些假想结点(虚结点)，使之符合完全二叉树形式。为此，在输入结点值时，存在的结点则输入它对应的字符，不存在的结点(虚结点)，输入逗号，最后以一个特殊符号“#”作为输入的结束，表示建二叉链表已完成。建成的二叉链表可以由根指针root唯一确定。算法描述如下：,C语言程序设计与数据结构,【算法14.8】 #include typedef char ElementType; typedef struct node ElementType data; struct node *LChild,*RChild; BinNode, *BinTree; 建立树的函数如下： BinTree Create() BinTree q100,s; /* 定义q数组作为队列存放二叉链表中结点，100为最大容量，s为二叉链表中结点* / BinTree root ; /* 二叉链表的根指针 */ int front=1,rear=0; /* 定义队列的头、尾指针 */ char ch; /* 结点的data域值 */ root=NULL; ch=getchar(); while(ch!=#) /* 输入值为#号,算法结束 */ s=NULL; if(ch!=,) /* 输入数据不为逗号,表示不为虚结点,否则为虚结点 */ s=(BinNode *)malloc(sizeof(BinNode); s-data=ch;s-LChild=NULL; s-RChild=NULL; ,rear+;qrear=s; /* 新结点或虚结点进队 */ if(rear=1) root=s; else if(s!=NULL) ,C语言程序设计与数据结构,2.二叉树的遍历 二叉树的遍历是指按照一定的规律或路径对二叉树中的每一个结点进行访问且仅访问一次。遍历在顺序结构中非常容易实现，但是在非线性结构的二叉树中，由于每个结点都有可能存在两棵子树，因此，遍历操作就是将二叉树中结点按一定规律线性化的操作，目的是将非线性化结构变成线性化的访问序列。二叉树的遍历操作是二叉树中最基本的运算。 日常习惯中，访问顺序一般按先左后右的顺序。若限定先左后右，则只有DLR，LDR，LRD三种，分别称为先序法(先根次序法)，中序法(中根次序法)，后序法(后根次序法)。三种遍历的递归算法如下。 1) 先序法(DLR) 若二叉树为空，则空操作，否则执行如下三个操作：访问根结点；先序遍历左子树；先序遍历右子树。 2) 中序法(LDR) 若二叉树为空，则空操作，否则执行如下三个操作：中序遍历左子树；访问根结点；中序遍历右子树。 3) 后序法(LRD) 若二叉树为空，则空操作，否则执行如下三个操作：后序遍历左子树；后序遍历右子树；访问根结点。 有一棵二叉树，如图14.19所示： 则其按先序、中序、后序遍历得到的访问序列如下。 (1) 先序遍历序列：A、B、D、E、G、H、C、F； (2) 中序遍历序列：D、B、G、E、H、A、C、F； (3) 后序遍历序列：D、G、H、E、B、F、C、A。 图14.19 树,C语言程序设计与数据结构,以二叉链表作为存储结构，描述二叉树的递归遍历算法如下。 (1) 先序遍历算法，算法如下： 【算法14.9】 void PreOrder(BinTree r) if (r!=NULL) /* NULL值为0，也可用if(r) */ Visit(r-data); /* 访问根结点 */ PreOrder(r-LChild); /* 先序遍历左子树 */ PreOrder(r-RChild); /* 先序遍历右子树 */ (2) 中序遍历算法，算法如下： 【算法14.10】 void MidOrder(BinTree r) if (r) MidOrder(r-LChild); /* 中序遍历左子树 */ Visit(r-data); /* 访问根结点 */ MidOrder(r-RChild); /* 中序遍历右子树 */ (3) 后序遍历算法，算法如下： 【算法14.11】 void PreOrder(BinTree r) if (r) Visit(r-data); PreOrder(r-LChild); PreOrder(r-RChild); Visit(r-data); ,C语言程序设计与数据结构,14.4 典型习题分析解答 【例14.1】一个栈的入栈序列为a，b，c，d，e，则下列序列中不可能是栈的输出序列的是_。 (A) edcba (B) decba (C) dceab (D) abcde 答案：C 分析： 本题主要考点是栈的特点：先进后出，所以eab是不可能出现的。d第一个出栈，说明a，b，c都已经入栈，然后可以是栈顶元素c先出栈，再将e入栈然后出栈，这时a，b都已经入栈，所以出栈的序列只能是b，a。 【例14.2】若已知一个栈的入栈序列为1，2，3，n，其输出序列为s1，s2，s3，sn，若s1=n，则si（1in）为_。 (A)i (B)n=i (C)n-i+1 (D)不确定 答案：C 分析： 当s1=n，即n是第一个最早出栈的，根据栈的原理，n必定是最后一个入栈的，所以输入的顺序必定是1，2，3，n，即n出栈的之后1，2，3，n-1都已经入栈，所以出栈的序列必定为n， ，3，2，1，所以答案选C。,C语言程序设计与数据结构,【例14.3】对于一个栈，给出输入项a，b，c。如果输入项序列由a，b，c所组成，试给出全部可能的输出序列_。 答案：abc，acb，bac，bca，cba 分析： 本题利用栈的“先进先出”的特点，有如下几种情况： a进 a出 b进 b出 c进 c出 产生的输出序列为abc a进 a出 b进 c进 c出 b出 产生的输出序列为acb a进 b进 b出 a出 c进 c出 产生的输出序列为bac a进 b进 b出 c进 c出 a出 产生的输出序列为bac a进 b进 c进 c出 b出 a出 产生的输出序列为cba 【例14.4】在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，则当做出栈处理时，top变化为_。 (A) top- (B)top=0 (C)top不变 （D)top+ 答案：A 分析： 顺序栈是用顺序存储结构实现的栈，同时设置了一个栈顶指针top来动态地指示栈顶元素在顺序栈中的位置。通常以top=-1表示空栈，当做出栈操作时top指针应该下移。 【例14.5】已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为_。 (A)GEDHFBCA (B)DGEBHFCA (C)ABCDEFGH (D)ACBFEDHG 答案：B 分析： 利用前序和中序遍历的方法可以确定二叉树的结构，具体步骤如下：前序遍历的第一个结点A为树的根结点；中序遍历中A的左边的结点为A的左子树，A的右边的结点为A的右子树；再分别对A的左右子树进行上述处理，直到每个结点都找到正确的位置。,C语言程序设计与数据结构,【例14.6】树是结点的集合，它的根结点的数目是_。 (A)有且只有一个 (B)1或者多于1 (C)0或1 (D)至少2 答案：C 分析： 树是n（n0）个结点的有限集合，当n=0时称为空树，对于空树没有根结点，即根结点的个数为0，对于非空树有且只有一个根结点，所以树的根结点的数目为0或者1。 【例14.7】栈和队列的共同特点是_。 (A)都是先进先出 (B)都是先进后出 (C)只允许在端点处插入和删除元素 (D)没有共同点 答案：C 分析： 栈和队列都是一种特殊的操作受限的线性表，只允许在端点处进行插入和删除。二者的区别是：栈只允许在表的一端进行插入或删除操作，是一种“后进先出”的线性表；而队列只允许在表的一端进行插入操作，在另一端进行删除操作，是一种“先进先出”的线性表。 【例14.8】在深度为5的满二叉树中，叶子结点的个数为_。 (A)32 (B)31 (C)16 (D)15 答案：C 分析： 本题考察的是满二叉树的性质。所谓满二叉树是指这样的一种二叉树：除了最后一层外，每一层上的所有的结点都有两个叶子结点。这就是说，在满二叉树中，层上的结点数都达到最大值，即在满二叉树的第k层上有2k-1个结点，并且深度为m的满二叉树有2m-1个结点。,C语言程序设计与数据结构,【例14.9】具有3个结点的二叉树有_。 (A)2种形态 (B)4种形态 (C)7种形态 (D)5种形态 答案：D 分析： 具有3个结点的二叉树具有以下的几种形态： 【例14.10】设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为_。 (A)12 (B)13 (C)14 (D)15 答案：B 分析：本题考查二叉树的基本概念及其基本性质（N0=N2+1）。按照题目的要求可得到满足条件的二叉树，如下图所示： 故该二叉树中总的结点个数为13。 【例14.11】对下列二叉树进行前序遍历的结果是_。 (A)ABEFCDG (B)EFBCGDA (C)FEGDCBA (D)ABECFDG 答案：A 分析： 二叉树先序遍历的含义是：首先访问根结点，然后按照前序遍历的方法访问根结点的左子树，最后按前序遍历右子树，前序遍历二叉树的过程是一个递归的过程。根据题目中给出的二叉树的结构可知前序遍历的结果是：ABEFCDG。,C语言程序设计与数据结构,【例14.12】编写算法判断二叉树是否是完全二叉树。 分析：完全二叉树是指在一棵二叉树中除最后一层外，其余层都是满的，并且最后一层或者是满的，或者在右边缺少连续若干结点。要判定一棵二叉树是否完全二叉树，应先建立一棵二叉树，此例采用链式存储结构的先序算法建立一棵二叉树。判定一棵二叉树是否是完全二叉树，可以使用队列，在层次遍历的过程中利用完全二叉树“若某结点无左孩子，就一定没有右孩子”的原则进行判断。 答案： #include typedef char ElementType; typedef struct node ElementType data; struct node *LChild,*RChild; BinNode, *BinTree; void CreateBinTree(BinTree *root) char ch; ch=getchar(); if (ch=#) *root=NULL; else *root=(BinTree)malloc(sizeof(BinNode); (*root)-data=ch; CreateBinTree( ,int JudgeComplete(BinTree bt) /* 判断二叉树是否是完全二叉树，是返回1，不是返回0 */ int tag=0,front,rear; BinTree p=bt,Q50; /* Q是队列，元素是二叉树结点指针，容量足够大 */ if(p=NULL) return 1; front=rear=0; Q+rear=p; /* 初始化队伍，根结点指针入队 */ while(front!=rear) p=Q+front; if(p-LChild ,