数据结构之(队、栈、二叉树)

（队、栈、二叉树）数据（Data）数据是信息的载体。它能够被计算机识别、存储和加工处理，是计算机程序加工的'原料”。随着计算机应用领域的扩大，数据的范畴包括：整数、实数、字符串、图像和声音等。数据元素（DataElement）数据元素是数据的基本单位。数据元素也称元素、结点、顶点、记录。一个数据元素可以由若干个数据项（也可称为字段、域、属性）组成。数据项是具有独立含义的最小标识单位。数据结构（DataStructure）指的是数据之间的相互关系，即数据的组织形式。一般包括以下三方面内容：数据元素之间的逻辑关系，也称数据的逻辑结构（LogicalStructure）；数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。数据元素及其关系在计算机存储器内的表示，称为数据的存储结构（StorageStructure）；数据的存储结构是逻辑结构用计算机语言的实现（亦称为映象），它依赖于计算机语言。对机器语言而言，存储结构是具体的。一般，只在高级语言的层次上讨论存储结构。数据的运算，即对数据施加的操作。数据的运算定义在数据的逻辑结构上，每种逻辑结构都有一个运算的集合。最常用的检索、插入、删除、更新、排序等运算实际上只是在抽象的数据上所施加的一系列抽象的操作。（1） 逻辑结构表中的每一行是一个数据元素（或记录、结点）它由学号、姓名、各科成绩及平均成绩等数据项组成。表中数据元素之间的逻辑关系是：对表中任一个结点，与它相邻且在它前面的结点（亦称为直接前趋（ImmediatePredecessor））最多只有一个；与表中任一结点相邻且在其后的结点（亦称为直接后继（ImmediateSuccessor））也最多只有一个。表中只有第一个结点没有直接前趋，故称为开始结点；也只有最后一个结点没有直接后继。故称之为终端结点。例如，表中”马二”所在结点的直接前趋结点和直接后继结点分别是”丁一”和”张三”所在的结点，上述结点间的关系构成了这张学生成绩表的逻辑结构。（2） 存储结构该表的存储结构是指用计算机语言如何表示结点之间的这种关系，即表中的结点是顺序邻接地存储在一片连续的单元之中，还是用指针将这些结点链接在一起？（3） 数据的运算在上面的学生成绩表中，可能要经常查看某一学生的成绩；当学生退学时要删除相应的结点；进来新学生时要增加结点。究竟如何进行查找、删除、插入，这就是数据的运算问题。搞清楚了上述三个问题，也就弄清了学生成绩表这个数据结构。数据的逻辑结构分类在不产生混淆的前提下，常将数据的逻辑结构简称为数据结构。数据的逻辑结构有两大类：（1）线性结构线性结构的逻辑特征是：若结构是非空集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。线性表是一个典型的线性结构。栈、队列、串等都是线性结构。(2)非线性结构非线性结构的逻辑特征是：一个结点可能有多个直接前趋和直接后继。数组、广义表、树和图等数据结构都是非线性结构。队队列的基础知识到医院看病排队挂号排队、在学校食堂就餐排队买饭、到银行办理存款或取款业务排队、共同的特征，严格遵守先来后到原则，不存在插队现象队列(Queue)是一种特殊的线性表。它是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front),允许插入的一端称为队尾(rear)。因此队列亦称作先进先出(FirstInFirstOut)的线性表，简称FIFO表栈回顾线性表的特性：除了首尾结点，所有的结点都有前驱和后继；首结点只有后继没有前驱，尾结点只有前驱没有后继；线性表的任何位置都可以进行插入、删除等操作。现在我们对线性表的操作做一点限制，规定所有的插入或删除操作只能在线性表的一端进行，这样的线性表称为栈(stack)。栈是一种特殊的线性表，对它的插入和删除都限制在表的同一端进行。一、栈的概念和特性把可以操作的一端称为栈顶，不允许操作的一端称为栈底。在栈顶插入一个元素，称为进栈，在栈顶删除一个元素称为出栈。栈中元素的进出是按后进先出的原则进行，这是栈结构的重要特征。(LIFO:LastInFirstOut)用一个变量记录栈顶的位置，通常称这个变量为栈指针。中缀表达式转换后缀表达式从左向右扫描表达式、运算数送到输出队列、运算符进栈、如果运算优先级大于栈顶元素直接进栈，如果运算优先级小于或等于栈顶元素，则先弹出栈顶元素，再进栈、左括号直接进栈、右括号则依次弹出栈中的元素，直到遇到第一个左括号为止。赛前知识点梳理二

