noip数学模型及二叉树的应用

数学模型及二叉树的应用什么是数学模型?•计算机处理的是数•而题目的描述是文字•信息学与数学有什么相似，有什么不同？思考方法•1．用自己的语言复述问题这实际上是从自然语言上对信息原型的转化，有利于我们抓住其主要属性；•2．用数学的语言复述问题我们抓住了信息原型的主要属性，接着用数学语言描述出来。实际上是将信息原型进行抽象，以建立适当的数学模型；•3．联想有关的知识事实上，当我们用数学语言描述信息原型时，如果所得结果简单明了，可以直接形成算法或构造简单模型。我们就运用机理分析法一来解决了（即一级创造）。如果不行，则需要“联想有关知识”。这实际上是往“一级摹仿”靠近。主要联想的是相似的信息原型或存在关系的已知数学模型。•4．推出有用的事实如果联想到的知识可以帮我们建立数学模型。那么，我们自然可以套用算法解题了。但进一步延伸下去，也就是达到“二级摹仿”。我们针对该信息原型的特有属性，得出某些“有用”的事实来改进优化模型和算法。•5．大胆的创造当然，通过以上四步，我们能够较好的建立一个正确高效数学模型就不错了。但通过上述四步，我们很可能在脑海中酝酿着模糊的新模型。不要埋没它，大胆的创造，很有可能建立一种新的具有广泛适用性的模型或一套新的方法体系。这也就是我们所说的“二级创造”。例题：NOIP2005篝火晚会一共有n个同学，编号从1到n。一开始，同学们按照1，2，……，n的顺序坐成一圈，而实际上每个人都有两个最希望相邻的同学。如何下命令调整同学的次序，形成新的一个圈，使之符合同学们的意愿，成为摆在佳佳面前的一大难题。佳佳可向同学们下达命令，每一个命令的形式如下：(b1,b2,...bm-1,bm)这里m的值是由佳佳决定的，每次命令m的值都可以不同。这个命令的作用是移动编号是b1，b2，……bm–1，bm的这m个同学的位置。要求b1换到b2的位置上，b2换到b3的位置上，……，要求bm换到b1的位置上。执行每个命令都需要一些代价。我们假定如果一个命令要移动m个人的位置，那么这个命令的代价就是m。我们需要求出最小的代价•这是一个实际问题•怎么找到问题的本质？•置换群？另一个例题•对于任意一个{0,1,2......N-1}的排列A[0],A[1]......A[N-1]。可以得到它的衍生序列(Childarray)B。•其中B[0]=0,当0iN时，B[i]=A[B[i-1]]。•比如下列的排列及其衍生序列：•PermutationChildarray•{0,1,2}{0,0,0}•{0,2,1}{0,0,0}•{1,0,2}{0,1,0}•{1,2,0}{0,1,2}•{2,0,1}{0,2,1}•{2,1,0}{0,2,0}•而一个排列被称为是完美(Perfect)的，当且仅当其衍生序列也是一个{0,1,2......N-1}的排列。比如上面的排列{1,2,0}和{2,0,1}。•现在给你一个0~N-1的排列P，他想找到一个完美排列Q。使得P和Q的差异最小。两个排列的差异即为使得P[i]≠Q[i]的i的个数(0=iN)。•问题看起来很复杂，怎么分析？•还是置换群•两道看起来风马牛不相及的题，最终都可以化归到群论！•这就是数学模型例题3•构造一个长度为N的数列{An}，满足任意连续的P个数0，任意连续的Q个数0。•例如N=5,P=2,Q=3，则•-23-23-2是满足条件的一个数列•题目本身似乎就已经有了模型。•但怎么解题呢？•定义Si=A1+A2+…+Ai，S0=0•列出Si之间的不等关系。•再建立一个图论模型，使用拓扑排序求解。二叉树树和森林•树：n0个结点的集合，根+其余结点分为m=0个集合，每一个集合本身又是一棵树（子树）•结点的度：该结点的子树数目•树的度：树中各结点度数的最大值•叶子、父结点、儿子结点、兄弟结点•祖先结点：从根结点到该结点的路径上所有结点•层次、高度：根为1,依次往下数•有序树：规定所有结点的儿子结点次序，否则为无序树•森林：m=0棵互不相交树的集合其它表示方法：1.(A(B(L,E),C(F),D(G(I),H))2.类似于书籍的目录表示法。高度定义为层数或层数－1，都可以；本书定义为层数。ABCDEFGHIL高度为4、度为3的树例：结点总数为3时的所有二叉树的树的形状二叉树的定义空或有一个根，根有左子树、右子树；而左右子树本身又是二叉树。和树的区别：可为空左右子树有序，不可颠倒BCDEFL例：二叉树二叉树的性质•性质1：在二叉树的第i层上至多有2i-1个结点BCDEFLA1层：结点个数21-1=20个2层：结点个数22-1=21个3层：结点个数23-1=22个证：k=1时成立，设k=i-1时成立则当k=i时在二叉树的第i层上至多有2i-1-1*2=2i-1个结点•性质2：高度为k的二叉树至多有2k-1个结点证：利用性质1，将第1层至第k层的最多的结点数进行相加：1+2+22+…………+2k-2+2k-1=2k-1•性质3：二叉树的叶子结点数n0等于度为2的结点数n2+1证：设度为1的结点数为n1，树枝的总数为B则：B=n-1=n0+n1+n2-1又B=n1+2×n2；原命题得证。CEFLA完全二叉树BCDEFLAPSQRUBCDEFLAPSQRXUWV•满二叉树:每层结点数最多•完全二叉树:1、满二叉树2、从满二叉树最底层从右向左依次去掉若干结点形成的性质4：具有n个结点的完全二叉树高度为log2n+1证：根据性质2和完全二叉树的定义：设其高度为k2k-1-1n=2k-12k-1n+1=2k2k-1=n2k故：k-1=log2nk;原命题得证。完全二叉树BCDEFLAPSQRU性质5：对一棵有n个结点的完全二叉树按照从第一层（根所在的层次〕到最后一层，并且每一层都按照从左到右的次序进行编号。根结点的编号为1，最后一个结点的编号为n。1：对任何一个编号为i的结点而言，它的左儿子的编号为2i(若2i=n),而右儿子的编号为2i+1(若2i+1=n)。2：对任何一个编号为j的结点而言，它的父亲结点的的编号为j/2。根结点无父结点。证：对编号归纳121110987654321二叉树的顺序存储一般情况：ABCDEFGHILA1-1B92C53D6-1E-1-1F-1-1G87H-1-1I-1-1L-140123456789rightleftdata应用范围：适用于二叉树上的结点个数已知，或不支持动态存储分配的高级语言。二叉树的顺序存储特殊情况：完全二叉树A23B45C67D89E100F00G00H00I00L00012345678910rightleftdata应用范围：适用于完全二叉树，且结点个数已知。DCGEFBAHILABCDEFGHI0123456789L二叉树的链接存储仅定义结点的类型即可。结点之间的关系通过指针实现。ABCDEFGHILdataleftright标准形式：（二叉链表）广义标准形式：（三叉链表）dataleftrightParent二叉树的链接存储例：A∧B/\∧∧∧∧∧∧CDEFGGFDCBAE二叉树遍历设N代表根节点，L代表左子树，R代表右子树。a.前序（或先序）：如果二叉树为空，则操作为空：否则访问根结点；前序遍历左子树；前序遍历右子树。记为：NLR。b.中序：如果二叉树为空，则操作为空：否则中序遍历左子树；访问根结点；中序遍历右子树。记为：LNR。c.后序：如果二叉树为空，则操作为空：否则后序遍历左子树；后序遍历右子树；访问根结点。记为：LRN。前序：A、L、B、E、C、D、W、X中序：B、L、E、A、C、W、X、D后序：B、E、L、X、W、D、C、ABCDELAXW二叉树的确定•前序（后序）＋中序唯一确定一棵二叉树例：前序:A、B、D、E、F、C中序:D、B、E、F、A、CEFABCD1.二叉排序树的概念:二叉排序树是一种动态树表。二叉排序树的定义：二叉排序树或者是一棵空树，或者是一棵具有如下性质的二叉树：⑴若它的左子树非空，则左子树上所有结点的值均小于根结点的值；⑵若它的右子树非空，则右子树上所有结点的值均大于根结点的值；⑶左、右子树本身又各是一棵二叉排序树。二叉排序树的性质：按中序遍历二叉排序树，所得到的中序遍历序列是一个递增有序序列。二叉排序树2.二叉排序树的插入:在二叉排序树中插入新结点，要保证插入后的二叉树仍符合二叉排序树的定义。插入过程：若二叉排序树为空，则待插入结点*S作为根结点插入到空树中；当非空时，将待插结点关键字S-key和树根关键字t-key进行比较，若s-key==t-key,则无须插入，若s-keyt-key,则插入到根的左子树中，若s-keyt-key,则插入到根的右子树中。而子树中的插入过程和在树中的插入过程相同，如此进行下去，直到把结点*s作为一个新的树叶插入到二叉排序树中，或者直到发现树已有相同关键字的结点为止。•3.二叉排序树的查找:在当前二叉排序树上找到某特定元素。•思考：怎么利用二叉排序树的性质加快查找？•4.二叉排序树的应用:•查找当前第K大元素•查询某元素在当前所有元素中的排名堆一个顺序存储的完全二叉树，如果任何一个结点的值都不小于或不大于它左右子树（如果有的话）中所有结点的值，那么这个顺序存储的序列就是堆。这个二叉树的根被称为堆顶，最后一层最右端的叶子结点称为堆底。由于堆是一个顺序存储的完全二叉树，所以一个长度是n的序列要成为一个堆，必须存储在容量是n+1的顺序表中，其中0号单元不用。堆顶r[1]是整个序列的最大值或者最小值。堆顶是最大值的堆被称为大顶堆或者极大堆；堆顶是最小值的堆被称为小顶堆或者极小堆。73291311151716197329131115121619171321199111625472(a)(b)(c)怎么建堆？•自底向上调整？堆排序【堆排序的基本思想】首先将一个序列构建成堆；然后将堆顶与堆底交换，再去掉堆底，剩余的序列可能不是堆，将它再调整成堆，再将堆顶与堆底交换。如此重复直到堆只有一个结点为止。【需要解决的问题】如何将一个替换掉堆顶的堆重新调整成堆？一个完全二叉树，根的左右子树都是堆，而整棵二叉树不是堆。问如何将这棵二叉树调整成堆。堆的应用•NOIP2004合并果子等