栈

  栈的定义：栈是一种特殊的表这种表只在表头进行插入和删除操作。因此，表头对于栈来说具有特殊的意义，称为栈顶。相应地，表尾称为栈底。不含任何元素的栈称为空栈。
  栈的逻辑结构：假设一个栈S中的元素为an,an-1,..,a1，则称a1为栈底元素，an为栈顶元 素。栈中的元素按a1 ,a2,..,an-1,an的次序进栈。在任何时候，出栈的元素都是栈顶元素。换句话说，栈的修改是按后进先出的原则进行的，如图1所示。因此，栈又称为后进先出(Last In First Out)表，简称为LIFO表。所以，只要问题满足LIFO原则，就可以使用栈。
 

1、已知元素（8，25，14，87，51，90，6，19，20），问这些元素以怎样的顺序进入栈，才能使出栈的顺序满足：8在51前面；90在87的后面；20在14的后面；25在6的前面；19在90的后面。（     ）。
 A）20，6，8，51，90，25，14，19，87   B）51，6，19，20，14，8，87，90，25
 C）19，20，90，7，6，25，51，14，87   D）6，25，51，8，20，19，90，87，14
 E）25，6，8，51，87，90，19，14，20

2、某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时刻该车站状态为空，从这一时刻开始的出入记录为：“进，出，进，进，出，进，进，进，出，出，进，出”。假设车辆入站的顺序为1，2，3，……，则车辆出站的顺序为（  ）。

A. 1, 2, 3, 4, 5   B. 1, 2, 4, 5, 7   C. 1, 3, 5, 4, 6   D. 1, 3, 5, 6, 7   E. 1, 3, 6, 5, 7

3、某大学计算机专业的必修课及其先修课程如下表所示：

请你判断下列课程安排方案哪个（些）是合理的（  ）。

A. C₀, C₁, C₂, C₃, C₄, C₅, C₆, C₇    B. C₀, C₁, C₂, C₃, C₄, C₆, C₇, C₅

C. C₀, C₁, C₆, C₇, C₂, C₃, C₄, C₅    D. C₀, C₁, C₆, C₇, C₅, C₂, C₃, C₄

E. C₀, C₁, C₂, C₃, C₆, C₇, C₅, C₄

4．设栈S和队列Q的初始状态为空，元素e ₁ ，e ₂ ，e ₃ ，e ₄ ，e ₅ ，e ₆依次通过栈S，一个元素出栈后即进入队列Q，若出队的顺序为e ₂ ，e ₄ ，e ₃ ，e ₆ ，e ₅ ，e ₁ ，则栈S的容量至少应该为（  ）。

    A）2  B）3  C）4  D）5

队列

队列的定义：
队列是一种特殊的线性表，对这种线性表，删除操作只在表头(称为队头)进行，插入操作只在表尾(称为队尾)进行。队列的修改是按先进先出的原则进行的，所以队列又称为先进先出(First In First Out)表，简称FIFO表。
队列的数学性质：
假设队列为a1,a2,..,an，那么a1就是队头元素，an为队尾元素。队列中的元素是按a1,a2,..,an的顺序进入的，退出队列也只能按照这个次序依次退出。也就是说，只有在a1离开队列之后，a2才能退出队列，只有在a1,a2,..,an-1都离开队列之后，an才能退出队列。图1是队列的示意图。
 

                                            树和二叉树
树的概念
树的递归定义如下：（1）至少有一个结点（称为根）（2）其它是互不相交的子树

1.树的度——也即是宽度，简单地说，就是结点的分支数。以组成该树各结点中最大的度作为该树的度，如上图的树，其度为3;树中度为零的结点称为叶结点或终端结点。树中度不为零的结点称为分枝结点或非终端结点。除根结点外的分枝结点统称为内部结点。
2.树的深度——组成该树各结点的最大层次，如上图，其深度为4；
3.森林——指若干棵互不相交的树的集合，如上图，去掉根结点A，其原来的二棵子树T1、T2、T3的集合{T1,T2,T3}就为森林；
4.有序树——指树中同层结点从左到右有次序排列，它们之间的次序不能互换，这样的树称为有序树，否则称为无序树。
5.树的表示
树的表示方法有许多，常用的方法是用括号：先将根结点放入一对圆括号中，然后把它的子树由左至右的顺序放入括号中，而对子树也采用同样的方法处理；同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。如上图可写成如下形式：
 (A(B(E(K,L),F),C(G),D(H(M),I,J)))
                                          二叉树
1.二叉树的基本形态：
二叉树也是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：

(1)空二叉树——(a)；
(2)只有一个根结点的二叉树——(b)；
(3)右子树为空的二叉树——(c)；
(4)左子树为空的二叉树——(d)；
(5)完全二叉树——(e)
注意：尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形。
2.两个重要的概念：
(1)完全二叉树——只有最下面的两层结点度小于2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树；
(2)满二叉树——除了叶结点外每一个结点都有左右子女且叶结点都处在最底层的二叉树,。

3.二叉树的性质
(1) 在二叉树的第i层上至多有2i-1个结点(i>=1)；
(2) 深度为h的二叉树最多有2h-1个结点(h>=1)；
(3) 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；
(4) 具有n个结点的完全二叉树的深度为int（log2n）+1
4.二叉树的遍历运算（递归定义）假如以L、D、R分别表示遍历左子树、遍历根结点和遍历右子树，遍历整个二叉树则有DLR、LDR、LRD、
DRL、RDL、RLD六种遍历方案。若规定先左后右，则只有前三种情况，分别规定为：
                  DLR——先（根）序遍历，
                  LDR——中（根）序遍历，
                  LRD——后（根）序遍历。
1、先序遍历二叉树的操作定义为：
（1）访问根结点；
（2）先序遍历左子树；
（3）先序遍历右子树。
2、中序遍历二叉树的操作定义为：
（1）中序遍历左子树；
（2）访问根结点；
（3）中序遍历右子树。
3、后序遍历二叉树的操作定义为：
（1）后序遍历左子树；
（2）后序遍历右子树；
（3）访问根结点。
5、完全二叉树的特点是：
（1)所有的叶结点都出现在第k层或k－1层。
（2）错任一结点，如果其右子树的最大层次为1，则其左子树的最大层次为1或l＋1。
性质：具有n个结点的完全二叉树的深度为[log2n]＋1。
（符号【x】表示不大于x的最大整数。）
假设此二叉树的深度为k，则根据性质2及完全二叉树的定义得到：2k-1－1已知一棵二叉树的前序遍历的结果是ABECDFGHIJ, 中序遍历的结果是EBCDAFHIGJ, 试画出这棵二叉树。
【解答】
当前序序列为ABECDFGHIJ，中序序列为EBCDAFHIGJ时，逐步形成二叉树的过程如下图所示
 

习题：

1.        对于图6.29给出的树，指出树中的根结点、叶结点和分支结点。并指出各个结点的度数和层数。

2. 对图6.29所示的树，采用先根次序、后根次序和中根次序遍历。问得到怎样的结点序列？

3. 已知某二叉树的先根遍历序列为：A，B，D，E，G，C，F，H，I，J，对称次序遍历序列为：D，B，G，E，A，H，F，I，J，C，试给出该二叉树的后根次序遍历序列。