(树、二叉树)树是一种重要的非线性数据结构，很象自然界中的树那样，从树根到大分枝、小分枝、直到叶子把数据联系起来，这种数据结构就叫做树结构，简称树。树中每个分叉点称为结点，起始结点称为根结点，任意两个结点间的连接关系称为树枝，结点下面不再有分枝称为树叶。结点的前趋结点称为该结点的”双亲”，结点的后趋结点称为该结点的”子女”或”孩子"，同一结点的”子女”之间互称”兄弟”。树结构的特点是：它的每一个结点都可以有不止一个直接后继，除根结点外的所有结点都有且只有一个直接前趋。树的基本术语结点的度和树的宽度一个结点拥有的子树的个数称为是该结点的度，树的所有结点中的最大度为该树的宽度分支结点和叶结点度为0的结点称为叶结点或端结点、度大于0的结点称作分支结点(根结点除外)树的基本术语2树的深度在树的结构中，结点的层数从树根开始定义，根结点在第一层，其子结点在第二层，以此类推。树中结点最大的层号为树的深度。有序树和无序树若结点的子树有次序排列，且先后次序不能互换，这样的树称为有序树，反之为无序树。森林森林是若干棵互不相交的树构成的集合。二叉树的定义 xOPQQ如果树中每个结点的子树个数小于或等于2,并且各 / \/\子树的次序不能互换，有左、右子树之分，这样的 |. °、 | °.°树称为二叉树。二叉树是一种度为2的有序树。d「c'c二叉树共有5种不同的基本形态。a,空二叉树；b.只有一个根结点的二叉树；c.右子树为空的二叉树；d.左子树为空的二叉树;.左、右子树非空的二叉树。N个结点的二叉树有C(N,2N)/(N+1)二叉树的性质性质1：二叉树第i(i>=1)层的结点总数不超过2i-1；性质2：深度为k的二叉树的结点总数不超过2k-1(k>=1)。第1层1个结点，20、第2层2个结点，21、第3层4个结点，22第i层2i-1个结点；对于深度为k的二叉树所具有的结点总数为：2人0+2人1+2人2+……+2A(k-1)=2Ak-1特殊的二叉树满二叉树：如果一个深度为K的二叉树，具有2k-1个结点，则称该二叉树为满二叉树。满二叉树最底一层的各个结点的度数为0，而其余的结点的度数均为2。对于给定深度，满二叉树的结点数最多。完全二叉树：如果一棵深度为K二叉树，1至k-1层的结点都是满的，即满足2i-1，只有最下面的一层的结点数小于2i-1，并且最下面一层的结点都集中在该层最左边的若干位置，则此二叉树称为完全二叉树。二叉树性质3在任意二叉树中，如果其叶结点的个数为N0，其度数为2的结点总数为N2,则有：N0=N2+1设有一棵k叉树，其中只有度为0和k两种结点，设n0，nk，分别表示度为0和度为k的结点个数，试求出n0和nk之间的关系(n0=数学表达式，数学表达式仅含nk、k和数字)。n0和nk之间的关系为：n0=(k-1)nk+1二叉树的性质对于完全二叉树，结点的位置与结点编号的关系：如果i=1，则i为根，无父结点；如果i<>1，则父结点为［i/2］。如果2*i<=N，则i的左儿子的编号为2*i。如果2*i+1<=N，则i的右儿子的编号为2*i+1。二叉树的遍历二叉树的遍历不外乎这么四种：①先根(先序)遍历；②中根(中序)遍历；③后根(后序)遍历；④宽度优先(按层)遍历。先根遍历的顺序是先访问根结点，然后是左子树，最后是右子树；中根遍历的顺序是先访问左子树，然后是根结点，最后是右子树；后根遍历的访问顺序是先访问左子树，然后是右子树，最后是根结点；宽度优先遍历是先根结点，然后自上而下、从左到右按层访问，直到树中每个结点都被访问完为止。考试题一般不正面考，也就是说，不可能给你画好一棵二叉树，让你写出它的遍历序列，而是给出它的某两个遍历序列，或是其他条件，让你自己画出可能的二叉树，从而推出相应的遍历序列。常见的题型有如下几种：由中根序列和后根序列来确定二叉树的结构，从而判断先根遍历序列及其它。例如：(NOIP2001提高组试题)已知一棵二叉树的结点名为大写英文字母，其中序与后序遍历的顺序分别为：CBGEAFHDIJ与CGEBHFJIDA则该二叉树的先序遍历的顺序为：解析：已知中序序列为CBGEAFHDI(1) 后序序列为CGEBHFJIDA。(2)TOC\o"1-5"\h\z由(2)知：根结点为A 兰由(1)知：A的左子树中序序列为CBGE(3) •.：A的右子树中序序列为FHDIJ(4)由(2)知：A的左子树后序序列为CGEB(5) 威垒，A的右子树后序序列为HFJID(6) '-由(5)(6)知：A的左子树根结点为B，A的右子树根结点为D由(3)(4)知：B的左子树为C，右子树中序序列为GED的左子树中序序列为FH，右子树中序序列为IJ由(5)(6)知：B的右子树后序序列为GE，即根结点为ED的左子树后序序列为HF，即根结点为FD的右子树后序序列为JI，即根结点为I综上可推出二叉树的结构如图所示故该二叉树的先序遍历序列为：ABCEGDFHIJ由前序序列和中序序列来确定一棵二叉树，从而判断后序序列及其它。例如：(NOIP2004提高组试题)二叉树T，已知其前序遍历序列为1243576，中序遍历序列为4215736,则其后序遍历序列为(B )。A.4257631B.4275631C.4275361D.4723561E.452637l由先根序列和后根序列来推断二叉树的结构，从而判断中根遍历序列以及其他。例如：(NOIP2007提高组第14题)已知7个结点的二叉树的先根遍历是1245637f数字为结点的编号，以下同)，后根遍历是4652731，则该二叉树的可能的中根遍历是()。A.4265173B.4256137C.4231547D.4256173解析：先根遍历序列是1245637(1)后根遍历序列是4652731(2)

由（1）和（2）知：根结点为l,1的左子树根结点是2,右子树根结点是3,结点4是结点2的左子树，可以判断结点5是结点2的右子树的根结点，但结点6可能是结点5的左子树，也可能是它的右子树，同样结点7可能是结点3的左子树，也可能是它的右子树。对应的二叉树的结构可能是如下四种:图③的图③的中序遍历序列是：4265137，：：：图④的中序遍历序列是：425613可 故此题的答案应选ABD（四）通过二叉树的宽度优先遍历和树中结点的最大深度及结点之间的关系来判断树的结构，从而解决有关问题。例如：（NOIP2005提高组试题）二叉树T的宽度优先遍历序列为ABCDEFGHI，已知A是C的父结点，D是G的父结点，F是I的父结点，树中所有结点的最大深度为3（根结点深度设为0），可知E的父结点可能是（）。A.AB.BC. CD. DE.F解析：二叉树的宽度优先遍历就是按层遍历，从根结点自上而下，自左向右访问树中的每个结点。由题目可知A是根结点，又知A是C的父结点，可以推知B是A的左子树的根结点，C是A的右子树的根结点。又知D是G的父结点，F是I的父结点，树中所有结点的最大深度为3,故E结点可能是B结点的右子树，也可能是G结点的左子树。二叉树的部分结构图为下图①②所示：故E的父结点可能是B，也可能是C。（五）二叉树的应用。有些题目要求写